Stacks, Queues & Linked Lists

1 · Abstract data types vs. implementations basic

Here's a distinction that quietly separates people who write maintainable code from people who don't. When someone says "use a stack," they're describing what it does — not what it's made of. That gap between "what it does" and "how it's built" is one of the most important ideas in this whole track, and it has a name: the abstract data type.

Think of a car's steering wheel. You know its contract — turn left to go left, turn right to go right — without knowing whether behind it sits a rack-and-pinion, a hydraulic system, or drive-by-wire electronics. You could swap the entire mechanism for a better one and every driver's knowledge still works, because they only ever depended on the interface, never the internals.

Data structures work the same way. A stack is defined by its behaviour — push, pop, peek, all last-in-first-out — not by how it's stored. That behaviour is the abstract data type (ADT). You can implement it with an array, a linked list, whatever, as long as it obeys the contract. Why this earns its own section: your agent code talks to the interface ("give me the next task"), so the day you discover your list-based queue is too slow, you can swap in a faster implementation and not one line of caller code changes. The ADT is the promise; the implementation is a swappable detail behind it. Keep that separation in mind for every structure below — each one is a contract first, and a chunk of code second.

2 · Stack — Last In, First Out basic

You use a stack every time you hit Ctrl-Z. Undo doesn't reverse some random edit — it reverses your most recent one, then the one before that, walking backwards in the exact reverse order you did things. That "most recent comes back first" behaviour is a stack, and once you spot the pattern you'll see it everywhere: the browser Back button, the call stack that runs your functions, matching brackets in a parser, an agent unwinding its steps after an error.

The defining rule is LIFO — Last In, First Out: a stack adds and removes only at one end (the "top"). The physical picture is a stack of plates — you can only take the last plate you put down, because it's sitting on top of all the others. You never reach into the middle. Because both actions happen at that single accessible end, push (add) and pop (remove) are each O(1) — no shifting, no searching, just touch the top.

The happy surprise in Python: you don't need a special class. A plain list is a perfect stack — append(x) is push and pop() (with no argument, so it takes from the end) is pop. Both are the O(1) end-operations you met in D1. The lab below builds a tiny explicit Stack wrapper anyway — not because you need it, but so the LIFO contract is spelled out in code you can read.

python# Pythonic: a list IS a stack
stack = []
stack.append("a")          # push
stack.append("b")
top = stack[-1]            # peek -> 'b'  (no removal)
x = stack.pop()            # pop  -> 'b'

# From scratch, so the contract is explicit
class Stack:
    def __init__(self):
        self._items = []
    def push(self, x):        # O(1) amortized
        self._items.append(x)
    def pop(self):            # O(1)
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()
    def peek(self):           # O(1)
        return self._items[-1]
    def is_empty(self):
        return not self._items
    def __len__(self):
        return len(self._items)

pythondef is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)                 # opener -> push
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False              # closer must match the last opener
    return not stack                       # nothing left unclosed

print(is_balanced("{[()]}"))    # True
print(is_balanced("{[(])}"))    # False

3 · Queue — First In, First Out basic → intermediate

If a stack is Ctrl-Z, a queue is the checkout line at a shop: whoever arrived first gets served first, and newcomers join the back. That's FIFO — First In, First Out — the opposite discipline to a stack, and it's how you model anything that should be handled fairly in arrival order: tasks waiting for a worker, messages waiting to be processed, requests waiting for your API.

The mechanics: a queue adds at one end (enqueue, the "back") and removes from the other (dequeue, the "front"). Two different ends — that's the crucial difference from a stack, and it's exactly where beginners get burned.

The trap — and it's a big one. Your instinct will be to use a plain list: append to add at the back, pop(0) to remove from the front. It works… and it's secretly O(n). Remember from D1 §4 why: removing item 0 forces every remaining element to physically shift down one slot to close the gap. Do that inside a loop and you've built a hidden O(n²) that runs fine in testing and melts under real load. The right tool is collections.deque, which is engineered for O(1) at both ends — that's the very next section. Rule of thumb: the moment you need a queue, reach for deque, never list.pop(0).

