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

Concept Flow - Insert at Beginning of Doubly Linked List

Create new node with data

↓

Set new_node.prev = NULL

↓

Set new_node.next = head

↓

If head != NULL?

No→Skip

|Yes↓

Set head.prev = new_node

↓

Set head = new_node

↓

Done

This flow shows how a new node is created and inserted at the start of the doubly linked list, updating pointers carefully.

Execution Sample

DSA C

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

void insertAtBeginning(struct Node** head, int data) {
  struct Node* new_node = malloc(sizeof(struct Node));
  new_node->data = data;
  new_node->prev = NULL;
  new_node->next = *head;
  if (*head != NULL) (*head)->prev = new_node;
  *head = new_node;
}

This code creates a new node and inserts it at the beginning of a doubly linked list, updating the head pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	Empty	new_node allocated	∅
2	Set new_node.prev = NULL	new_node(10)	new_node.prev = NULL	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
3	Set new_node.next = head (NULL)	new_node(10)	new_node.next = NULL	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
4	Check if head != NULL (head is NULL)	new_node(10)	No change	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
5	Set head = new_node	new_node(10)	head → new_node	head ┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
6	Insert 20 at beginning	new_node(10)	Create new_node(20)	head → 10
7	Set new_node.prev = NULL	20 → 10	new_node(20).prev = NULL	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:? │ │ next:? │ │ next:∅ │ └────────┘ └────────┘
8	Set new_node.next = head (10)	20 → 10	new_node(20).next = 10	┌────────┐ ┌────────┐ │ data:20│ ──→│ data:10│ │ prev:∅ │ │ prev:? │ │ next:──┼ │ next:∅ │ └────────┘ └────────┘
9	Set head.prev = new_node (10.prev = 20)	20 → 10	10.prev = 20	┌────────┐ ┌────────┐ │ data:20│ ──→│ data:10│ │ prev:∅ │ │ prev:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘
10	Set head = new_node (head → 20)	20 → 10	head → 20	head ┌────────┐ ┌────────┐ │ data:20│ ──→│ data:10│ │ prev:∅ │ │ prev:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘
11	Insert 30 at beginning	20 → 10	Create new_node(30)	head → 20
12	Set new_node.prev = NULL	30 → 20 → 10	new_node(30).prev = NULL	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:? │ │ prev:? │ │ next:? │ │ next:? │ │ next:∅ │ └────────┘ └────────┘ └────────┘
13	Set new_node.next = head (20)	30 → 20 → 10	new_node(30).next = 20	┌────────┐ ──→ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:? │ │ prev:? │ │ next:──┼ │ next:? │ │ next:∅ │ └────────┘ └────────┘ └────────┘
14	Set head.prev = new_node (20.prev = 30)	30 → 20 → 10	20.prev = 30	┌────────┐ ──→ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:──┼ │ prev:? │ │ next:──┼ │ next:? │ │ next:∅ │ └────────┘ └────────┘ └────────┘
15	Set head = new_node (head → 30)	30 → 20 → 10	head → 30	head ┌────────┐ ──→ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:──┼ │ prev:? │ │ next:──┼ │ next:? │ │ next:∅ │ └────────┘ └────────┘ └────────┘
16	End of insertions	30 → 20 → 10	No change	head ┌────────┐ ──→ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:──┼ │ prev:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘

💡 All nodes inserted at beginning; head updated each time; prev and next pointers set correctly.

Variable Tracker

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

Key Moments - 3 Insights

Why do we set new_node.prev to NULL when inserting at the beginning?

Because the new node becomes the first node, it has no previous node. See execution_table step 2 and 7 where new_node.prev is set to NULL.

Why do we update the old head's prev pointer to new_node?

To maintain the backward link in the doubly linked list. Without this, the old head would not point back to the new first node. See execution_table step 9 and 14.

What happens if the list is empty before insertion?

The head is NULL, so new_node.next is set to NULL and no prev pointer update is needed. See execution_table step 4 where head is NULL and step 5 where head is set to new_node.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what pointer change happens?

A The old head's prev pointer is set to new_node

B The new_node.next is set to NULL

C The head pointer is set to NULL

D The new_node.prev is set to old head

💡 Hint

Check the 'Pointer Changes' column at step 9 in execution_table.

At which step does the head pointer first point to the new node with data 20?

A Step 5

B Step 15

C Step 10

D Step 2

💡 Hint

Look at the 'Pointer Changes' and 'Visual State' columns for when head changes to node with data 20.

If the list was not empty, what must be updated after setting new_node.next = head?

A new_node.prev must be set to head

B head.prev must be set to new_node

C head.next must be set to new_node

D new_node.next must be set to NULL

💡 Hint

