Stacks and Queues using Linked List

The array-based stack and queue both share the same limitation: a fixed-size array means an OVERFLOW check, and a full array refuses further insertions even if the program has plenty of free memory elsewhere. A linked list has no such limit, a new node is allocated on demand, so a linked-list-based stack or queue only runs out of room when the machine itself runs out of memory.

Stack using linked list

A stack becomes a linked list where all insertion and deletion happens at the head, one end only, exactly matching the LIFO rule.

In an array-based stack, TOP is usually an integer index that tells us the position of the top element. In a linked-list stack, TOP is different: it is a pointer to the top node itself.

PUSH: inserting at the head

Pushing a new value means the same operation as inserting at the beginning of a linked list.

PUSH(TOP, item)
 
1. Create NEW
2. NEW->data = item
3. NEW->next = TOP
4. TOP = NEW
5. Return TOP

Pushing 40 onto a stack currently holding 30 → 20 → 10 (TOP at the node holding 30):

NEW is created and filled with 40, still disconnected from the stack:

Step 3 sets NEW->next = TOP, wiring NEW onto the front of the existing chain, though TOP itself hasn't moved yet:

Step 4 moves TOP onto NEW, and the stack is 40 → 30 → 20 → 10, top to bottom:

There's no overflow check here, unlike the array version, since a new node can always be allocated as long as memory is available. PUSH is O(1), identical to insertion at the beginning of a linked list.

POP: removing from the head

Popping the top value is the same operation as deletion at the beginning.

POP(TOP)
 
1. If TOP == NULL
       Return UNDERFLOW
2. TEMP = TOP
3. item = TEMP->data
4. TOP = TOP->next
5. free(TEMP)
6. Return item

Example 1: empty stack. Popping when TOP == NULL. Step 1 catches this immediately and returns UNDERFLOW, since there's no node to remove.

Example 2: non-empty stack. Popping from 40 → 30 → 20 → 10 (TOP at the node holding 40). TEMP marks the node about to be removed, before TOP moves:

Step 4 moves TOP to the second node, then step 5 frees TEMP. The popped value is 40, and the stack is now 30 → 20 → 10:

Just as with deletion at the beginning of a linked list, TEMP has to be saved before TOP moves, otherwise the node about to be freed becomes unreachable. POP is O(1), since it only ever touches the head node.

Queue using linked list

A queue becomes a linked list where insertion happens at one end and removal at the other, matching the FIFO rule, insertion at the rear, removal at the front.

Unlike the stack, a linked-list queue needs two pointers, since insertion and removal happen at opposite ends, one link cannot reach both without a full traversal.

ENQUEUE: inserting at the rear

ENQUEUE(FRONT, REAR, item)
 
1. Create NEW
2. NEW->data = item
3. NEW->next = NULL
4. If FRONT == NULL
       FRONT = NEW
       REAR = NEW
       Return
5. REAR->next = NEW
6. REAR = NEW

Example 1: enqueue into an empty queue. Inserting 10 when FRONT == NULL. Step 4 catches this: both FRONT and REAR are set to point at NEW, the single node now being both ends of the queue at once:

Example 2: enqueue into a non-empty queue. Inserting 30 into 10 → 20 (FRONT at 10, REAR at 20). NEW is created and filled with 30, not yet linked:

Step 5 sets REAR->next = NEW, attaching NEW after the current rear node:

Step 6 moves REAR onto NEW, giving 10 → 20 → 30:

Reaching the rear node here is a direct O(1) pointer read, REAR is always tracked, so there's no need to walk the list from FRONT the way a plain linked list's insert-at-end would. ENQUEUE is O(1), as long as REAR is maintained.

DEQUEUE: removing from the front

DEQUEUE(FRONT, REAR)
 
1. If FRONT == NULL
       Return UNDERFLOW
2. TEMP = FRONT
3. item = TEMP->data
4. FRONT = FRONT->next
5. If FRONT == NULL
       REAR = NULL
6. free(TEMP)
7. Return item

Example 1: empty queue. Dequeuing when FRONT == NULL. Step 1 catches this immediately and returns UNDERFLOW.

Example 2: dequeuing the only node. Dequeuing from a queue holding just 10 (FRONT and REAR both at that node):

TEMP marks the node, FRONT moves to TEMP->next, which is NULL. Step 5 catches this and resets REAR to NULL as well, otherwise REAR would keep pointing at a freed node with nothing behind it. Once TEMP is freed, the queue is empty: FRONT == NULL and REAR == NULL.

Example 3: dequeuing from a longer queue. Dequeuing from 10 → 20 → 30 (FRONT at 10, REAR at 30). TEMP marks the front node before it moves:

Step 4 moves FRONT to the second node, then TEMP is freed. The dequeued value is 10, and the queue is 20 → 30:

REAR only needs resetting when the queue becomes completely empty (example 2); as long as at least one node remains, REAR is untouched by a dequeue, it never pointed at the front in the first place. DEQUEUE is O(1), since it only ever touches the front node.

Why this beats the array version

The array-based circular queue solves the wasted space problem of a plain array queue, but still has a hard capacity limit. A linked-list queue avoids the wasted-space problem entirely, since removed nodes are freed rather than left behind as unusable array slots, and there is no capacity to run out of in the first place.

Quick recall

• A linked-list stack pushes and pops only at TOP, the head of the list; both operations are the same as insert/delete at the beginning of a linked list.
• A linked-list queue needs two pointers, FRONT (removal) and REAR (insertion), since the two ends are different nodes.
• Neither structure needs an OVERFLOW check, since nodes are allocated on demand instead of drawing from a fixed-size array.
• Emptying a linked-list queue completely requires resetting both FRONT and REAR to NULL, not just FRONT, otherwise REAR is left pointing at freed memory.
• Every core operation, PUSH, POP, ENQUEUE, DEQUEUE, is O(1), the same complexity as the array-based versions, without the fixed-capacity trade-off.