DSA Series Chapter 6 : Step-by-Step simulation of enqueue and dequeue for the linked-list queue

on

Before moving with this topic, you must check this first ,

DSA Series Chapter 6 : Queues 

Step-by-Step simulation of enqueue and dequeue for the linked-list queue Used symbolic addresses (NodeA@0x100) so you can follow memory and pointers precisely.

Notation

  • front and rear are struct Node * in struct Queue.

  • A node: [ data | next ]

  • NULL represents a null pointer.

  • newNode = malloc(...) creates a node (shown with a symbolic address).

Initial state — empty queue

front -> NULL
rear  -> NULL

ENQUEUE (value = 10) — inserting into an empty queue

Pseudo-code steps (typical):

  1. newNode = (struct Node*)malloc(sizeof(struct Node));

  2. newNode->data = 10;

  3. newNode->next = NULL;

  4. if rear == NULL (queue empty) then:

    • front = rear = newNode;
      else

    • rear->next = newNode; rear = newNode;

Execution with symbolic addresses:

  1. Allocate: newNode = NodeA@0x100

    • NodeA: [ 10 | NULL ]

  2. Since rear == NULL (empty), do:

    front = NodeA@0x100
rear  = NodeA@0x100

Resulting layout

front/rear
   ↓
[ 10 | NULL ]   (NodeA@0x100)

Notes: front == rear because only one node exists.

ENQUEUE (value = 20) — inserting into non-empty queue

Before operation

front -> NodeA@0x100 [10 | NULL]
rear  -> NodeA@0x100 [10 | NULL]

Steps

  1. newNode = NodeB@0x110 → [20 | NULL]

  2. rear->next = newNode;

    • NodeA.next = NodeB@0x110

  3. rear = newNode;

After

front -> NodeA@0x100 [10 | next -> 0x110]
                     ↓
                    NodeB@0x110 [20 | NULL]
                              ↑
                             rear

Pointer updates

  • NodeA.next changed from NULL → 0x110

  • rear updated from 0x100 → 0x110

ENQUEUE (value = 30) — repeat

  1. newNode = NodeC@0x120 → [30 | NULL]

  2. rear->next = newNode; (NodeB.next -> NodeC)

  3. rear = newNode;

Queue

front -> NodeA@0x100 [10] -> NodeB@0x110 [20] -> NodeC@0x120 [30 | NULL]
                                                       ↑
                                                      rear

DEQUEUE — remove from front (normal case: >1 node)

Before

front -> NodeA@0x100 [10] -> NodeB@0x110 [20] -> NodeC@0x120 [30]
rear  -> NodeC@0x120

Typical pseudo-code:

  1. if front == NULL → queue empty, return / underflow.

  2. temp = front;

  3. value = temp->data;

  4. front = front->next;

  5. if front == NULL then rear = NULL; // queue became empty

  6. free(temp); (optional to show deallocation)

First dequeue (removes 10):

  1. temp = NodeA@0x100

  2. value = 10

  3. front = NodeA->next → front = NodeB@0x110

  4. front != NULL, so do not change rear

  5. free(NodeA)

After

front -> NodeB@0x110 [20] -> NodeC@0x120 [30]
rear  -> NodeC@0x120
(Dequeued value = 10)

DEQUEUE repeatedly until single node removed

Second dequeue (removes 20):

  • temp = NodeB@0x110

  • front = NodeB->next → NodeC@0x120

  • rear unchanged (NodeC@0x120)

  • free NodeB
    Queue after

front -> NodeC@0x120 [30 | NULL]
rear  -> NodeC@0x120
(Dequeued value = 20)

Third dequeue (removes 30) — edge case: single element

  • temp = NodeC@0x120

  • front = NodeC->next → NULL

  • After assigning front = NULL, check if (front == NULL) rear = NULL;

  • So set rear = NULL

  • free NodeC

Queue after

front -> NULL
rear  -> NULL
(Dequeued value = 30)

Notes: This is the important edge-case: after removing the last element, both front and rear must be set to NULL. Many bugs occur when code forgets to update rear, leaving it as a dangling pointer.

ENQUEUE after some DEQUEUEs (queue reused)

Suppose after previous operations the queue is empty (front = rear = NULL). Now enqueue(40):

  • Allocate NodeD@0x140 [40 | NULL]

  • Because rear == NULL, set front = rear = NodeD@0x140.

Works identically to first enqueue.

DEQUEUE on EMPTY queue (underflow)

Before

front = NULL
rear  = NULL

  • If code calls dequeue(), check if (front == NULL) → return underflow / print error.

  • Do not dereference front or rear (would crash).

Step-by-step pointer table (example timeline)

Step Operation front pointer rear pointer Comment
0 initial NULL NULL empty
1 enqueue(10) NodeA@0x100 NodeA@0x100 single node
2 enqueue(20) NodeA@0x100 NodeB@0x110 NodeA.next -> NodeB
3 enqueue(30) NodeA@0x100 NodeC@0x120 NodeB.next -> NodeC
4 dequeue() NodeB@0x110 NodeC@0x120 removed NodeA
5 dequeue() NodeC@0x120 NodeC@0x120 removed NodeB
6 dequeue() NULL NULL removed NodeC; queue empty
7 dequeue() NULL NULL underflow — nothing to remove

Implementation details to avoid mistakes (practical tips)

  1. Always set newNode->next = NULL when enqueueing — rear must always end with NULL.

  2. Check rear == NULL to decide whether queue is empty — don't check front only (consistent checks are fine).

  3. After dequeue when front becomes NULL, set rear = NULL. Forgetting this leaves rear dangling.

  4. Free removed nodes (if using malloc) to avoid memory leak.

  5. Do not use rear->next without verifying rear != NULL. (safe in enqueue because you check for empty first).

  6. Thread-safety: for concurrent use, protect front/rear with locks; simultaneous enqueue+dequeue otherwise unsafe.

Time & Space complexity (quick recap)

  • enqueue — O(1) time (no traversal), O(1) auxiliary space per operation (for new node).

  Meaning of O(1) in enqueue

When an algorithm has O(1) (constant time) complexity, it means:

The time required to perform the operation does NOT depend on the number of elements in the queue.

Whether the queue has

  • 1 element

  • 10 elements

  • 1,000 elements

  • 1,000,000 elements

…enqueue takes the same amount of time.

  • dequeue — O(1) time, O(1) space.

  • Total space — O(n) nodes in heap for n queued elements.

 

Comments

Post a Comment