GATE/Programming & Data Structures/Linked Lists, Stacks & Queues
Sign in to track
Medium18 min readProgramming & Data Structures

Linked Lists, Stacks & Queues

Singly/doubly linked lists, stack and queue ADTs, implementations, and complexity.

Key Points

  • ·Singly linked list: O(n) search, O(1) insert at head, O(1) delete with node pointer
  • ·Doubly linked list: O(1) delete given node pointer, O(n) space (extra prev pointer)
  • ·Stack (LIFO): push/pop/peek — O(1); used for function calls, expression evaluation
  • ·Queue (FIFO): enqueue/dequeue — O(1) with circular array or linked list
  • ·Circular queue avoids false overflow: rear = (rear+1) % capacity
  • ·Infix to Postfix uses operator-precedence stack; postfix evaluation uses operand stack

Linked List — A Treasure Hunt

Imagine a treasure hunt where each clue tells you where the next clue is hidden. You start at clue 1, which says "go to the oak tree." At the oak tree is clue 2, which says "go to the library." And so on.

A linked list works the same way. Each node holds two things: the actual data, and the address of the next node.

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

A linked list storing 10 → 20 → 30:

[10 | *]──► [20 | *]──► [30 | NULL]
  head

No locker numbers here — each node can be anywhere in memory. The only way to reach node 3 is to follow the chain from node 1 → node 2 → node 3.

Operations and Why They Take That Long

Insert at head (O(1)):

New node:  [5 | *]
Step 1: make new node point to current head
Step 2: update head to new node

Before:        [10]──►[20]──►[30]──►NULL
After:  [5]──►[10]──►[20]──►[30]──►NULL
         head

Just two pointer changes regardless of list size — that's O(1).

Search (O(n)): You must start at head and follow pointers until you find the value. In the worst case you visit every node — O(n).

Delete a node (O(1) if you have the previous node):

Delete 20:
Before:  [10]──►[20]──►[30]
Step: make 10's next point to 30, free 20
After:   [10]──►[30]

Doubly Linked List — Looking Both Ways

Add a prev pointer to each node so you can go backwards too.

[NULL|10|*]──►[*|20|*]──►[*|30|NULL]
     head

Benefit: delete any node in O(1) without needing the previous node (you already have prev). Cost: 1 extra pointer per node.

Floyd's Cycle Detection — Tortoise and Hare

To detect if a linked list has a loop, use two pointers: - Slow (tortoise): moves 1 step at a time - Fast (hare): moves 2 steps at a time

If there's a cycle, the fast pointer will eventually lap the slow pointer and they'll meet inside the cycle. If there's no cycle, fast will reach NULL first.

List with cycle:  1 → 2 → 3 → 4 → 5
                              ↑       |
                              +───────+

Step 1: slow=1, fast=1
Step 2: slow=2, fast=3
Step 3: slow=3, fast=5
Step 4: slow=4, fast=4  ← MEET! Cycle detected.

Stack — A Pile of Plates

A stack works like a pile of plates in a cafeteria. You can only: - Push: add a plate on top - Pop: remove the top plate - Peek: look at the top plate without removing it

Last In, First Out (LIFO).

Push 1, Push 2, Push 3:        Pop:
┌───┐                           ┌───┐
│ 3 │  ← top                    │ 2 │  ← top (3 was removed)
│ 2 │                           │ 1 │
│ 1 │                           └───┘
└───┘
Returns: 3

Uses: function call stack, undo/redo, balanced brackets, infix→postfix.

Infix to Postfix — Step by Step

Convert A + B * C to postfix:

Precedence: * and / > + and -

Scan:  A  →  output: A
Scan:  +  →  push +.  Stack: [+]
Scan:  B  →  output: A B
Scan:  *  →  * has higher precedence than +, push *.  Stack: [+, *]
Scan:  C  →  output: A B C
End   →  pop all:  output: A B C * +

Result: A B C * +

Reading: "multiply B and C, then add A" — which is what A + (B*C) means. ✓

Evaluate Postfix — Step by Step

Evaluate 2 3 4 * +:

Scan 2: push 2.         Stack: [2]
Scan 3: push 3.         Stack: [2, 3]
Scan 4: push 4.         Stack: [2, 3, 4]
Scan *: pop 4 and 3, push 3*4=12.  Stack: [2, 12]
Scan +: pop 12 and 2, push 2+12=14. Stack: [14]
Answer: 14

Queue — A Bus Stop Line

A queue works like people waiting for a bus. The first person to arrive is the first to board.

First In, First Out (FIFO). - Enqueue: join at the rear - Dequeue: leave from the front

Enqueue 1, 2, 3:        Dequeue:
Front                   Front
← [1][2][3] ← Rear      ← [2][3] ← Rear    (1 was removed)

Circular Queue — Solving False Overflow

A simple array queue wastes space: after many enqueue+dequeue operations, front keeps moving right and rear hits the end even though there's space at the beginning.

Solution: treat the array as circular using modulo:

rear = (rear + 1) % capacity
front = (front + 1) % capacity

Capacity = 5, after enqueue 1,2,3 and dequeue 1,2:
Index:    0    1    2    3    4
Value:   [ ]  [ ]   3   [ ]  [ ]
                    ↑
                  front=rear=2

Enqueue 4: rear = (2+1)%5 = 3
Enqueue 5: rear = (3+1)%5 = 4
Enqueue 6: rear = (4+1)%5 = 0  ← wraps around! No false overflow.

Quick Check

Q1. Stack contains (bottom to top): 1, 2, 3, 4. After two pops, what is the top element?

Answer: 2 — pop 4, pop 3, top is now 2.

Q2. Convert (A + B) * C to postfix.

Scan (: push (.          Stack: [(]
Scan A: output A
Scan +: push +.          Stack: [(, +]
Scan B: output A B
Scan ): pop until (: output A B +.  Stack: []
Scan *: push *.          Stack: [*]
Scan C: output A B + C
End: pop all.  output: A B + C *

Answer: **A B + C ***

Key Formulas

  • Circular queue: rear = (rear + 1) % capacity
  • Stack push: arr[++top] = x; Stack pop: return arr[top--]

GATE Exam Tips

  • ★GATE regularly asks to simulate a stack/queue operation sequence — trace step by step
  • ★For infix→postfix: remember * / have higher precedence than + -; left-to-right associativity
  • ★Circular queue: use (size == capacity) to check full, (size == 0) to check empty
  • ★Floyd cycle detection: two pointers meet inside the cycle — also works to find cycle start

Finished reading this topic?

Mark it complete to track your study progress.

Sign in to track