Dequeue Using Linked List in DSA C - Execution Trace

Concept Flow - Dequeue Using Linked List

Create new node

↓

Is Dequeue empty?

↓

Set front and rear

↓

For Dequeue operations

↓

Update pointers accordingly

↓

Print or return updated Dequeue

Shows how nodes are added or removed from front or rear in a linked list based dequeue.

Execution Sample

DSA C

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

// Insert at front
void insertFront(int val);

This code snippet shows the node structure and a function to insert a node at the front of the dequeue.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize empty dequeue	None	front = NULL, rear = NULL	NULL
2	Insert 10 at front	10	front -> newNode(10), rear -> newNode(10)	10 <-> NULL
3	Insert 20 at rear	10, 20	rear -> newNode(20), newNode(10).next = newNode(20), newNode(20).prev = newNode(10)	10 <-> 20 <-> NULL
4	Insert 5 at front	5, 10, 20	front -> newNode(5), newNode(5).next = old front(10), old front(10).prev = newNode(5)	5 <-> 10 <-> 20 <-> NULL
5	Delete front node	10, 20	front -> old front.next(10), old front(10).prev = NULL	10 <-> 20 <-> NULL
6	Delete rear node	10	rear -> old rear.prev(10), old rear(20) removed	10 <-> NULL
7	Delete front node	None	front = NULL, rear = NULL	NULL
8	Try delete front on empty dequeue	None	No change	NULL

💡 Execution stops after all insertions and deletions are performed, including handling empty dequeue.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
front	NULL	Node(10)	Node(10)	Node(5)	Node(10)	Node(10)	NULL	NULL
rear	NULL	Node(10)	Node(20)	Node(20)	Node(20)	Node(10)	NULL	NULL
List Size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why do we update both front and rear pointers when inserting the first node?

Because when the dequeue is empty (Step 2), the new node is both the front and rear, so both pointers must point to it as shown in the execution_table row 2.

Why do we set the prev pointer of the new front node to NULL after deletion?

After deleting the front node (Step 5), the new front node has no node before it, so its prev pointer must be NULL to mark it as the start, as seen in the pointer changes column.

What happens if we try to delete from an empty dequeue?

No changes occur to front or rear pointers (Step 8), and the dequeue remains empty, preventing errors, as shown in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the visual state of the dequeue?

A 10 <-> 20 <-> NULL

B 5 <-> 10 <-> 20 <-> NULL

C 5 <-> 20 <-> NULL

D 10 <-> NULL

💡 Hint

Check the Visual State column at Step 4 in the execution_table.

At which step does the dequeue become empty again after deletions?

A Step 6

B Step 7

C Step 5

D Step 8

💡 Hint

Look at the List Size and Visual State columns in the execution_table.

If we insert a node at rear when dequeue is empty, what pointers change?

A Only rear pointer changes

B Only front pointer changes

C Both front and rear pointers change

D No pointer changes

💡 Hint

Refer to Step 2 where first insertion updates both front and rear pointers.

Concept Snapshot

Dequeue using linked list:
- Nodes have data, next, prev pointers
- InsertFront: new node becomes front, update pointers
- InsertRear: new node becomes rear, update pointers
- DeleteFront: remove front node, update front pointer
- DeleteRear: remove rear node, update rear pointer
- Handle empty dequeue by setting front and rear to NULL

Full Transcript

This visual execution trace shows how a dequeue is implemented using a doubly linked list. We start with an empty dequeue where front and rear pointers are NULL. When inserting the first node, both front and rear point to it. Subsequent insertions at front or rear update pointers accordingly, linking nodes with next and prev. Deletions remove nodes from front or rear, updating pointers and handling empty state by resetting front and rear to NULL. The trace carefully tracks the list nodes, pointer changes, and visual state after each operation, helping learners see how the dequeue structure changes step-by-step.