Data Structures: Stacks, Queues & Hash Tables

The shape decides the operation, not the other way round

A data structure is a contract between how data is arranged in memory and what operations that arrangement makes cheap or expensive. There is no free structure — every design trades one operation's speed for another's, and choosing the right structure is really choosing which operations your program does most and letting it pay the smallest possible price for those, at the expense of the ones it rarely needs.

Stacks and queues: two disciplines on the same sequence

A stack only ever adds or removes from one end — last in, first out (LIFO). It is the natural structure for anything with nested scope: the call stack that tracks which function returns to which, undo history, matching parentheses, depth-first traversal. A queue adds at one end and removes from the other — first in, first out (FIFO) — which is what you want for anything processed in arrival order: task scheduling, print queues, and breadth-first search, where the frontier must be explored in the order it was discovered.

stack: push(x), pop()      → both O(1), always at the same end (top)
queue: enqueue(x), dequeue() → both O(1), at opposite ends (back, front)

Both are typically built on an array (with a moving head/tail index,
or a ring buffer) or a linked list — either backing store gives O(1)
push/pop as long as you never need to reach into the middle.

live demo · nodes linking and relinking as items are inserted● LIVE

Arrays versus linked lists: contiguous memory versus pointers

An array stores elements contiguously, so any index can be reached directly by arithmetic — O(1) random access — but inserting or deleting in the middle means shifting every following element, O(n). A linked list stores each element in its own node with a pointer to the next, so inserting or deleting is O(1) once you already hold a reference to the right spot, but reaching any given element means walking the chain from the head, O(n), and each node is a separate memory allocation, scattered across RAM rather than packed together. That scattering matters more in practice than the Big-O suggests: modern CPUs fetch memory in cache-line-sized chunks, so an array's contiguous layout means many elements arrive "for free" in one fetch, while a linked list's pointer-chasing triggers a fresh, slow memory fetch almost every step — which is why arrays usually win real-world benchmarks even when the linked list has the same asymptotic complexity.

Hash tables: turning search into arithmetic

Searching an unsorted array for a value takes O(n) — you must check every element in the worst case. A hash table sidesteps searching almost entirely: a hash function turns a key into a number, that number is reduced modulo the table's size to pick a bucket, and the value is stored (or looked up) directly at that bucket. With a good hash function spreading keys evenly, insertion, lookup and deletion are all O(1) on average. Collisions — two different keys landing in the same bucket — are handled either by chaining (each bucket holds a small linked list) or open addressing (probe forward to the next free slot); either way, performance degrades toward O(n) only if the table gets too full, which is why a well-implemented hash table automatically resizes and re-hashes once its load factor crosses a threshold, typically around 0.7.

Choosing between them

The practical rule is to name your program's dominant operation and pick the structure that makes it O(1) or close to it: need order-preserving nested undo — a stack; need arrival-order processing — a queue; need frequent middle insertion with an existing reference to the spot — a linked list; need fast key lookup with no ordering requirement — a hash table; need both fast lookup and sorted order — reach for a balanced tree instead, trading O(1) lookup for O(log n) in exchange for keeping everything sorted.

Frequently asked questions

Why is a hash table lookup O(1) if it still has to search inside a bucket?

O(1) here is an average-case, amortised claim, not a worst case. With a good hash function and a load factor kept below roughly 0.75 by resizing, each bucket holds a small constant number of entries on average, so scanning one bucket takes constant time on average even though a single pathological bucket could in theory hold everything.

When would I choose a linked list over an array?

When you need frequent insertions or deletions in the middle of a sequence and already hold a reference to the relevant node — that is O(1) for a linked list versus O(n) for an array, which must shift every following element. Arrays win almost everywhere else, because contiguous memory means far better cache locality and O(1) random access, which a linked list cannot offer at all.

What is the practical difference between a stack and a queue?

Which end you remove from. A stack is LIFO — last in, first out — so it naturally models nested, unwinding work like function calls, undo history or matching brackets. A queue is FIFO — first in, first out — so it models anything processed in arrival order, like a print spooler, a breadth-first search frontier, or a task scheduler.

Try it live

Everything above runs in your browser — open Data Structures and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Data Structures simulation

Data Structures: The Shapes That Decide Your Program's Speed