Insert at Beginning

Inserting at the front of a singly linked list is O(1): create a node, set its next to the current head, then make that node the new head. Works when the list is empty (head == NULL) too.

C program (return new `head`)

The function returns the updated head pointer so main can write head = insert_begin(head, value);.

newNode->next = head; links the rest of the list (or NULL if list was empty).
return newNode; makes the new node the head.

Singly linked list: node values and head pointer after insert at beginning — List values and `head` — new node becomes the front.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void free_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

int main(void)
{
    struct Node *head = NULL;

    head = insert_begin(head, 30);
    head = insert_begin(head, 20);
    head = insert_begin(head, 10);

    print_list(head);   /* 10 20 30 */

    free_list(head);
    return 0;
}

Program output

10 20 30

Overall program flow

Step	Operation	`head` points to	List state (values)
1	`head = NULL`	`NULL`	Empty list
2	`head = insert_begin(head, 30)`	Node with data `30`	`30`
3	`head = insert_begin(head, 20)`	Node `20` → node `30`	`20 30`
4	`head = insert_begin(head, 10)`	Node `10` → `20` → `30`	`10 20 30`
5	`print_list(head)`	Same as step 4	Output line: `10 20 30`
6	`free_list(head)`	All nodes freed	List destroyed (no nodes left)

Each `insert_begin` call in detail

Call 1: insert_begin(NULL, 30)

Step	Operation	Variable	Value
1	Allocate new node	`newNode`	Address: `0x1000`
2	Set `newNode->data`	`newNode->data`	`30`
3	Set `newNode->next`	`newNode->next`	`head` (`NULL`)
4	Return `newNode`	return value	`0x1000`

After call 1:

head → [30 | NULL]

Call 2: insert_begin(0x1000, 20)

Step	Operation	Variable	Value
1	Allocate new node	`newNode`	Address: `0x2000`
2	Set `newNode->data`	`newNode->data`	`20`
3	Set `newNode->next`	`newNode->next`	`head` (`0x1000`)
4	Return `newNode`	return value	`0x2000`

After call 2:

head → [20 | 0x1000] → [30 | NULL]

Call 3: insert_begin(0x2000, 10)

Step	Operation	Variable	Value
1	Allocate new node	`newNode`	Address: `0x3000`
2	Set `newNode->data`	`newNode->data`	`10`
3	Set `newNode->next`	`newNode->next`	`head` (`0x2000`)
4	Return `newNode`	return value	`0x3000`

After call 3:

head → [10 | 0x2000] → [20 | 0x1000] → [30 | NULL]

Memory layout (example addresses)

Final list in heap

Address	Node	`data`	`next`	Points to
`0x3000`	`n1` (newest insert)	10	`0x2000`	`n2`
`0x2000`	`n2`	20	`0x1000`	`n3`
`0x1000`	`n3` (first insert)	30	`NULL`	nowhere

Visual representation

head (0x3000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: 0x2000 ┼───→│ next: 0x1000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘
     n1                   n2                   n3
  (inserted last)     (inserted 2nd)      (inserted first)

Detailed step-by-step: call 3 (insert `10`)

Inside insert_begin when head is 0x2000 and data is 10:

Line	Code	Before	After
1	`malloc(sizeof(struct Node))`	—	Heap block at `0x3000`; `newNode = 0x3000`
2	`if (newNode == NULL)`	`newNode = 0x3000` (not `NULL`)	Skip `return head`
3	`newNode->data = data;`	`newNode->data` uninitialized	`newNode->data = 10`
4	`newNode->next = head;`	`head` passed in = `0x2000`	`newNode->next = 0x2000`
5	`return newNode;`	Return value `0x3000`	In `main`: `head = 0x3000`

Complexity summary

Operation	Time	Extra space
`insert_begin`	`O(1)`	`O(1)` for the one new node
`print_list`	`O(n)`	`O(1)`
`free_list`	`O(n)`	`O(1)`
Whole program (build + print + free)	`O(n)`	`O(n)` nodes stored in the list

The key takeaway is that inserting at the beginning of a linked list is O(1) time: you only allocate one node and update the head pointer, no matter how long the list already is.

Alternative: pass struct Node **head and update *head inside the function—same logic, no return value needed.