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.

Practice

1. What is the main advantage of using a linked list to implement a dequeue compared to an array?

easy

A. Dynamic size allows easy insertion and deletion at both ends

B. Faster access to elements by index

C. Uses less memory than arrays

D. Simpler to implement than arrays

Solution

1. Step 1: Understand linked list flexibility

   A linked list can grow or shrink dynamically without needing a fixed size.

2. Step 2: Compare with array limitations

   Arrays have fixed size and costly resizing; linked lists allow easy insertion/deletion at both ends.

3. Final Answer:

   Dynamic size allows easy insertion and deletion at both ends -> Option A

4. Quick Check:

   Linked list dynamic size = Advantage [OK]

Hint: Linked lists grow/shrink easily at ends [OK]

Common Mistakes:

• Confusing faster index access with linked list
• Thinking linked lists always use less memory
• Assuming arrays are simpler to implement

2. Which of the following is the correct way to declare a node structure for a dequeue using a linked list in C?

easy

A. struct Node { int data; struct Node* next; };

B. struct Node { int data; struct Node next; struct Node prev; };

C. struct Node { int data; int next; int prev; };

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

Solution

1. Step 1: Identify node fields for dequeue

   A dequeue node needs data and pointers to next and previous nodes for double linking.

2. Step 2: Check pointer types

   Correct syntax uses pointers (struct Node*) for next and prev, not int or struct Node directly.

3. Final Answer:

   struct Node { int data; struct Node* next; struct Node* prev; }; -> Option D

4. Quick Check:

   Double linked node = data + next ptr + prev ptr [OK]

Hint: Double linked nodes need next and prev pointers [OK]

Common Mistakes:

• Using int instead of pointer for next/prev
• Missing prev pointer for dequeue
• Declaring next/prev as struct Node instead of pointer

3. Consider the following operations on an empty dequeue implemented using a linked list:
insertFront(10); insertRear(20); insertFront(5); deleteRear();
What will be the state of the dequeue from front to rear after these operations?

medium

A. 5 -> 10 -> null

B. 10 -> 5 -> null

C. 20 -> 10 -> null

D. 5 -> 20 -> null

Solution

1. Step 1: Perform insertFront(10) and insertRear(20)

   Dequeue: 10 (front) -> 20 (rear)

2. Step 2: Perform insertFront(5) and deleteRear()

   After insertFront(5): 5 -> 10 -> 20
   After deleteRear(): removes 20, so 5 -> 10

3. Final Answer:

   5 -> 10 -> null -> Option A

4. Quick Check:

   Front insert adds at front, rear delete removes last [OK]

Hint: Track front and rear changes stepwise [OK]

Common Mistakes:

• Confusing insertFront and insertRear order
• Forgetting to delete rear element
• Mixing up front and rear positions

4. The following C code snippet for deleting from the front of a dequeue has an error. What is the error?

void deleteFront() {
  if (front == NULL) {
    printf("Dequeue is empty\n");
    return;
  }
  struct Node* temp = front;
  front = front->next;
  if (front == NULL) {
    rear = NULL;
  }
  free(temp);
}

medium

A. Uses free() incorrectly

B. Does not check if dequeue is full

C. Does not update the prev pointer of new front node

D. Does not update rear pointer when dequeue becomes empty

Solution

1. Step 1: Analyze pointer updates after deletion

   After moving front to front->next, the new front's prev pointer still points to old node.

2. Step 2: Identify missing update

   Must set front->prev = NULL to maintain correct double link.

3. Final Answer:

   Does not update the prev pointer of new front node -> Option C

4. Quick Check:

   Update prev pointer after front deletion [OK]

Hint: Always reset prev of new front to NULL [OK]

Common Mistakes:

• Ignoring prev pointer update
• Checking dequeue full in delete function
• Not updating rear when empty (not shown here)

5. You want to implement a function to reverse a dequeue implemented using a doubly linked list. Which approach correctly reverses the dequeue?

hard

A. Only swap front and rear pointers without changing node links

B. Swap next and prev pointers of each node, then swap front and rear pointers

C. Delete all nodes and re-insert them from rear to front

D. Traverse from front to rear and copy data into a new list in reverse order

Solution

1. Step 1: Understand reversing a doubly linked list

   Reversing means each node's next and prev pointers must be swapped to reverse direction.

2. Step 2: Swap front and rear pointers

   After swapping pointers in nodes, front and rear pointers must also be swapped to reflect new ends.

3. Final Answer:

   Swap next and prev pointers of each node, then swap front and rear pointers -> Option B

4. Quick Check:

   Swap links + swap ends = reverse dequeue [OK]

Hint: Swap next/prev in nodes, then swap front/rear [OK]

Common Mistakes:

• Only swapping front and rear pointers
• Rebuilding list instead of reversing links
• Copying data instead of changing pointers