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.

Practice

1. What does the "Insert at Beginning" operation do in a singly linked list?

easy

A. Deletes the first node of the list

B. Adds a new node at the end of the list

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

D. Deletes the last node of the list

Solution

1. Step 1: Understand the operation

   Inserting at the beginning means placing a new node before the current first node.

2. Step 2: Effect on the list

   The new node becomes the head, pushing the old head to second position.

3. Final Answer:

   Adds a new node at the start of the list -> Option C

4. Quick Check:

   Insert at beginning = Add new head [OK]

Hint: New node becomes head, old head moves next [OK]

Common Mistakes:

• Confusing insert at beginning with insert at end
• Thinking it deletes nodes
• Assuming it inserts in the middle

2. Which of the following is the correct syntax to insert a new node at the beginning in C for a singly linked list?

easy

A. newNode->next = head; head = newNode;

B. head = newNode->next; newNode = head;

C. head->next = newNode; newNode = head;

D. newNode = head; head->next = newNode;

Solution

1. Step 1: Assign newNode's next to current head

   This links the new node to the existing list.

2. Step 2: Update head to newNode

   Now the new node is the first node in the list.

3. Final Answer:

   newNode->next = head; head = newNode; -> Option A

4. Quick Check:

   Link newNode to head, then update head [OK]

Hint: Point newNode->next to head, then head to newNode [OK]

Common Mistakes:

• Swapping assignments order
• Assigning head to newNode->next incorrectly
• Not updating head pointer

3. What will be the linked list after inserting nodes with values 10, then 20, then 30 at the beginning in that order? Assume the list was initially empty.

medium

A. 10 -> 20 -> 30 -> null

B. 10 -> 30 -> 20 -> null

C. 20 -> 30 -> 10 -> null

D. 30 -> 20 -> 10 -> null

Solution

1. Step 1: Insert 10 at beginning

   List becomes 10 -> null.

2. Step 2: Insert 20 at beginning

   List becomes 20 -> 10 -> null.

3. Step 3: Insert 30 at beginning

   List becomes 30 -> 20 -> 10 -> null.

4. Final Answer:

   30 -> 20 -> 10 -> null -> Option D

5. Quick Check:

   Last inserted is new head [OK]

Hint: Last inserted node is always head [OK]

Common Mistakes:

• Assuming insertion at end
• Reversing insertion order
• Confusing node values order

4. Given the following code snippet, what is the error that prevents correct insertion at the beginning?

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

void insertAtBeginning(struct Node** head, int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = NULL;
  *head = newNode;
}

medium

A. malloc size is incorrect

B. newNode->next should point to current head before updating head

C. newNode->data is not assigned

D. head pointer should not be double pointer

Solution

1. Step 1: Check newNode->next assignment

   It is set to NULL, losing the existing list.

2. Step 2: Correct linking

   newNode->next should point to current head before head is updated.

3. Final Answer:

   newNode->next should point to current head before updating head -> Option B

4. Quick Check:

   Link newNode->next to old head before head update [OK]

Hint: Link newNode->next to old head before head update [OK]

Common Mistakes:

• Setting newNode->next to NULL always
• Not using double pointer for head
• Forgetting to assign data

5. You have a singly linked list with nodes: 5 -> 15 -> 25 -> null. You want to insert a new node with value 10 at the beginning. After insertion, what will be the correct sequence of nodes?

hard

A. 10 -> 5 -> 15 -> 25 -> null

B. 5 -> 10 -> 15 -> 25 -> null

C. 10 -> 15 -> 25 -> 5 -> null

D. 5 -> 15 -> 25 -> 10 -> null

Solution

1. Step 1: Current list is 5 -> 15 -> 25 -> null

   This is the starting list before insertion.

2. Step 2: Insert 10 at beginning

   New node 10 points to current head (5), then head updated to 10.

3. Final Answer:

   10 -> 5 -> 15 -> 25 -> null -> Option A

4. Quick Check:

   New node becomes head, old head follows [OK]

Hint: New node points to old head, becomes new head [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating head pointer
• Linking nodes incorrectly