Doubly Linked List Structure and Node Design in DSA C - Execution Trace

Concept Flow - Doubly Linked List Structure and Node Design

Create new node

↓

Set node data

↓

Set node prev pointer to NULL

↓

Set node next pointer to NULL

↓

If list empty?

Yes→Set head and tail to new node

No↓

Link new node after tail

↓

Update tail pointer

↓

Done

This flow shows how a new node is created with data and pointers, then linked into the doubly linked list by updating head, tail, and pointers.

Execution Sample

DSA C

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

Defines a doubly linked list node with data and two pointers: prev and next.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	None	new_node->prev = NULL, new_node->next = NULL	NULL
2	Check if list empty	None	head = NULL, tail = NULL	NULL
3	List empty: set head and tail to new_node	10	head = new_node, tail = new_node	NULL <- [10] -> NULL
4	Create new node with data=20	10	new_node->prev = NULL, new_node->next = NULL	NULL <- [10] -> NULL
5	List not empty: link new_node after tail	10, 20	tail->next = new_node, new_node->prev = tail	NULL <- [10] <-> [20] -> NULL
6	Update tail pointer to new_node	10, 20	tail = new_node	NULL <- [10] <-> [20] -> NULL
7	Create new node with data=30	10, 20	new_node->prev = NULL, new_node->next = NULL	NULL <- [10] <-> [20] -> NULL
8	List not empty: link new_node after tail	10, 20, 30	tail->next = new_node, new_node->prev = tail	NULL <- [10] <-> [20] <-> [30] -> NULL
9	Update tail pointer to new_node	10, 20, 30	tail = new_node	NULL <- [10] <-> [20] <-> [30] -> NULL
10	End of insertion sequence	10, 20, 30	No pointer changes	NULL <- [10] <-> [20] <-> [30] -> NULL

💡 All nodes inserted and linked; list is now 3 nodes long with correct prev and next pointers.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
head	NULL	Node(10)	Node(10)	Node(10)	Node(10)
tail	NULL	Node(10)	Node(20)	Node(30)	Node(30)
new_node	NULL	Node(10)	Node(20)	Node(30)	Node(30)

Key Moments - 3 Insights

Why do we set new_node->prev to tail before updating tail?

Because the new node must point back to the current tail before tail moves to the new node, as shown in steps 5 and 8 in the execution_table.

What happens if the list is empty when inserting the first node?

The head and tail pointers are both set to the new node, making it the only node in the list, as shown in step 3.

Why do we initialize new_node->next and new_node->prev to NULL?

To avoid dangling pointers and clearly mark the ends of the list, as shown in steps 1, 4, and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what pointer changes happen?

A head points to new_node and new_node->next points to head

B tail->next points to new_node and new_node->prev points to tail

C new_node->prev and new_node->next are set to NULL

D tail is set to NULL

💡 Hint

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

At which step does the list first have two nodes linked?

A Step 3

B Step 6

C Step 5

D Step 4

💡 Hint

Look at the 'Nodes in List' and 'Visual State' columns in the execution_table.

If we forget to set new_node->prev to tail, what would happen to the list?

A The list would be singly linked forward only, losing backward links

B The list would have cycles

C The head pointer would be NULL

D The tail pointer would not update

💡 Hint

Refer to the 'Pointer Changes' and 'Visual State' columns showing prev pointers.

Concept Snapshot

Doubly Linked List Node:
struct Node { data, prev, next };

Insert Node:
- Create node with data
- Set prev and next to NULL
- If empty list, head=tail=node
- Else link node after tail
- Update tail pointer

Prev points backward, next points forward.

Full Transcript

A doubly linked list node has three parts: data, a pointer to the previous node, and a pointer to the next node. When inserting a new node, we first create it and set its prev and next pointers to NULL. If the list is empty, both head and tail point to this new node. If not empty, we link the new node after the current tail by setting the current tail's next pointer to the new node and the new node's prev pointer back to the tail. Then we update the tail pointer to the new node. This process ensures the list can be traversed forward and backward. The execution table shows each step of inserting three nodes with data 10, 20, and 30, updating pointers and the list structure accordingly.