Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Stacks and queues using linked lists

Implement and analyze stacks and queues using singly linked lists: node design, push/pop, enqueue/dequeue, invariants, complexities, and complete Python programs with I/O.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Engineers frequently need dynamic, grow/shrink-on-demand LIFO (Last-In-First-Out) and FIFO (First-In-First-Out) data structures. Implementing stacks and queues using linked lists avoids fixed-size limits and costly shifts that appear in array-based versions, which is valuable in compilers, network buffers, schedulers, and real-time pipelines.

Key ideas

  • Definition: A node is a data structure with two fields: one for the stored element (data) and one for a reference to the next node. In Python we model the reference with a variable that holds another Node or None.
  • Definition: A stack is an Abstract Data Type (ADT) that supports operations push(x), pop(), peek(), is_empty(), and size() and obeys the LIFO discipline: the last element pushed is the first element popped. Exact property statement: If a1, a2, …, ak are pushed in that order, then popping k times returns ak, ak−1, …, a1.
  • Definition: A queue is an ADT that supports enqueue(x), dequeue(), front(), is_empty(), and size(), and obeys the FIFO discipline: the first element inserted is the first element removed. Exact property statement: If a1, a2, …, ak are enqueued in that order and k dequeue operations occur (with no intervening enqueues), the outputs are a1, a2, …, ak.
  • Definition: Underflow is the error condition when pop or dequeue is attempted on an empty structure. In safe code we check is_empty() and either raise an exception or return a sentinel.
  • Definition: Overflow is a capacity-exceeded error in fixed-size implementations. In linked lists, overflow does not occur unless memory allocation fails.
  • Assumption for operations analysis: We use a singly linked list with a reference to the top (for stack) or to both front and rear (for queue). Node allocation and pointer assignments are O(1).
  • Theorem (Time complexity): In a stack implemented with a singly linked list, push and pop have worst-case time O(1); in a queue with references to both front and rear, enqueue and dequeue have worst-case time O(1). Proof sketch: Each operation performs a constant number of pointer updates and no traversal.
  • Invariant (Stack via head-as-top): The variable top points to the most recently pushed node; following next links from top visits elements in reverse push order; size equals the number of nodes reachable from top. Maintaining this invariant: push makes the new node’s next = old top and then sets top = new node; pop sets top = top.next.
  • Invariant (Queue via front+rear): The variable front points to the node to be dequeued next; rear points to the most recently enqueued node; if the queue is empty, both front and rear are None. Enqueue on empty sets both to the new node; otherwise rear.next = new node and rear = new node. Dequeue moves front = front.next; if front becomes None, set rear = None.
  • Memory model: Each enqueue/push allocates one node; each pop/dequeue releases one node (in Python, garbage collection frees it when no references remain; in C/C++, free/delete is required — see Dynamic memory management and garbage collection topic).
  • Trade-offs vs arrays:
    • Linked list stack/queue have no fixed capacity; no shifting/copying on ends; operations stay O(1).
    • They use extra memory for pointers and have non-contiguous storage, which may reduce cache locality compared to arrays.
  • Diagram to draw (Stack using singly linked list): Draw boxes for nodes stacked vertically; each box has two partitions: left label "data" and right label "next". The top variable is an arrow pointing to the topmost node. For each node, draw an arrow from its next partition to the node below. The last node’s next arrow goes to a small cross or label "None".
  • Diagram to draw (Queue using singly linked list): Draw a horizontal chain of boxes (nodes). Label the leftmost box "front" with an arrow from a front variable; label the rightmost box "rear" with an arrow from a rear variable. Each node’s next arrow points to the next node; the last node’s next is None. Also show the empty case with both front and rear arrows pointing to "None".
  • Circular linked list variant for queue: Definition: A circular singly linked list links the last node’s next back to the first node. If you only store a tail reference, then the front is tail.next. Enqueue at tail.next position by inserting after tail and updating tail; dequeue removes tail.next. Invariant: When non-empty, tail.next is the front; when empty, tail is None; tail.next always points to a valid node.
  • Error handling policy: For pop/dequeue on empty, either return a special value (not recommended if data can be any value) or raise an exception. In Python, raising IndexError is conventional.
  • Space complexity: If n is the number of elements, the data structure uses O(n) node storage plus O(1) references (top or front+rear). Each node has data plus one pointer overhead.
  • Use-cases: Stacks — DFS, undo history, recursion simulation (see Recursion and the stack). Queues — BFS, producer-consumer buffers, print/job scheduling, I/O buffering.

