Linked Lists, Stacks & Queues: Who Goes Next?
What you'll learn
- How a linked list stores items as nodes joined by pointers, and when that beats an array
- The two classic rules for "who goes next": the stack (last in, first out) and the queue (first in, first out)
- Where they hide in real software: undo, the call stack, bracket matching, expression evaluation, job queues and rate limiters
- How to get O(1) operations in practice: a dynamic array as a stack,
collections.dequeas a queue, and the ring buffer - You will write: a bracket checker, a text editor whose cursor walks a linked list, and a rate limiter
Plates, a bakery line and a treasure hunt
A pile of plates in a kitchen: you put a clean plate on top, and you take the top plate when you need one. The plate you added last is the first one used. That is a stack, and it is exactly how the undo button works: the last change you made is the first one undone.
The line at a bakery is the opposite. The first customer to arrive is the first one served, and newcomers join at the back. That is a queue: print jobs, support tickets and requests waiting for a busy server all line up this way, because it is fair.
A treasure hunt is a chain of clues. Each clue tells you where the next one is hidden. You cannot jump straight to clue number 7: you must follow the chain from the first clue. But adding a new clue in the middle is easy: write one new note and change where the previous clue points. That is a linked list.
Stacks and queues are rules about the order in which items leave. Arrays and linked lists are two ways to store items. This lesson connects the two.
Linked lists
A singly linked list is a chain of nodes. Each node holds a value and a pointer (a reference) to the next node. The list itself only remembers the first node, the head; the last node points to nothing (None, null).
head -> [3] -> [7] -> [9] -> None
The nodes can live anywhere in memory, so there is no "start + i x size" formula as in an array. That decides the costs:
- Read the k-th item: O(k), up to O(n): you walk from the head, one pointer at a time
- Insert or delete at the head: O(1)
- Insert or delete right after a node you already hold: O(1): change one or two pointers, nothing shifts
- Search for a value: O(n)
- Append at the end: O(1) only if you also keep a pointer to the last node (the tail)
insert 8 after 7:
before: [3] -> [7] -------> [9]
after: [3] -> [7] -> [8] -> [9] two pointers changed, nothing moved
A doubly linked list gives every node a prev pointer as well. Now you can walk backwards, and delete a node you hold in O(1) because you can reach both neighbours. Java's LinkedList and C++'s std::list are doubly linked; C++'s std::forward_list is singly linked. Python's list is not a linked list: it is a dynamic array.
Two tricks make linked-list code much less buggy:
- A sentinel (dummy) node that sits before the first real node. The list is never truly empty, so "insert at the front" and "insert in the middle" become the same code.
- Draw the arrows before you change them. The classic exercise, reversing a list in place, needs three pointers:
def reverse(head):
prev = None
cur = head
while cur is not None:
nxt = cur.next # remember the rest of the list
cur.next = prev # turn this arrow around
prev = cur
cur = nxt
return prev # the old tail is the new head
Array or linked list? In practice an array is usually faster for scanning, because its items sit next to each other and the CPU cache loads them in blocks. Linked lists win when you keep references to positions and insert or delete there all the time: the cursor of a text editor, the "least recently used" order of a cache (a hash map plus a doubly linked list), or the free blocks of a memory allocator.
Every edit changes one or two pointers and never moves the other nodes. Reading the item at index 2 has to walk there node by node. Reversal turns each arrow around once, so it is O(n) time and O(1) extra space.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def show(head):
parts = []
while head is not None:
parts.append(str(head.value))
head = head.next
return " -> ".join(parts + ["None"])
def get(head, k): # O(k): there is no shortcut to the k-th node
for _ in range(k):
head = head.next
return head.value
def reverse(head):
prev, cur = None, head
while cur is not None:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
return prev
# Build 3 -> 7 -> 9 by pushing at the front: O(1) each time
head = None
for v in (9, 7, 3):
head = Node(v, head)
print("built: ", show(head))
seven = head.next
seven.next = Node(8, seven.next) # insert after a node we hold: O(1)
print("insert 8: ", show(head))
head.next = head.next.next # unlink the 7: one pointer change
print("delete 7: ", show(head))
print("item at 2: ", get(head, 2))
head = reverse(head)
print("reversed: ", show(head))
Stacks: last in, first out
A stack offers three operations, all O(1): push (put on top), pop (take the top off) and peek (look at the top). You never touch the middle.
Implementing one is easy. Use the end of a dynamic array: Python list.append / list.pop(), JavaScript push / pop, C++ std::stack or std::vector. In Java, use ArrayDeque: its documentation notes it is likely to be faster than the legacy Stack class when used as a stack. The head of a linked list works too.
Where stacks appear:
- Undo and redo: two stacks. Undo pops from "done" and pushes onto "undone"; redo does the reverse; any new action clears "undone".
- The call stack: every function call pushes a frame with its local variables, every
returnpops it. That is why the most recent call finishes first, and why runaway recursion ends in a stack overflow (the Recursion & Dynamic Programming lesson, later in this course). - Depth-first search keeps the vertices still to explore on a stack (the Trees & Graphs lesson, later in this course, puts it to work).
- Bracket matching and expression evaluation, below.
Bracket matching. Push every opening bracket. For every closing bracket, the top of the stack must be its partner: pop it. Watch the stack for {[()]}:
read { push stack: {
read [ push stack: { [
read ( push stack: { [ (
read ) top is ( pop -> stack: { [
read ] top is [ pop -> stack: {
read } top is { pop -> stack: (empty) => balanced
There are exactly three ways to fail: a closing bracket that does not match the top, a closing bracket when the stack is empty, and opening brackets left over at the end. Counting brackets is not enough: ([)] has two of each but is wrong.
Expression evaluation. In postfix notation, also called Reverse Polish Notation (RPN), the operator comes after its operands: 3 4 + 2 * means (3 + 4) x 2. A stack evaluates it in one pass: a number is pushed; an operator pops two values (the first pop is the right operand), applies itself and pushes the result. No parentheses and no precedence rules are needed. The Java Virtual Machine executes bytecode the same way on an operand stack (the JVM specification, section 2.6.2: iadd pops two ints and pushes their sum), and Dijkstra's shunting-yard algorithm uses a stack of operators to turn ordinary infix expressions into postfix.
3 4 + 2 *
push 3 [3]
push 4 [3, 4]
+ pop 4, 3 [7]
push 2 [7, 2]
* pop 2, 7 [14] -> 14
Lab exercise 1
PythonGraded in Code LabCheck the brackets the way a code editor does. Read one line of text. It may contain the brackets (), [], {} and any other characters, which you ignore.
Output: OK if every bracket is matched. Otherwise the 1-based position of the first problem:
- a closing bracket that does not match the most recent unclosed opening bracket, or that arrives when nothing is open: print its position;
- if the line ends while brackets are still open: print the position of the earliest (leftmost) bracket that was never closed.
Examples: print(a[i] + {b: (c)}) prints OK. foo(bar[i) prints 10: the ) at position 10 arrives while [ is the most recent open bracket. while (x[i] { prints 7: both ( (position 7) and { (position 13) stay open, and the earliest is reported.
Keep a stack of (bracket, position) pairs.
- Balanced code with other characters
- The example: wrong closing bracket
- A closing bracket with nothing open
- Never closed: report the earliest
- Empty line
- 6,000 nested brackets, wrong at the very end
Example run
- Input
print(a[i] + {b: (c)})- Expected output
OK
import sys
line = sys.stdin.readline().rstrip("\r\n")
pairs = {")": "(", "]": "[", "}": "{"}
# TODO: check the brackets with a stack.
# 1. For every character (enumerate(line, start=1) gives 1-based positions):
# an opening bracket -> push (bracket, position);
# a closing bracket -> if the stack is empty or its top is not pairs[ch], the answer is this position;
# otherwise pop.
# 2. If the line ends with brackets still open, the answer is the position at the BOTTOM of the stack.
answer = "OK"More lines in Code Lab: 1
Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.
JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.
Queues: first in, first out
A queue adds at the back (enqueue) and removes from the front (dequeue), both in O(1) when it is implemented well. A deque (double-ended queue) allows both operations at both ends.
The classic trap. Removing the first item of a dynamic array shifts every other item one place left: O(n) per dequeue, O(n²) for a whole run. The Python documentation says it plainly: lists "incur O(n) memory movement costs for pop(0) and insert(0, v)", while collections.deque appends and pops at either end in approximately O(1). JavaScript's Array.prototype.shift is specified (ECMAScript) as moving every remaining element down one index, so treat it as O(n) too. What to use instead:
- Python:
collections.dequewithappendandpopleft - Java:
ArrayDequewithofferandpoll - C++:
std::queue(built onstd::deque) - JavaScript or Go: an array plus a head index that moves forward, or a ring buffer
The ring buffer (circular buffer) is the standard array implementation. Keep a fixed array, the index of the front item (head) and the number of items (size). The next free slot is (head + size) % capacity: when the back reaches the end of the array it wraps around to index 0. Nothing ever shifts.
capacity 5: enqueue A B C D, dequeue twice (A, B), enqueue E F
index: 0 1 2 3 4
slot: [ F | . | C | D | E ]
^ ^
| head = 2: C leaves next
F wrapped around to index 0; the next free slot is (2 + 4) % 5 = 1
When the buffer is full you either refuse new items (fixed-size buffers in keyboards, audio and network devices do that) or grow: copy the items, in queue order, into an array twice as large. Growing now and then keeps enqueue at O(1) amortised, like appending to a dynamic array.
Two stacks make a queue. Push new items onto an in stack. To dequeue, pop from an out stack; only when out is empty, move everything from in to out (which reverses the order). A single dequeue can cost O(n), but every item is moved at most once, so a sequence of n operations costs O(n) in total: O(1) amortised per operation.
Where queues appear: print and job queues, message queues between services, the run queue of an operating system's round-robin scheduler, packets waiting in a router, keyboard input buffers, and breadth-first search (Trees & Graphs), which visits vertices in the order it discovered them.
E and F land at indexes 0 and 1 while C and D are still at 2 and 3: the queue wraps around instead of shifting. When G arrives the buffer is full, so it grows and the items are copied in queue order. The undo part shows the two-stack design: undo moves a word from one stack to the other, redo moves it back.
// A queue on a ring buffer: O(1) enqueue and dequeue, nothing ever shifts
class RingQueue {
constructor(capacity = 4) {
this.buf = new Array(capacity).fill(null);
this.head = 0; // index of the front item
this.size = 0;
}
enqueue(x) {
if (this.size === this.buf.length) this.grow();
this.buf[(this.head + this.size) % this.buf.length] = x;
this.size++;
}
dequeue() {
if (this.size === 0) return undefined;
const x = this.buf[this.head];
this.buf[this.head] = null;
this.head = (this.head + 1) % this.buf.length;
this.size--;
return x;
}
grow() { // copy the items in queue order into an array twice as large
const bigger = new Array(this.buf.length * 2).fill(null);
for (let i = 0; i < this.size; i++) bigger[i] = this.buf[(this.head + i) % this.buf.length];
this.buf = bigger;
this.head = 0;
}
}
const slots = (q) => q.buf.map((x) => x ?? ".").join(" ");
const q = new RingQueue(4);
for (const job of ["A", "B", "C"]) q.enqueue(job);
console.log("served:", q.dequeue(), q.dequeue());
for (const job of ["D", "E", "F"]) q.enqueue(job); // E and F wrap around to the front of the array
console.log("slots:", slots(q), "| head =", q.head);
q.enqueue("G"); // full: grow to 8 slots
console.log("after growing:", slots(q));
const order = [];
while (q.size > 0) order.push(q.dequeue());
console.log("served in order:", order.join(" "));
// Undo and redo are two stacks
const done = [];
const undone = [];
const type = (word) => { done.push(word); undone.length = 0; }; // a new action clears redo
const undo = () => { if (done.length) undone.push(done.pop()); };
const redo = () => { if (undone.length) done.push(undone.pop()); };
type("Hello"); type("big"); type("world");
undo(); undo(); redo();
console.log("text:", done.join(" "), "| can still redo:", undone.join(" "));
Lab exercise 2
CGraded in Code LabA text editor with a cursor. Store the text in a doubly linked list of characters, so that every edit at the cursor costs O(1) however long the text is. The cursor sits between characters and starts after the last character.
Input: the first line is the starting text (1 to 10,000 lowercase letters). The second line has m, the number of commands. Then m lines, each one of:
L: move the cursor one character left (nothing happens at the start)R: move the cursor one character right (nothing happens at the end)B: delete the character just left of the cursor (nothing happens at the start)I c: insert the lowercase lettercjust left of the cursor (the cursor ends up after it)
Output: the final text on one line (an empty line if everything was deleted).
Example: text abc and the commands L, L, B, I x, R, I y:
abc| -> L -> ab|c -> L -> a|bc -> B -> |bc -> I x -> x|bc -> R -> xb|c -> I y -> xby|c
prints xbyc.
The nodes are array slots: ch[i], prv[i] and nxt[i] (-1 means "no node"). Slot 0 is a sentinel before the first letter, and cursor is the node just left of the cursor (0 when the cursor is at the start). The starter already builds the list; you write the four commands.
- The example
- Edits at both ends, moving past them
- Backspace, then insert and move in the middle
- Delete everything
- Moving alone changes nothing
- 6,400 commands
Example run
- Input
abc 6 L L B I x R I y
- Expected output
xbyc
#include <stdio.h>
#include <string.h>
#define MAXN 200005 /* starting letters + one node per insert */
char text[MAXN];
char ch[MAXN];
int prv[MAXN], nxt[MAXN]; /* -1 means "no node" */
int main(void) {
int m = 0;
if (scanf("%10005s", text) != 1) return 0;More lines in Code Lab: 35
Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.
JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.
A queue at work: the rate limiter
Public APIs protect themselves with rate limits: "at most 100 requests per minute per user". A server that refuses a request for that reason answers with HTTP status 429 Too Many Requests, defined in RFC 6585.
One precise way to enforce "at most L requests in any window of W seconds" is the sliding log: remember the timestamps of the requests you allowed, oldest first. That is a queue, because timestamps arrive in order and leave in the same order:
- A request arrives at time
t. - Dequeue every timestamp
swiths <= t - W: those requests have left the window(t - W, t]. - If fewer than
Ltimestamps remain, allow the request and enqueuet. Otherwise deny it, and do not record it: a refused request should not use up the quota.
L = 2, W = 10 window = (t - 10, t]
t = 1 queue [] -> allow queue [1]
t = 2 queue [1] -> allow queue [1, 2]
t = 3 queue [1, 2] -> deny (2 requests already in (-7, 3])
t = 11 drop 1 -> allow queue [2, 11]
t = 12 drop 2 -> allow queue [11, 12]
Each timestamp is enqueued once and dequeued at most once, so n requests cost O(n) in total even though step 2 is a loop. The queue never holds more than L items. (Production systems often use cheaper approximations such as fixed windows or token buckets; the sliding log is the exact version.)
Lab exercise 3
GoGraded in Code LabBuild a rate limiter. An API allows at most L requests in any window of W seconds. Requests arrive at whole-second timestamps that never decrease. A request at time t is allowed if fewer than L allowed requests have a timestamp s with t - W < s <= t; otherwise it is denied. A denied request does not count against later ones.
Input: the first line has L W n (all at least 1). The second line has the n timestamps.
Output: n lines, each ALLOW or DENY.
Example: input
2 10 6
1 2 3 11 12 21
prints ALLOW, ALLOW, DENY, ALLOW, ALLOW, ALLOW (one per line), as traced in the lesson; at 21 the 11 leaves the window.
Keep the timestamps of the allowed requests in a queue: a slice plus a head index (dequeue is head++: nothing is copied). Before deciding about t, dequeue every timestamp <= t - W.
- The example
- One request per second
- Denied requests do not count
- A burst in the same second
- A single request
- 4,000 requests, 20 per 50 seconds
Example run
- Input
2 10 6 1 2 3 11 12 21
- Expected output
ALLOW ALLOW DENY ALLOW ALLOW ALLOW
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()More lines in Code Lab: 15
Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.
JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.
Question 1 of 5
You hold a reference to a node in the middle of a doubly linked list. What does it cost to delete that node?
Question 2 of 5
Why is list.pop(0) a poor way to dequeue in Python?
Question 3 of 5
What is the value of the postfix (RPN) expression 5 1 2 + 4 * + 3 - ?
Question 4 of 5
A bracket checker reads ( [ ) ]. What does it report?
Question 5 of 5
A queue built from two stacks moves items from the in-stack to the out-stack only when the out-stack is empty. What does a dequeue cost?
Summary
- A linked list is a chain of nodes and pointers: O(1) insert and delete at a node you hold (or at the head), but O(n) to reach the k-th item. A doubly linked list can also delete a held node and walk backwards. A sentinel node removes edge cases.
- A stack is last in, first out: push, pop and peek in O(1) at the end of a dynamic array. It powers undo, the call stack, DFS, bracket matching and postfix evaluation.
- A queue is first in, first out. Never dequeue by shifting an array: use
collections.deque,ArrayDeque, a head index or a ring buffer. Two stacks also make a queue with O(1) amortised operations. - Queues order work fairly (job queues, schedulers, BFS) and keep sliding records, like the exact rate limiter that dequeues expired timestamps.
Practice next: detect a cycle in a linked list with a slow and a fast pointer, implement a stack that also returns its minimum in O(1), and compute the maximum of every window of k numbers with a deque. Then continue with Sorting & Binary Search.
Practice
Reading is not learning until you run something. Pick one.
Graded lab exercises
- Lab exercise 1PythonNot passed yet Try in Code Lab
- Lab exercise 2CNot passed yet Try in Code Lab
- Lab exercise 3GoNot passed yet Try in Code Lab