pythonfrom collections import deque

q = deque()
q.append("task1")          # enqueue at the back  — O(1)
q.append("task2")
first = q.popleft()        # dequeue from the front — O(1)  -> 'task1'

# A from-scratch queue that stays O(1) using two stacks (a classic):
class Queue:
    def __init__(self):
        self._in = []          # push here
        self._out = []         # pop here
    def enqueue(self, x):
        self._in.append(x)                 # O(1)
    def dequeue(self):
        if not self._out:                    # refill only when empty
            while self._in:
                self._out.append(self._in.pop())   # reverse into _out
        if not self._out:
            raise IndexError("dequeue from empty queue")
        return self._out.pop()             # amortized O(1)

4 · Deque — fast at both ends intermediate

We just saw a plain list is a bad queue because its front is slow. The fix is a structure that's fast at both ends — the deque (pronounced "deck", short for double-ended queue). It supports O(1) add and remove at the front and the back. Think of it as a subway car with doors at both ends: people flow in and out either side instantly, no shuffling the whole car.

How it pulls that off (and why it's not just a faster list): CPython's collections.deque isn't one contiguous block — it's a chain of small fixed-size blocks linked together (a doubly-linked list of arrays). Adding at either end just tacks onto the block at that end, so nothing ever shifts. It gives up the O(1) random indexing a list has (you can't jump to d[5000] cheaply) — but for a queue you never index the middle anyway, so that's a trade you happily make.

When to reach for it: any real queue, a sliding window over a stream, or a "keep only the last N" bounded history — deque even takes a maxlen so it auto-drops the oldest item when full, which is a one-liner for chat-history windows. Whenever your problem says "add/remove from the ends," this is the tool.

pythonfrom collections import deque

# maxlen makes it a ring buffer: appending past the limit drops the far end
recent = deque(maxlen=3)
for msg in ["m1", "m2", "m3", "m4"]:
    recent.append(msg)
print(list(recent))        # ['m2', 'm3', 'm4'] — 'm1' fell off automatically

recent.appendleft("m0")     # add at the front — O(1); drops 'm4'

5 · Priority queue & heapq advanced

A queue serves people in arrival order — but a hospital emergency room can't work that way. A patient with a heart attack jumps ahead of someone with a sprained wrist, no matter who arrived first. That's a priority queue: it doesn't serve first-in, it serves most-important-first. By universal convention we treat the smallest number as highest priority (priority 1 beats priority 5), so "remove the most important" becomes "remove the minimum."

The obvious implementations are both bad, and the tension is worth feeling. Keep the list sorted so the min is always at the front? Then inserting costs O(n) to slot into place. Keep it unsorted for cheap inserts? Then finding the min costs O(n) every time. You can't win with a flat list — one operation is always slow.

The resolution is a cleverer shape called a binary heap (you'll build one from scratch in D4; here we just use it). A heap is a tree kept in "loose" order — each parent is smaller than its children, but siblings are unsorted — which is just enough structure to make both push and pop O(log n) while peeking the minimum stays O(1). Python ships this as the heapq module, and here's the quirk that trips everyone: it doesn't give you a Heap class — it gives you functions (heappush, heappop) that operate on an ordinary list you maintain, with the minimum always sitting at heap[0]. It's a top-k engine: exactly what RAG uses to keep the best-scoring chunks.

pythonimport heapq

# A min-heap. Push (priority, item); smallest priority pops first.
pq = []
heapq.heappush(pq, (2, "reindex"))
heapq.heappush(pq, (1, "page oncall"))     # higher priority = lower number
heapq.heappush(pq, (3, "cleanup"))
print(heapq.heappop(pq))       # (1, 'page oncall')

# Top-k largest scores WITHOUT sorting everything: O(n log k)
scores = [(0.91, "docA"), (0.55, "docB"), (0.73, "docC"), (0.88, "docD")]
top2 = heapq.nlargest(2, scores)        # [(0.91,'docA'), (0.88,'docD')]

Why a heap and not just sorted()[:k]? Sorting all n items is O(n log n). If you only need the top k, a size-k heap does it in O(n log k) — a big win when n is millions and k is 10, and it never holds more than k items in memory.

6 · Singly linked list — from scratch intermediate → advanced

Everything so far has been array-flavoured — items sitting side by side in memory. Now we meet the opposite philosophy, and it's worth slowing down for, because the pointer-relinking idea you learn here is the foundation of trees (D4) and graphs (D5). Get it now and those chapters feel easy; skip it and they feel like magic.

Picture a treasure hunt. You don't get a map of all the locations — you get one clue, and that clue tells you where the next clue is, which points to the next, and so on. A linked list is exactly that: each element lives in a little box called a node that holds two things — a value, and a pointer ("the address of the next node"). The list itself is just a reference to the first node (the "head"); you follow the pointers to reach the rest.

This design makes a deliberate trade, and understanding the trade is the point. Because the nodes are scattered in memory rather than contiguous, you lose the array's superpower: there's no O(1) jump to element i — to reach the 5th node you must walk the 4 clues before it (O(n)). But you gain something arrays are bad at: inserting or removing at a node you already hold is O(1) — you just rewrite a couple of pointers ("skip me, point to the next one"), with none of the mass-shifting that makes list.insert(0, x) slow. Arrays: instant to read, slow to restructure. Linked lists: slow to read, instant to restructure. The lab builds one node-by-node so the pointer surgery is concrete.

pythonclass Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt            # pointer to the next node (or None)

class LinkedList:
    def __init__(self):
        self.head = None
    def push_front(self, value):     # insert at head — O(1)
        self.head = Node(value, self.head)
    def __iter__(self):              # walk head -> tail — O(n)
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next
    def find(self, value):           # O(n) — no random access
        for v in self:
            if v == value: return True
        return False

# Reverse a linked list in place — the canonical pointer-juggling problem
def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next         # 1. remember the rest
        cur.next = prev        # 2. flip this node's pointer backwards
        prev = cur             # 3. advance prev
        cur = nxt              # 4. advance cur
    return prev                # new head — O(n) time, O(1) space

7 · Doubly linked list advanced

The singly linked list has one frustrating blind spot. Its treasure-hunt clues only point forward — so if you're standing on a node and want to delete it, you're stuck: to relink the list you need the node before it, and there's no way back. Your only option is to restart from the head and walk until you find the predecessor — O(n), just to remove a node you were already touching.

A doubly linked list fixes this by giving every node a second pointer, prev, alongside next. Now each node knows both its neighbours — it's a chain you can walk in either direction. The payoff is the operation the singly list couldn't do: remove a node in O(1) when you already hold it, because you can reach its predecessor instantly (node.prev) and splice it out. That single capability is why the doubly linked list is the secret ingredient in the LRU cache at the end of this chapter.

One practical craft note that this section teaches: real doubly-linked-list code is riddled with "what if it's the first node? the last? the only one?" edge cases. The professional trick is a sentinel — a permanent dummy head/tail node that never holds data but guarantees every real node always has a neighbour on both sides. Suddenly there are no special cases, because there are no true "ends" to trip over. It's a small idea that makes the code dramatically cleaner, and you'll see it pay off in the lab.

pythonclass DNode:
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = DNode()        # sentinels — never hold real data
        self.tail = DNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    def add_back(self, node):      # insert before tail — O(1)
        last = self.tail.prev
        last.next = node; node.prev = last
        node.next = self.tail; self.tail.prev = node
    def remove(self, node):        # unlink a held node — O(1)
        node.prev.next = node.next
        node.next.prev = node.prev

8 · Cycle detection — Floyd's tortoise & hare advanced

Here's a subtle bug that can hang a program forever: a linked list whose last node points back into itself instead of ending. Walk it looking for the end and you loop infinitely. So how do you detect a loop before it traps you? This is a famous puzzle with a genuinely beautiful answer.

The obvious solution works but is wasteful: keep a set of every node you've visited; if you ever see one twice, there's a cycle. Correct — but it costs O(n) extra memory to store all those nodes. Can we do it with no extra memory?

Floyd's algorithm says yes, using an idea from a running track. Put two runners on the list: a slow tortoise that steps one node at a time, and a fast hare that leaps two. If the list is straight, the hare simply reaches the end — no cycle. But if the list loops, both runners get trapped going around the same loop — and because the hare gains exactly one step on the tortoise per move, it inevitably catches up from behind and they land on the same node. Two runners meeting means there's a cycle. It's O(n) time but O(1) space — the classic "trade cleverness for memory" result, and a favourite interview question precisely because the two-speed insight is so hard to invent on the spot and so satisfying once seen.

pythondef has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # 1 step
        fast = fast.next.next       # 2 steps
        if slow is fast:            # they met -> cycle
            return True
    return False                   # fast reached the end -> no cycle

9 · Expert — an O(1) LRU cache expert advanced

This is the capstone that ties the whole chapter together — and it's one of the most-asked hard interview questions in the industry, because solving it proves you can combine structures rather than just recite them. The problem: build a cache that holds only the N most recently used items, evicting the least-recently-used one when it's full — with both "look something up" and "store something" running in O(1). Think of your phone's recent-apps list: fixed size, most-recent floats to the front, the stalest drops off the end.

Why it's hard: no single structure can do both jobs. You need two capabilities at once — instant lookup by key ("is 'user_42' cached?") and instant reordering by recency ("mark this the newest, drop the oldest"). A hash map nails the first but has no notion of order. A doubly linked list nails the second (move-to-front and drop-the-tail are the O(1) relink operations from §7) but can't find a key without scanning. Each structure is missing exactly what the other has.

The insight is to run them together, pointing at the same nodes. The hash map maps key → the node, giving O(1) "where is it?"; the doubly linked list holds those same nodes in recency order, giving O(1) "make it newest / evict the oldest." A lookup hits the map to find the node, then splices it to the front of the list. Both structures update in constant time, so the whole cache is O(1). This "two structures covering each other's weakness" pattern is exactly how Python's own functools.lru_cache and OrderedDict work under the hood — you're about to build the real thing.

class _Any:
    '''stands in for any undefined demo value; supports call/attr/index/
    iteration and basic arithmetic (as 0.7) so demo snippets run.'''
    def __call__(self, *a, **k): return _Any()
    def __getattr__(self, k): return _Any()
    def __getitem__(self, k): return _Any()
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __contains__(self, o): return True
    def __enter__(self, *a): return _Any()
    def __exit__(self, *a): return False
    def __float__(self): return 0.7
    def __int__(self): return 1
    def __lt__(self, o): return True
    def __gt__(self, o): return False
    def __le__(self, o): return True
    def __ge__(self, o): return False
    def __add__(self, o): return o
    def __radd__(self, o): return o
    def __bool__(self): return True
    def __repr__(self): return 'demo'
    def __str__(self): return 'demo'
def DNode(*a, **k):  # demo stub
    return _Any()
def DoublyLinkedList(*a, **k):  # demo stub
    return _Any()

pythonclass LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                       # key -> DNode  (O(1) find)
        self.dll = DoublyLinkedList()        # recency order (front=old, back=new)

    def get(self, key):
        if key not in self.map:
            return None
        node = self.map[key]
        self.dll.remove(node)               # pull it out ...
        self.dll.add_back(node)             # ... and mark most-recent — O(1)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self.dll.remove(self.map[key])
        node = DNode(key, value)
        self.map[key] = node
        self.dll.add_back(node)             # most-recent
        if len(self.map) > self.cap:         # over capacity -> evict oldest
            oldest = self.dll.head.next     # front = least recently used
            self.dll.remove(oldest)
            del self.map[oldest.key]

# In real code you rarely hand-roll this — the stdlib gives you memoization:
from functools import lru_cache
@lru_cache(maxsize=256)
def embed(text):                  # repeated calls with the same text are free
    ...                             # (see P4/P5 — this IS an LRU cache under the hood)

Exercises advanced

🎯 Interview practice interview

The interview questions this topic gets asked — worked, with code. For the full pattern catalog see D8 · Big Tech DSA patterns.

pythondef is_valid(s):
    pairs = {")":"(", "]":"[", "}":"{"}
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif not stack or stack.pop() != pairs[c]:
            return False
    return not stack

pythonclass MinStack:
    def __init__(self):
        self.st = []; self.mins = []
    def push(self, x):
        self.st.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))
    def pop(self): self.mins.pop(); return self.st.pop()
    def get_min(self): return self.mins[-1]

Checkpoint advanced

from collections import deque

stack = []
for x in "ABC": stack.append(x)
print([stack.pop() for _ in range(3)])   # ['C','B','A']  LIFO

queue = deque()
for x in "ABC": queue.append(x)
print([queue.popleft() for _ in range(3)])  # ['A','B','C'] FIFO

def is_valid(s):                       # O(n) time, O(n) space
    match = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack or stack.pop() != match[ch]:
                return False
    return not stack                   # leftover openers = unbalanced

print(is_valid("([]{})"))   # True
print(is_valid("(]"))       # False
print(is_valid("(("))       # False

class Node:
    def __init__(self, val):
        self.val = val; self.next = None

def has_cycle(head):                   # O(n) time, O(1) space
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:               # pointers meet inside the loop
            return True
    return False

a, b, c = Node(1), Node(2), Node(3)
a.next, b.next, c.next = b, c, a       # c points back to a -> cycle
print(has_cycle(a))                    # True
c.next = None
print(has_cycle(a))                    # False

class MinStack:                        # every op O(1)
    def __init__(self):
        self.stack = []                # (value, min-so-far)
    def push(self, x):
        cur_min = x if not self.stack else min(x, self.stack[-1][1])
        self.stack.append((x, cur_min))
    def pop(self):
        return self.stack.pop()[0]
    def top(self):
        return self.stack[-1][0]
    def get_min(self):
        return self.stack[-1][1]

s = MinStack()
for x in (5, 2, 7, 1): s.push(x)
print(s.get_min())   # 1
s.pop()
print(s.get_min())   # 2

import heapq, itertools

class PriorityQueue:
    def __init__(self):
        self.h = []; self.counter = itertools.count()
    def push(self, item, priority):
        heapq.heappush(self.h, (priority, next(self.counter), item))
    def pop(self):                     # O(log n)
        return heapq.heappop(self.h)[2]

pq = PriorityQueue()
pq.push("email", 3); pq.push("page", 1); pq.push("log", 3)
print(pq.pop(), pq.pop(), pq.pop())    # page email log

from collections import OrderedDict

class LRUCache:                        # get/put both O(1)
    def __init__(self, capacity):
        self.cap = capacity
        self.d = OrderedDict()
    def get(self, key):
        if key not in self.d:
            return -1
        self.d.move_to_end(key)        # mark most-recently-used
        return self.d[key]
    def put(self, key, value):
        if key in self.d:
            self.d.move_to_end(key)
        self.d[key] = value
        if len(self.d) > self.cap:
            self.d.popitem(last=False) # evict least-recently-used

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
print(c.get(1))   # 1  (now 2 is LRU)
c.put(3, 3)       # evicts key 2
print(c.get(2))   # -1

Knowledge check check yourself