Data structures: arrays, lists, trees, hash tables

An algorithm works on data, and how the data is laid out decides what the algorithm can do quickly. A data structure is that layout plus the operations it supports — find, insert, delete, walk in order — each with its own cost in the big-O sense. On a real machine, the layout also decides how well the caches work, which can matter just as much.

Arrays

An array stores its elements one after another in a single block of memory. Element i lives at:

address of element i = base + i × element size

That's one multiplication and one addition, whatever i is, so indexing is O(1). x86 builds this formula right into its addressing modes: mov eax, DWORD PTR [rsi+rcx*4] reads element rcx of an int array starting at rsi, in a single instruction.

The price is rigidity. Inserting or deleting in the middle means shifting everything after it, which is O(n). A dynamic array (C++ std::vector, Python list, Rust Vec) grows by allocating a bigger block — larger by a constant factor, such as 2, or 1.5 in some implementations — and copying. Most appends then cost O(1), and the occasional copy averages out to O(1) per append — amortized O(1).

Linked lists

A linked list stores each element in its own node, with a pointer to the next one. Inserting or removing a node, once you're at the right place, is O(1): you just rewrite a couple of pointers. But finding element i means following i pointers, which is O(n).

The big-O table says little about the real cost of walking a list. The two demos below sum the same 64 numbers, first from an array, then from a linked list whose nodes are scattered through memory, one per cache line, and linked in a shuffled order — as nodes allocated at different times usually are. Both run through the same cache: 1 KB, 64-byte lines.

The array needs 4 misses for 64 elements: each 64-byte line holds 16 ints, so one miss brings in the next 15 for free. The list needs 65 misses — one per node, plus one for the head pointer — for exactly the same additions. Each node costs two accesses, reading its value and its next pointer, and they share a line, so about half the accesses hit. But every node is a new line.

It's worse on a real CPU than the counts suggest. In the array loop, the address of the next element is known in advance, so an out-of-order core and the hardware prefetcher can fetch many lines at once. In the list, the address of the next node is the value being loaded: each miss has to complete before the next one can even start. This is pointer chasing, and it serializes every memory access. That's why linked lists are often much slower than arrays in practice, even for operations where their big-O is better.

Stacks and queues

Two simple structures are defined by their access order rather than their layout:

• a stack is last in, first out: push and pop at the same end. An array with a top index does both in O(1). The call stack is exactly this, with rsp as the top index.
• a queue is first in, first out: add at the back, remove at the front. A ring buffer — an array whose front and back indexes wrap around — does both in O(1). Keyboard input, network packets and audio all flow through ring buffers.

Hash tables

A hash table finds a value by its key in O(1) on average. A hash function turns the key into a number, and that number modulo the table size gives a bucket, where the entry is stored. Different keys sometimes land in the same bucket — a collision — and there are two classic ways to handle it:

• chaining: each bucket holds a small list of entries;
• open addressing: on a collision, probe the next buckets until a free one appears. The entries stay inside one array, which is much friendlier to the cache.

The table stays fast as long as its load factor — entries divided by buckets — stays low. When it grows too high, the table allocates a bigger array and reinserts everything. Like a dynamic array's growth, that's O(n) once in a while and amortized O(1) per insert.

The worst case is real, though: if many keys hash to the same bucket, every lookup becomes O(n). Attackers can do this on purpose by sending keys chosen to collide, a hash flooding denial-of-service attack. That's why Python and Rust hash strings with SipHash, a hash function keyed with a random secret, so collisions can't be predicted.

Trees

A binary search tree keeps its keys in order: everything in a node's left subtree is smaller, everything in its right subtree is larger. A lookup goes down one path from the root, so it costs as many steps as the tree is tall:

• if the tree is balanced, the height is about log₂ n, and lookup, insertion and deletion are O(log n), while keeping the keys sorted. Red-black and AVL trees rebalance themselves on every insertion to guarantee it; C++'s std::map and Java's TreeMap are red-black trees;
• if nothing rebalances it, inserting keys that are already sorted builds a tree that's just a long chain, and every operation degrades to O(n).

Binary trees have the linked list's cache problem: each step down is a pointer to follow. A B-tree fixes that with wide nodes, each holding dozens or hundreds of keys, and one child per gap between them. The tree becomes only a few levels deep, and each node fills a disk page or a few cache lines. That's why nearly every database index and most filesystems use B-trees or their variant, B+ trees.

A heap is a tree kept in an array: the children of element i are at 2i + 1 and 2i + 2. It always gives the smallest (or largest) element in O(1) and inserts or removes in O(log n). That makes it the standard priority queue, and it's the structure inside heap sort.

Choosing a structure

The usual advice follows from the demos: start with an array, or a hash table for lookup by key, and reach for pointer-based structures only when their operations are really needed.

Takeaways

• A data structure is a memory layout plus operations. Its big-O costs and its access pattern both matter.
• Arrays index in O(1) with address arithmetic and are cache-friendly. Dynamic arrays append in amortized O(1).
• Linked lists insert in O(1) but chase pointers: one cache miss per node, and misses that can't overlap.
• Hash tables look up in O(1) on average, depending on a good hash, a low load factor, and protection against collision attacks.
• Balanced trees keep keys sorted with O(log n) operations. B-trees use wide nodes to cut the number of levels, which is why databases and filesystems use them.