Insert at Beginning of Doubly Linked List in DSA C++

Mental Model

Add a new node at the start by linking it before the current first node and updating the head pointer.

Analogy: Imagine adding a new book at the front of a shelf where each book is connected to the one before and after it.

null ← 1 ↔ 2 ↔ 3 -> null
↑head

Dry Run Walkthrough

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

Goal: Add a new node with value 0 at the start of the list and update links correctly

Step 1: Create new node with value 0

null ← 1 ↔ 2 ↔ 3 -> null
↑head   new(0)

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

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

null ← 1 ↔ 2 ↔ 3 -> null
new(0) -> 1 ↔ 2 ↔ 3 -> null
↑head

Why: New node should point forward to the old first node

Step 3: Set current head's prev to new node

null ← new(0) ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Why: Old first node must point back to new node

Step 4: Update head pointer to new node

null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Why: Head must now point to the new first node

Result:

null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

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

    void insertAtBeginning(int val) {
        Node* newNode = new Node(val); // create new node
        if (head == nullptr) {
            head = newNode; // empty list, new node is head
            return;
        }
        newNode->next = head; // link new node to old head
        head->prev = newNode; // link old head back to new node
        head = newNode; // update head to new node
    }

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

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

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

    return 0;
}

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

create new node with given value

if (head == nullptr) { head = newNode; // empty list, new node is head return; }

handle empty list by making new node the head

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

point new node's next to current head

head->prev = newNode; // link old head back to new node

set old head's prev to new node

head = newNode; // update head to new node

update head pointer to new node

Output

Before insertion:

1 ↔ 2 ↔ 3 -> null

After inserting 0 at beginning:

0 ↔ 1 ↔ 2 ↔ 3 -> null

Complexity Analysis

Time: O(1) because insertion at beginning only changes a few pointers without traversal

Space: O(1) because only one new node is created regardless of list size

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

Edge Cases

empty list

new node becomes the head with no next or prev

DSA C++

if (head == nullptr) {
            head = newNode; // empty list, new node is head
            return;
        }

list with one node

new node links correctly before the single existing node

DSA C++

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

When to Use This Pattern

When you need to add an element quickly at the start of a doubly linked list, use this pattern to update pointers efficiently without traversal.

Common Mistakes

Mistake: Forgetting to update the old head's prev pointer to the new node
Fix: Always set head->prev = newNode after linking newNode->next = head

Mistake: Not handling empty list case causing null pointer errors
Fix: Check if head is nullptr and set head = newNode directly

Summary

Inserts a new node at the start of a doubly linked list by updating next and prev pointers.

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

The key is to link the new node before the current head and update the head pointer.

Practice

1. What is the main purpose of inserting a node at the beginning of a doubly linked list?

easy

A. To delete the first node of the list

B. To add a new node before the current head node

C. To add a new node after the tail node

D. To reverse the entire list

Solution

1. Step 1: Understand the head node position

   The head node is the first node in the doubly linked list.

2. Step 2: Insert new node before head

   Inserting at the beginning means placing the new node before the current head and updating pointers.

3. Final Answer:

   To add a new node before the current head node -> Option B

4. Quick Check:

   Insert at beginning = Add before head [OK]

Hint: Insert at beginning means new node becomes the head [OK]

Common Mistakes:

• Confusing insertion at beginning with insertion at end
• Not updating the previous head's previous pointer
• Trying to delete instead of insert

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

easy

A. Node* newNode = new Node(data); head->prev = newNode; newNode->next = head; head = newNode;

B. Node newNode = Node(data); newNode->next = head; head = newNode;

C. Node* newNode = new Node(data); head->next = newNode; newNode->prev = head; head = newNode;

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

Solution

1. Step 1: Create new node with pointer

   Use pointer syntax: Node* newNode = new Node(data);

2. Step 2: Update pointers for doubly linked list

   Set newNode->next to current head, update head->prev to newNode, then update head to newNode.

3. Final Answer:

   Node* newNode = new Node(data); head->prev = newNode; newNode->next = head; head = newNode; -> Option A

4. Quick Check:

   Correct pointer updates = Node* newNode = new Node(data); head->prev = newNode; newNode->next = head; head = newNode; [OK]

Hint: Remember to update both next and prev pointers [OK]

Common Mistakes:

• Using object instead of pointer for new node
• Not updating head->prev pointer
• Swapping next and prev pointers incorrectly

3. What will be the output of the following code snippet after inserting 10 at the beginning of the doubly linked list?

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

Node* head = new Node(20);
head->next = new Node(30);
head->next->prev = head;

Node* newNode = new Node(10);
newNode->next = head;
head->prev = newNode;
head = newNode;

// Print list from head
Node* temp = head;
while(temp) {
  std::cout << temp->data << " -> ";
  temp = temp->next;
}
std::cout << "null";

medium

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

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

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

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

Solution

1. Step 1: Initial list setup

   List initially: 20 <-> 30, head points to 20.

2. Step 2: Insert 10 at beginning

   New node 10 points next to 20, 20's prev points to 10, head updated to 10.

3. Step 3: Print list from head

   Traverse from head: 10 -> 20 -> 30 -> null

4. Final Answer:

   10 -> 20 -> 30 -> null -> Option C

5. Quick Check:

   New head is 10, followed by 20 and 30 [OK]

Hint: New node becomes head, old head shifts right [OK]

Common Mistakes:

• Not updating head pointer after insertion
• Incorrect pointer assignments causing wrong order
• Printing from tail instead of head

4. Identify the error in the following code snippet that inserts a node at the beginning of a doubly linked list:

void insertAtBeginning(Node*& head, int data) {
  Node* newNode = new Node(data);
  newNode->next = head;
  head->prev = newNode;
  head = newNode;
}

medium

A. newNode->prev should be set to head

B. newNode->next should be set to nullptr

C. head pointer should not be passed by reference

D. Missing check if head is nullptr before accessing head->prev

Solution

1. Step 1: Analyze pointer usage

   Code accesses head->prev without checking if head is nullptr (empty list).

2. Step 2: Identify potential runtime error

   If head is nullptr, accessing head->prev causes a crash (null pointer dereference).

3. Final Answer:

   Missing check if head is nullptr before accessing head->prev -> Option D

4. Quick Check:

   Always check head != nullptr before head->prev [OK]

Hint: Check if list is empty before updating pointers [OK]

Common Mistakes:

• Ignoring nullptr checks causing crashes
• Incorrect pointer assignments for prev
• Passing head by value instead of reference

5. Given a doubly linked list with nodes containing values [5, 15, 25], write the sequence of node values after inserting 1 at the beginning and then 35 at the beginning. What is the final list?

hard

A. 35 -> 1 -> 5 -> 15 -> 25 -> null

B. 1 -> 35 -> 5 -> 15 -> 25 -> null

C. 5 -> 15 -> 25 -> 1 -> 35 -> null

D. 35 -> 5 -> 15 -> 25 -> 1 -> null

Solution

1. Step 1: Initial list

   List is 5 -> 15 -> 25 -> null.

2. Step 2: Insert 1 at beginning

   New head is 1, list becomes 1 -> 5 -> 15 -> 25 -> null.

3. Step 3: Insert 35 at beginning

   New head is 35, list becomes 35 -> 1 -> 5 -> 15 -> 25 -> null.

4. Final Answer:

   35 -> 1 -> 5 -> 15 -> 25 -> null -> Option A

5. Quick Check:

   Last inserted node is new head [OK]

Hint: Last inserted node at beginning becomes new head [OK]

Common Mistakes:

• Inserting nodes at end instead of beginning
• Not updating head pointer after each insertion
• Mixing order of inserted nodes