Insert at Beginning Head Insert in DSA C++

Mental Model

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

Analogy: Imagine putting a new book on the front of a stack so it is the first one you see.

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

Dry Run Walkthrough

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

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

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 <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtBeginning(int val) {
        Node* newNode = new Node(val); // create new node
        newNode->next = head;          // link new node to current head
        head = newNode;                // update head to new node
    }

    void printList() {
        Node* curr = head;
        while (curr != nullptr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "null" << endl;
    }
};

int main() {
    LinkedList list;
    list.insertAtBeginning(3);
    list.insertAtBeginning(2);
    list.insertAtBeginning(1);
    cout << "Before insertion:" << endl;
    list.printList();

    list.insertAtBeginning(0);
    cout << "After inserting 0 at beginning:" << endl;
    list.printList();

    return 0;
}

Node* newNode = new Node(val); // create new node

create new node with given value

newNode->next = head; // link new node to current head

point new node's next to current head node

head = newNode; // update head to new node

update head pointer to new node to make it first

Output

Before insertion:

1 -> 2 -> 3 -> null

After inserting 0 at beginning:

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

Complexity Analysis

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

Space: O(1) because we only create one new node regardless of list size

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

Edge Cases

empty list

new node becomes the head and next points to null

DSA C++

newNode->next = head;          // link new node to current head

single element list

new node points to the old single node, becomes new head

DSA C++

head = newNode;                // update head to new node

When to Use This Pattern

When you need to add an item quickly at the start of a list, use head insert because it avoids traversing the list.

Common Mistakes

Mistake: Forgetting to update the head pointer after inserting the new node
Fix: Always assign head = newNode after linking newNode->next to old head

Mistake: Setting newNode->next to nullptr instead of current head
Fix: Set newNode->next = head to keep the existing list connected

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 is updated to new node.

Practice

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

easy

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

B. Deletes the first node of the list

C. Adds a new node at the start of the list, making it the new head

D. Searches for a node at the beginning

Solution

1. Step 1: Understand the operation

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

2. Step 2: Effect on the list

   The new node becomes the head, and its next pointer points to the old head.

3. Final Answer:

   Adds a new node at the start of the list, making it the new head -> Option C

4. Quick Check:

   Insert at beginning = new head [OK]

Hint: New node always becomes the head in beginning insert [OK]

Common Mistakes:

• Confusing insert at beginning with insert at end
• Thinking it deletes nodes
• Assuming it searches instead of inserts

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

easy

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

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

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

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

Solution

1. Step 1: Link new node to current head

   Set newNode->next to point to the current head node.

2. Step 2: Update head to new node

   Assign head to newNode so it becomes the new first node.

3. Final Answer:

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

4. Quick Check:

   Link then update head [OK]

Hint: Set newNode->next first, then update head [OK]

Common Mistakes:

• Updating head before linking newNode->next
• Swapping pointers incorrectly
• Assigning newNode to head->next

3. What will be the output linked list after executing this code?

struct Node { int data; Node* next; };
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
newNode->next = head;
head = newNode;
newNode = new Node{20, nullptr};
newNode->next = head;
head = newNode;

Print the list from head to end.

medium

A. 20 -> 10 -> null

B. 10 -> 20 -> null

C. null -> 10 -> 20

D. 10 -> null

Solution

1. Step 1: Insert first node with data 10

   head points to node with 10, next is nullptr.

2. Step 2: Insert second node with data 20 at beginning

   newNode->next = head (node 10), head = newNode (node 20).

3. Final Answer:

   20 -> 10 -> null -> Option A

4. Quick Check:

   Last inserted node is head [OK]

Hint: Last inserted node is always head [OK]

Common Mistakes:

• Assuming order is insertion order instead of reversed
• Confusing next pointers
• Ignoring nullptr termination

4. Identify the error in this code snippet for inserting at the beginning of a linked list:

Node* newNode = new Node();
newNode->data = 5;
head = newNode;
newNode->next = head;

medium

A. No error, code is correct

B. newNode->data is not initialized

C. head should be set to nullptr first

D. newNode->next should be assigned before head is updated

Solution

1. Step 1: Check pointer assignments order

   Assigning head = newNode before setting newNode->next causes newNode->next to point to itself.

2. Step 2: Correct order

   newNode->next should be set to current head before updating head to newNode.

3. Final Answer:

   newNode->next should be assigned before head is updated -> Option D

4. Quick Check:

   Link newNode->next before head update [OK]

Hint: Always link newNode->next before changing head [OK]

Common Mistakes:

• Updating head before linking newNode->next
• Forgetting to initialize newNode->data
• Assuming no error in pointer assignments

5. Given a linked list with nodes 30 -> 20 -> 10 -> null, what will be the list after inserting a new node with data 40 at the beginning twice in a row?

hard

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

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

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

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

Solution

1. Step 1: Insert first 40 at beginning

   New head is 40, next points to old head 30.

2. Step 2: Insert second 40 at beginning

   New head is another 40, next points to previous 40 node.

3. Final Answer:

   40 -> 40 -> 30 -> 20 -> 10 -> null -> Option A

4. Quick Check:

   Each insert adds new head [OK]

Hint: Each insert adds a new head node [OK]

Common Mistakes:

• Assuming duplicate nodes merge
• Inserting at end instead of beginning
• Losing track of next pointers