Insert at Beginning of Doubly Linked List in DSA C++ - Execution Trace

Concept Flow - Insert at Beginning of Doubly Linked List

Create new node

↓

Set new_node.next = head

↓

If head != null

↓

Set head.prev = new_node

↓

Set head = new_node

↓

Done: new node is new head

The new node is created and linked before the current head. If the list is not empty, the old head's previous pointer is updated. Finally, head points to the new node.

Execution Sample

DSA C++

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

void insertAtBeginning(Node*& head, int val) {
  Node* new_node = new Node{val, nullptr, head};
  if (head) head->prev = new_node;
  head = new_node;
}

This code inserts a new node with value val at the start of a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	∅	head = ∅	List is empty
2	Create new node with data=10	Node(10)	new_node created with prev=∅, next=∅	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
3	Set new_node.next = head (∅)	Node(10)	new_node.next = ∅	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
4	Since head is ∅, skip head.prev update	Node(10)	No change	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
5	Set head = new_node	Node(10)	head → new_node	head ┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
6	Insert second node with data=20	Node(20) → Node(10)	new_node created with prev=∅, next=head(Node10) head.prev = new_node head = new_node	Before: head → Node(10) After: head → Node(20) → Node(10) Pointers: Node(20).prev=∅ Node(20).next=Node(10) Node(10).prev=Node(20) Node(10).next=∅
7	Insert third node with data=30	Node(30) → Node(20) → Node(10)	new_node created with prev=∅, next=head(Node20) head.prev = new_node head = new_node	Before: head → Node(20) → Node(10) After: head → Node(30) → Node(20) → Node(10) Pointers: Node(30).prev=∅ Node(30).next=Node(20) Node(20).prev=Node(30) Node(20).next=Node(10) Node(10).prev=Node(20) Node(10).next=∅
8	Termination	List built with 3 nodes	head points to Node(30)	Final list: head → Node(30) → Node(20) → Node(10) prev pointers: Node(10).prev=Node(20) Node(20).prev=Node(30) Node(30).prev=∅

💡 Insertion stops after updating head to new node; list head updated correctly.

Variable Tracker

Variable	Start	After Step 5	After Step 6	After Step 7	Final
head	∅	Node(10)	Node(20)	Node(30)	Node(30)
new_node	∅	Node(10)	Node(20)	Node(30)	Node(30)
new_node.prev	∅	∅	∅	∅	∅
new_node.next	∅	∅	Node(10)	Node(20)	Node(20)
head.prev	N/A	∅	Node(20)	Node(30)	Node(30)

Key Moments - 3 Insights

Why do we set new_node.next = head before changing head?

Because new_node must point to the current first node before head changes, as shown in step 3 and step 6 in the execution_table.

Why do we update head.prev only if head is not null?

If head is null, there is no node to update. This is shown in step 4 where head is ∅, so no prev pointer is set.

How does the prev pointer help in a doubly linked list?

It allows backward traversal and proper linking. In step 6 and 7, head.prev is updated to new_node to maintain backward links.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the prev pointer of the old head after insertion?

A It points to the new node inserted

B It remains null

C It points to itself

D It points to the next node

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6 in execution_table.

At which step does the head pointer first change from null to a node?

A Step 1

B Step 2

C Step 5

D Step 6

💡 Hint

Look at the 'Pointer Changes' column to see when head is assigned a new node.

If we insert a new node when the list is empty, what will be the prev and next pointers of the new node?

A prev = new node, next = null

B prev = null, next = null

C prev = null, next = head

D prev = head, next = new node

💡 Hint

Refer to step 2 and 3 where the first node is created and linked.

Concept Snapshot

Insert at Beginning of Doubly Linked List:
- Create new node with data
- Set new_node.next to current head
- If head exists, set head.prev to new_node
- Update head to new_node
- New node becomes list head with prev=null
- Maintains forward and backward links

Full Transcript

This visualization shows how to insert a new node at the beginning of a doubly linked list. First, a new node is created with its next pointer set to the current head. If the list is not empty, the previous pointer of the old head is updated to point back to the new node. Finally, the head pointer is updated to the new node, making it the first node in the list. The execution table traces each step, showing pointer changes and the list's visual state. The variable tracker follows the head and new_node pointers through the process. Key moments clarify why pointer updates happen in a specific order. The quiz tests understanding of pointer assignments and list state changes. This method ensures the doubly linked list remains correctly linked in both directions after insertion.

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