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.