The formula
A data structure isn't one equation — it's a table of costs. The "formula" is the
cost of each operation, written in big-O notation, which says how the work grows
as the number of stored items n grows.
Structure access[i] search insert (end) insert (middle) delete notes
Array O(1) O(n) O(1)* O(n) O(n) contiguous, index math
Dynamic array O(1) O(n) O(1) amort O(n) O(n) doubles when full
Linked list O(n) O(n) O(1)** O(1)** O(1)** ** if you hold the node
Stack (LIFO) — — O(1) push — O(1) pop last in, first out
Queue (FIFO) — — O(1) enq — O(1) deq first in, first out
Binary heap O(1) peek O(n) O(log n) O(log n) O(log n) priority queue
* only while spare capacity remains; a full fixed array can't grow at all
** rewiring the pointers is O(1) — walking to the node is not (see below)
Reading it: O(1) means the cost is flat — a million items or ten, same work.
O(log n) means the cost is the number of times you can halve n. O(n) means
you touch everything.
heap array indexing (root at index 1):
parent(i) = floor(i / 2)
left(i) = 2·i
right(i) = 2·i + 1
Reading it: a heap is a tree, but you store it in a flat array and find any node's parent or children with integer arithmetic — no pointers.
ring buffer next index: next = (idx + 1) mod capacity
Reading it: a queue in a fixed array that wraps around, so you never move data or allocate — the write pointer just rolls over from the last slot back to the first.
Where you meet it
The data logger on the test stand. Sensors push samples faster than the disk writer pulls them. You put a ring buffer (a queue in a fixed array) between them. Producer writes to the head, consumer reads from the tail, both
O(1), no allocation in the hot path. Pick a linked list here instead and every sample triggers a heap allocation — the one thing that will make you miss a deadline and drop data.Alarm handling in the control room. A priority queue (binary heap) holds pending events sorted by severity, not arrival order. The most critical alarm is always at the root, readable in
O(1); inserting a new one and pulling the top both costO(log n). That's how a scheduler always services the hottest event next without re-sorting the whole list.The parser reading your instrument's command file. Nested parentheses,
BEGIN/ENDblocks, function calls — all of it runs on a stack. Push on the way in, pop on the way out. Every recursive routine you've ever written uses the CPU's call stack for exactly this.A design-review argument over a lookup table. Someone stored 50,000 calibration points in a plain array and does a linear search on every reading:
O(n), and it's the reason the loop can't keep up at 10 kHz. Sort it once and binary-search (O(log n)), or drop it in a hash table (O(1)average), and the bottleneck disappears.
How it works
The whole game is a trade. There is no container that is cheap at everything, so you decide which operations happen in your inner loop and pay for those, letting the rare operations be slow.
An array wins when you know the index. The address is just
base + i·element_size, one multiply and one add, so element 900,000 costs
exactly what element 3 costs. It loses when you don't know where the thing is
(you scan) or when you need to insert in the middle (you shift everything after
it). Arrays are also cache-friendly: contiguous memory means the CPU prefetcher
guesses right and the next element is already in cache. This is why a "slower"
array often beats a "faster" linked list in practice — the big-O table doesn't
show cache misses, and a cache miss costs a hundred-plus cycles.
A linked list flips it. Each node holds its data and a pointer to the next
node, scattered wherever the allocator put them. Inserting or deleting is O(1)
— rewire two pointers — but only if you already hold the node. Finding the node
is O(n) because you have to walk the chain from the front. The classic mistake
is quoting linked-list insertion as O(1) and forgetting the O(n) walk to
reach the insertion point. And every hop follows a pointer to a random address,
which is a likely cache miss, so a linked-list traversal can be an order of
magnitude slower than an array scan of the same length.
Stacks and queues are disciplines, not really structures — you can build
either on an array or a linked list. A stack is last-in-first-out: push and pop
happen at the same end. A queue is first-in-first-out: you add at one end, remove
from the other. The gotcha with a naive array-backed queue is that removing from
the front shifts everything, making it O(n). The fix is the ring buffer: two
indices that wrap with mod capacity, so nothing ever moves. The cost is a fixed
size — when the buffer fills, you either block, overwrite the oldest sample, or
drop the newest, and you have to decide which on purpose. A logger that
silently overwrites is fine for a scrolling display and a disaster for a
qualification test record.
A binary heap is the priority queue. It's a tree kept in an array, with one
rule: every parent is smaller (or larger) than its children. That rule is weaker
than fully sorted, which is exactly why it's fast — you don't pay to sort things
you'll never look at. The top is always the min or max, free to read. Insert puts
the item at the end and "sifts up" swapping with its parent until the rule holds;
extract pulls the root, moves the last item up top, and "sifts down." Both walk
the height of the tree, which is log₂ n. Here's the punchline that makes heaps
worth knowing: a heap of a billion items is only about 30 levels deep, so an
insert or extract touches roughly 30 elements. A million items is about 20. The
depth barely moves as the data explodes — that's what O(log n) buys you.
The limit of validity on all of this: big-O describes growth, not absolute
speed. For small n — a few dozen items — a linear array scan beats a hash
table, a heap, and a balanced tree, because the constant factors and cache
behavior dominate and log n versus n doesn't matter yet. The engineer's
mistake is reaching for a fancy structure when a flat array would have been
faster and simpler. Measure your real n before you optimize its shape.
History
The ideas showed up together with the first real programming languages, because you can't run code without somewhere to keep the code's state.
The stack has a genuinely tangled origin. Klaus Samelson and Friedrich Bauer at the Technical University of Munich described a last-in-first-out store they called the Operationskeller — "operational cellar" — around 1955, filing a patent in 1957, as part of the machinery that made the ALGOL family of languages able to evaluate nested expressions and handle recursion [1][2]. The Australian philosopher Charles Hamblin worked out the same idea independently in 1954 for reverse-Polish expression evaluation [1]. Bauer received the IEEE Computer Pioneer Award in 1988 for the stack principle [1]. Underneath it all sits Alan Turing's 1936 machine and the later pushdown automaton — a finite machine plus a stack — which is precisely the theoretical object that recognizes the nested, context-free grammars real programming languages are built from [2].
The linked list came out of early artificial-intelligence work. Allen Newell, Cliff Shaw, and Herbert Simon built it in 1955–56 at RAND and Carnegie as the core structure of their Information Processing Language, IPL, which they used to write the Logic Theorist — arguably the first AI program [3][4]. They needed to grow and rearrange lists of symbols on the fly, which fixed-size arrays couldn't do, so they chained records by pointer. Newell and Simon later shared the 1975 Turing Award, and this was part of the body of work cited [4].
The binary heap and heapsort were published by J. W. J. Williams in 1964,
giving a priority queue with O(log n) insert and extract built entirely inside
a flat array — no pointers, no wasted space [5][6]. Robert Floyd followed the same
year with the O(n) bottom-up construction that builds a heap from an unsorted
array faster than inserting items one at a time [5][6]. Sixty years on, that same
array-in-a-tree trick still runs the priority queue in your scheduler.
Related tools
- /tools/adc-resolution
- /tools/snr-enob
- /tools/frequency-period
- /tools/loop-4-20ma