🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Linked List Head Insertion
Learn how to add a node at the front of a singly linked list in C, the two pointer moves that make it work, and why embedded C programming loves this O(1) operation.
Welcome to the next lecture of our free C programming course. In the last lecture you saw how a self-referential structure lets nodes chain together and how to walk a list from the first node to NULL. Now we start changing the list. The simplest change is adding a new node at the very beginning, and it is also the fastest: it costs the same no matter whether the list holds three nodes or three thousand. If you are following this free C tutorial to prepare for C programming for embedded systems, this is the operation you will meet most often, because event stacks, free-lists and interrupt work queues are all built on it.
What You Will Learn
- What “inserting at the beginning” means for a singly linked list and why it needs only two pointer assignments
- Why the order of those two assignments matters, and what happens when you swap them
- Three ways to write the function: pointer-to-pointer, returning the new head, and a global head
- How to build, run and verify a complete head-insertion program with expected output
- The mistakes beginners make and how embedded C programming teams avoid them
Prerequisites
You should be comfortable with structures, the arrow operator ->, pointers to pointers, and malloc() / free() from earlier chapters of this free embedded C course. You also need the node definition from the previous lecture:
typedef struct node {
int value;
struct node *next;
} node_t;
Why Insert at the Beginning of a Linked List?
A singly linked list only keeps one external handle: the head pointer. Everything else is reachable by following next. Because we already hold the head, putting a new node in front of it needs no traversal at all. We never walk the list, so the work is constant, written as O(1). Compare that with the other places a node can go:
| Where | Needs traversal? | Cost | Typical use |
|---|---|---|---|
| Beginning | No | O(1) | Stacks, undo lists, free-lists, newest-first logs |
| After a known node | No, if you hold that node | O(1) | Sorted insert once the spot is found |
| End (no tail pointer) | Yes, whole list | O(n) | Queues, ordered output |
| Middle by position | Yes, up to that spot | O(n) | Editors, playlists |
Real-world use in embedded firmware
Think of a sensor driver that must remember the most recent readings. New data arrives from an interrupt, and the main loop wants to look at the newest first. Pushing at the head gives you exactly that order for free. A small RTOS keeps its list of ready tasks and its pool of unused buffers the same way. On a microcontroller with a few kilobytes of RAM, an operation that never loops is also an operation with a predictable worst-case time, which matters when you must meet a deadline.
Head Insertion Step by Step
Suppose the list currently holds 10, 20, 30 and we want to put 5 in front. After malloc() and filling in the value, the new node exists but is not yet part of the list: its next holds NULL (or garbage if you forgot to set it). Two moves connect it.
Before insertion: head points at 10, new node floats free
Move 1: new node adopts the old first node
Move 2: head is redirected to the new node
In C those two moves are two lines. First fresh->next = head; makes the new node point at whatever is currently first. Then head = fresh; makes the list’s entry point the new node. Notice that nothing else in the list was touched: nodes 10, 20 and 30 do not even know a neighbour arrived.
Why the order of the two statements matters
If you run head = fresh; first, you have just overwritten the only pointer that knew where 10 lived. The old list is now unreachable, and the following fresh->next = head; makes the new node point at itself. You have leaked every old node and created a loop that hangs your next traversal.
Wrong order: head moved first, old list lost
Writing the Function: Three Styles
A function that changes the head must be able to change the caller’s head variable. Because C passes arguments by value, passing node_t *head gives the function a private copy. Assigning to the copy changes nothing outside. This is the number one reason a beginner’s insert “works inside the function but the list is still empty in main()”.
/* WRONG: head is a copy, the caller never sees the update */
void push_front_bad(node_t *head, int value)
{
node_t *n = malloc(sizeof *n);
n->value = value;
n->next = head;
head = n; /* changes only the local copy */
}
| Style | Signature | Good for | Watch out for |
|---|---|---|---|
| Pointer to pointer | int push_front(node_t **head, int v) | Library-style code; can return an error code | Caller must pass &head |
| Return new head | node_t *push_front_ret(node_t *head, int v) | Short, readable call: head = push_front_ret(head, 5); | Forgetting to assign the result back |
| Global head | int push_front(int v) | Tiny firmware with exactly one list | Hard to test, hard to reuse for a second list |
The pointer-to-pointer form is the one we will use through the rest of this chapter, because it lets the function return a success or failure code and it extends cleanly to deletion.
Complete Linked List Head Insertion Program
The program below builds a list by pushing 40, 30, 20 and 10 (so the list ends up in reverse order of insertion), then uses the second style to push 5. Helper functions make a node, print the list and free it. Every malloc() result is checked, which is non-negotiable in embedded C programming.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *next;
} node_t;
static node_t *make_node(int value)
{
node_t *n = malloc(sizeof *n);
if (n == NULL)
return NULL;
n->value = value;
n->next = NULL;
return n;
}
static void print_list(const node_t *head)
{
for (const node_t *p = head; p != NULL; p = p->next)
printf("%d -> ", p->value);
printf("NULL\n");
}
static void free_list(node_t *head)
{
while (head != NULL) {
node_t *next = head->next;
free(head);
head = next;
}
}
/* Style A: caller passes the address of its head pointer */
static int push_front(node_t **head, int value)
{
node_t *n = make_node(value);
if (n == NULL)
return -1;
n->next = *head; /* step 1: new node adopts the old first node */
*head = n; /* step 2: head now names the new node */
return 0;
}
/* Style B: function returns the new head */
static node_t *push_front_ret(node_t *head, int value)
{
node_t *n = make_node(value);
if (n == NULL)
return head; /* list unchanged on failure */
n->next = head;
return n;
}
int main(void)
{
node_t *head = NULL;
push_front(&head, 40);
push_front(&head, 30);
push_front(&head, 20);
push_front(&head, 10);
print_list(head);
head = push_front_ret(head, 5);
print_list(head);
free_list(head);
return 0;
}
Build and run
gcc -std=c11 -Wall -Wextra -g -o ll_head ll31.c
./ll_head
Expected output:
10 -> 20 -> 30 -> 40 -> NULL
5 -> 10 -> 20 -> 30 -> 40 -> NULL
Notice the first line: we pushed 40 first and 10 last, yet 10 prints first. Head insertion produces newest-first order. That is exactly the behaviour of a stack, which is why this routine is also called push.
Check for leaks while you learn
Compile with -fsanitize=address and run again. If you forget free_list(), the sanitizer prints every leaked node. It is a free safety net while you practise on your PC before moving to a microcontroller.
Common Mistakes and Troubleshooting
| Symptom | Likely cause | Fix |
|---|---|---|
| List still empty after insert | Head passed by value | Pass &head or return the new head |
| Traversal never ends | Swapped the two statements, node points to itself | Set next first, move head second |
| Random crash on print | New node’s next never initialised | Always assign next before publishing |
| Crash on first insert | Dereferenced NULL after failed malloc() | Check the pointer before using it |
| Memory grows forever | Nodes never freed | Free the list in a loop that saves next before freeing |
Best Practices, Performance and Security
- Return an error code instead of calling
exit()inside a data-structure function; the caller knows how to recover. - On small microcontrollers, prefer a fixed pool of nodes over
malloc()to avoid fragmentation. You will build one in the lab lecture of this chapter. - Keep one owner for each node. If two lists point to the same node, a later
free()becomes a double free. - Performance: head insertion is O(1) and touches only one existing cache line, the old first node’s address is merely copied, not dereferenced.
- Security: never trust a count or size that came from outside (UART, network) when deciding how many nodes to push. An attacker or a noisy line can exhaust your heap.
Summary and Key Takeaways
- Head insertion is two assignments: new->next = head, then head = new.
- It is O(1) and produces newest-first order, making it the natural way to build a stack.
- The function must change the caller’s head, so pass its address or return the new head.
- Always check
malloc()and initialisenext.
With this lecture of our free C programming course you can now grow a list from nothing. Next we place nodes somewhere other than the front: after a chosen node and at the end.
Frequently Asked Questions
Why is inserting at the beginning of a linked list O(1)?
Because the head pointer already tells you where the list starts. You never traverse, so the number of existing nodes does not affect the work.
Do I need a double pointer to insert at the head?
You need some way to change the caller’s head variable. A pointer to pointer does it; so does returning the new head and assigning it back.
What happens if I insert into an empty list?
It works with no special case. The head is NULL, so the new node’s next becomes NULL, and then the head points at the new node.
Is head insertion good for embedded C programming?
Yes. It is constant time and needs no loops, so its worst-case timing is predictable. Pair it with a static node pool if your device has no heap.
Why does my list print in reverse order of insertion?
Each new node goes in front of the previous ones, so the newest is first. Insert at the tail if you need arrival order.
Where can I learn more in this free C tutorial series?
Continue with the following lectures on inserting after a node, deleting nodes and building a menu-driven list program.
Keep Learning with the Free Embedded C Course
Every lecture is free, written for students, and built around code you can compile today.

2 Comments