Refer to execution_table steps 8 and 9 where new_node.next and head.prev are updated.

Concept Snapshot

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

Full Transcript

To insert a node at the beginning of a doubly linked list, first create a new node and assign the data. Set the new node's prev pointer to NULL because it will be the first node. Set its next pointer to the current head of the list. If the list is not empty, update the old head's prev pointer to point back to the new node. Finally, update the head pointer to the new node. This ensures the list maintains correct forward and backward links. The execution table shows each step with pointer changes and the visual state of the list after each insertion.

Practice

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

easy

A. To add a new node after the tail node

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

C. To delete the first node of the list

D. To reverse the entire list

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes connected both forward and backward, with a head and tail.

2. Step 2: Identify what inserting at the beginning means

   Inserting at the beginning means adding a new node before the current head node, making it the new head.

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
• Thinking insertion deletes nodes
• Mixing up head and tail positions

2. Which of the following is the correct way to update the previous pointer of the old head node when inserting a new node at the beginning in C?

easy

A. new_node->prev = old_head;

B. old_head->next = new_node;

C. new_node->next = old_head->prev;

D. old_head->prev = new_node;

Solution

1. Step 1: Identify pointer updates when inserting at beginning

   The new node's next points to old head, and old head's prev points back to new node.

2. Step 2: Choose correct pointer update for old head

   We must set old_head->prev = new_node to link backward to new node.

3. Final Answer:

   old_head->prev = new_node; -> Option D

4. Quick Check:

   Old head prev points to new node [OK]

Hint: Old head's prev points to new node after insertion [OK]

Common Mistakes:

• Setting old_head->next instead of prev
• Assigning new_node->prev incorrectly
• Forgetting to update old head's prev pointer

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

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

Node* head = NULL;

void insertAtBeginning(int val) {
  Node* new_node = (Node*)malloc(sizeof(Node));
  new_node->data = val;
  new_node->prev = NULL;
  new_node->next = head;
  if (head != NULL) {
    head->prev = new_node;
  }
  head = new_node;
}

int main() {
  insertAtBeginning(20);
  insertAtBeginning(10);
  Node* temp = head;
  while (temp != NULL) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  return 0;
}

medium

A. 10

B. 20 10

C. 10 20

D. 20

Solution

1. Step 1: Trace first insertion insertAtBeginning(20)

   List is empty, new node with 20 becomes head: 20 -> NULL

2. Step 2: Trace second insertion insertAtBeginning(10)

   New node with 10 points next to old head (20), old head prev points to new node, head updated to 10: 10 <-> 20

3. Final Answer:

   10 20 -> Option C

4. Quick Check:

   List after insertions = 10 20 [OK]

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

Common Mistakes:

• Printing nodes in reverse order
• Not updating head pointer
• Forgetting to update old head's prev pointer

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

void insertAtBeginning(int val) {
  Node* new_node = (Node*)malloc(sizeof(Node));
  new_node->data = val;
  new_node->prev = NULL;
  new_node->next = head;
  if (head != NULL) {
    head->next = new_node;
  }
  head = new_node;
}

medium

A. head->next should be head->prev when updating old head

B. new_node->prev should not be NULL

C. head pointer should not be updated

D. malloc size is incorrect

Solution

1. Step 1: Check pointer updates for old head

   When inserting at beginning, old head's prev pointer must point to new node, not next.

2. Step 2: Identify incorrect line

   Code uses head->next = new_node; which wrongly sets old head's next pointer instead of prev.

3. Final Answer:

   head->next should be head->prev when updating old head -> Option A

4. Quick Check:

   Old head prev must point to new node [OK]

Hint: Old head prev, not next, points to new node [OK]

Common Mistakes:

• Updating old head's next pointer instead of prev
• Not updating head pointer
• Incorrect malloc size usage

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25. You want to insert a new node with value 1 at the beginning. After insertion, what will be the correct sequence of node values when traversing from head to tail?

medium

A. 1 <-> 5 <-> 15 <-> 25

B. 5 <-> 15 <-> 25 <-> 1

C. 25 <-> 15 <-> 5 <-> 1

D. 1 <-> 15 <-> 5 <-> 25

Solution

1. Step 1: Understand insertion at beginning

   New node with value 1 becomes new head, pointing next to old head (5).

2. Step 2: Update pointers and traverse list

   Sequence after insertion: 1 (head) <-> 5 <-> 15 <-> 25 (tail).

3. Final Answer:

   1 <-> 5 <-> 15 <-> 25 -> Option A

4. Quick Check:

   New head is 1, followed by old nodes [OK]

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

Common Mistakes:

• Appending new node at end instead of beginning
• Mixing node order after insertion
• Not updating head pointer