Insert at Beginning Head Insert in DSA C

Mental Model

Add a new item right at the start of the list so it becomes the new first item.

Analogy: Imagine putting a new book on the front of a line of books on a shelf, pushing all others back.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, insert value 0 at beginning

Goal: Add 0 at the start so the list becomes 0 -> 1 -> 2 -> 3

Step 1: Create new node with value 0

new_node(0) -> null
head -> 1 -> 2 -> 3 -> null

Why: We need a new node to insert at the beginning

Step 2: Set new node's next to current head (node 1)

new_node(0) -> 1 -> 2 -> 3 -> null
head -> 1 -> 2 -> 3 -> null

Why: Link new node to the existing list so it points to the old first node

Step 3: Update head to new node

head -> 0 -> 1 -> 2 -> 3 -> null

Why: Make new node the first node in the list

Result:

head -> 0 -> 1 -> 2 -> 3 -> null

Annotated Code

DSA C

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

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Insert at beginning function
void insertAtBeginning(Node** head_ref, int new_data) {
    // Create new node
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;

    // Link new node to current head
    new_node->next = *head_ref;

    // Update head to new node
    *head_ref = new_node;
}

// Print list function
void printList(Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("null\n");
}

int main() {
    // Create initial list 1->2->3->null
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    head->next = (Node*)malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;

    printf("Original list: ");
    printList(head);

    // Insert 0 at beginning
    insertAtBeginning(&head, 0);

    printf("After inserting 0 at beginning: ");
    printList(head);

    return 0;
}

Node* new_node = (Node*)malloc(sizeof(Node));

Create new node to hold new data

new_node->data = new_data;

Assign new data to new node

new_node->next = *head_ref;

Link new node to current head node

*head_ref = new_node;

Update head pointer to new node

Output

Original list: 1 -> 2 -> 3 -> null

After inserting 0 at beginning: 0 -> 1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(1) because we only change pointers once without traversing the list

Space: O(1) because we allocate only one new node

vs Alternative: Compared to inserting at the end which requires O(n) traversal, this is faster and simpler

Edge Cases

empty list (head is NULL)

New node becomes the only node and head points to it

DSA C

new_node->next = *head_ref;

When to Use This Pattern

When you need to add an item quickly at the start of a linked list, use head insert to avoid traversal.

Common Mistakes

Mistake: Not updating the head pointer after inserting the new node
Fix: Assign the head pointer to the new node after linking it

Summary

Adds a new node at the start of a linked list.

Use when you want to quickly add elements to the front without traversing.

The new node points to the old head, then head updates to new node.