Formulas

  • top: Node | None — Stack’s top reference; None means empty.
  • push(x): create new Node(x), new.next = top, top = new — O(1) operation to insert at head.
  • pop(): if top is None -> underflow; else x = top.data; top = top.next; return x — O(1) remove from head.
  • peek(): if top is None -> underflow; else return top.data — O(1) read without removal.
  • front: Node | None, rear: Node | None — Queue’s endpoints; both None means empty.
  • enqueue(x): new = Node(x); if empty: front = rear = new; else rear.next = new; rear = new — O(1) tail insert.
  • dequeue(): if empty -> underflow; else x = front.data; front = front.next; if front is None: rear = None; return x — O(1) head remove.
  • tail: Node | None (circular queue) — Tail reference; empty if None, else tail.next is front.
  • enqueue_circ(x): new = Node(x); if empty: new.next = new; tail = new; else: new.next = tail.next; tail.next = new; tail = new — O(1) insert after tail.
  • dequeue_circ(): if empty -> underflow; else head = tail.next; x = head.data; if head == tail: tail = None; else tail.next = head.next; return x — O(1) remove from head.

Worked examples

Example 1: Stack using singly linked list with command-driven I/O

Program (save as stack_ll.py):

class Node:
    __slots__ = ("data", "next")
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class LinkedListStack:
    def __init__(self):
        self.top = None
        self._size = 0

    def is_empty(self):
        return self.top is None

    def push(self, x):
        self.top = Node(x, self.top)
        self._size += 1

    def pop(self):
        if self.top is None:
            raise IndexError("stack underflow")
        x = self.top.data
        self.top = self.top.next
        self._size -= 1
        return x

    def peek(self):
        if self.top is None:
            raise IndexError("stack underflow")
        return self.top.data

    def size(self):
        return self._size

    def __str__(self):
        # Show stack from top to bottom
        vals = []
        cur = self.top
        while cur is not None:
            vals.append(str(cur.data))
        # safety: break
            cur = cur.next
        return "[top -> " + ", ".join(vals) + "]"

if __name__ == "__main__":
    import sys
    s = LinkedListStack()
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        if line == "end":
            break
        cmd, *rest = line.split()
        if cmd == "push":
            if not rest:
                print("error: push needs a value")
                continue
            s.push(int(rest[0]))
            print("ok")
        elif cmd == "pop":
            try:
                print(s.pop())
            except IndexError as e:
                print("error:", e)
        elif cmd == "peek":
            try:
                print(s.peek())
            except IndexError as e:
                print("error:", e)
        elif cmd == "size":
            print(s.size())
        elif cmd == "show":
            print(s)
        else:
            print("error: unknown command")

Sample input:

push 10
push 20
peek
pop
pop
pop
end

Exact output:

ok
ok
20
20
10
error: stack underflow

Example 2: Queue using singly linked list (front and rear) with command-driven I/O

Program (save as queue_ll.py):

class Node:
    __slots__ = ("data", "next")
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class LinkedListQueue:
    def __init__(self):
        self.front = None
        self.rear = None
        self._size = 0

    def is_empty(self):
        return self.front is None

    def enqueue(self, x):
        node = Node(x)
        if self.front is None:
            self.front = self.rear = node
        else:
            self.rear.next = node
            self.rear = node
        self._size += 1

    def dequeue(self):
        if self.front is None:
            raise IndexError("queue underflow")
        x = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        self._size -= 1
        return x

    def front_value(self):
        if self.front is None:
            raise IndexError("queue underflow")
        return self.front.data

    def size(self):
        return self._size

    def __str__(self):
        vals = []
        cur = self.front
        while cur is not None:
            vals.append(str(cur.data))
            cur = cur.next
        return "[front -> " + ", ".join(vals) + " <- rear]"

if __name__ == "__main__":
    import sys
    q = LinkedListQueue()
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        if line == "end":
            break
        cmd, *rest = line.split()
        if cmd == "enqueue":
            if not rest:
                print("error: enqueue needs a value")
                continue
            q.enqueue(int(rest[0]))
            print("ok")
        elif cmd == "dequeue":
            try:
                print(q.dequeue())
            except IndexError as e:
                print("error:", e)
        elif cmd == "front":
            try:
                print(q.front_value())
            except IndexError as e:
                print("error:", e)
        elif cmd == "size":
            print(q.size())
        elif cmd == "show":
            print(q)
        else:
            print("error: unknown command")

Sample input:

enqueue 5
enqueue 7
front
dequeue
dequeue
dequeue
end

Exact output:

ok
ok
5
5
7
error: queue underflow

Example 3: Circular queue using a single tail pointer (singly linked circular list)

Program (save as circular_queue_ll.py):

class Node:
    __slots__ = ("data", "next")
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class CircularQueue:
    def __init__(self):
        self.tail = None  # empty when None; else tail.next is front
        self._size = 0

    def is_empty(self):
        return self.tail is None

    def enqueue(self, x):
        node = Node(x)
        if self.tail is None:
            node.next = node  # points to itself
            self.tail = node
        else:
            node.next = self.tail.next  # new node points to front
            self.tail.next = node       # old tail points to new
            self.tail = node            # new node becomes tail
        self._size += 1

    def dequeue(self):
        if self.tail is None:
            raise IndexError("queue underflow")
        head = self.tail.next
        x = head.data
        if head is self.tail:  # one element
            self.tail = None
        else:
            self.tail.next = head.next
        self._size -= 1
        return x

    def front(self):
        if self.tail is None:
            raise IndexError("queue underflow")
        return self.tail.next.data

    def size(self):
        return self._size

    def __str__(self):
        # internal pretty-printer to avoid O(n^2) string building patterns
        if self.tail is None:
            return "[front/rear: empty]"
        vals = []
        cur = self.tail.next
        while True:
            vals.append(str(cur.data))
            if cur is self.tail:
                break
            cur = cur.next
        return "[front -> " + ", ".join(vals) + " <- rear]"

if __name__ == "__main__":
    import sys
    cq = CircularQueue()
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        if line == "end":
            break
        cmd, *rest = line.split()
        if cmd == "enqueue":
            if not rest:
                print("error: enqueue needs a value")
                continue
            cq.enqueue(int(rest[0]))
            print("ok")
        elif cmd == "dequeue":
            try:
                print(cq.dequeue())
            except IndexError as e:
                print("error:", e)
        elif cmd == "front":
            try:
                print(cq.front())
            except IndexError as e:
                print("error:", e)
        elif cmd == "size":
            print(cq.size())
        elif cmd == "show":
            # print representation
            if cq.tail is None:
                print("[front/rear: empty]")
            else:
                vals = []
                cur = cq.tail.next
                while True:
                    vals.append(str(cur.data))
                    if cur is cq.tail:
                        break
                    cur = cur.next
                print("[front -> " + ", ".join(vals) + " <- rear]")
        else:
            print("error: unknown command")

Sample input:

enqueue 1
enqueue 2
enqueue 3
front
dequeue
show
size
end

Exact output:

ok
ok
ok
1
1
[front -> 2, 3 <- rear]
2

Common mistakes

  • In circular queues, breaking the circle: not setting node.next = node for the first element, or not updating tail.next during dequeue.
  • Using traversal to find the rear on every enqueue (O(n)) instead of maintaining a rear pointer (O(1)).
  • For stacks, pushing at the tail/end of a singly linked list, which makes push O(n); correct is to push at the head to keep O(1).
  • Missing underflow checks before pop/dequeue, causing null dereferences or exceptions.
  • Confusing front and rear arrows in diagrams; marks are lost if labels are swapped.
  • Not handling mixed types or input parsing errors in programs; robust code should validate commands.

For your exam

  • Short notes: Compare array vs linked list implementations (time for push/pop/enqueue/dequeue, memory overhead, capacity). Mention O(1) operations and memory trade-offs.
  • Diagrams: Draw linked-list stack with top; draw linked-list queue with front and rear; draw circular queue with only tail and tail.next as front. Label arrows clearly and show None or the circular link.
  • Algorithms: Stepwise procedures for push, pop, enqueue, dequeue. Include empty/non-empty cases explicitly. State invariants kept after each step.
  • Programs: Implement stack and queue using singly linked lists. Full-marks code includes class Node, proper pointer updates, underflow checks, and demonstration I/O or unit tests. Complexity comments are a plus.
  • Reasoning: Prove O(1) complexity by counting constant pointer operations; note no traversal is needed because of maintained endpoint references.

Quick check

  1. In a linked-list-based queue with front and rear pointers, what exactly must you update when you dequeue the last remaining element?
  2. In a stack implemented using a singly linked list, why is insertion done at the head rather than the tail?
  3. In a circular queue using a single tail pointer, which reference denotes the front element and why?

Answers: 1) Set front = None and also set rear = None to keep the empty invariant. 2) Inserting at the head makes push O(1) because no traversal is needed; inserting at tail would be O(n) without a tail pointer. 3) The front is tail.next because in the circular list tail points to the last node and its next wraps to the logical first (front).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?