Data Structures: The Building Blocks of Computation

Abstract

“Algorithms + Data Structures = Programs,” Niklaus Wirth titled his 1976 textbook, and the equation has held up better than almost any other claim in computer science. A data structure is a way of organizing information in memory so that it can be used efficiently, and the choice of structure, far more than the cleverness of the code around it, determines whether a program is fast or slow, scalable or doomed. The array, the linked list, the hash table, the tree, the graph: these are the nouns of programming, and the history of computing is in large part the history of finding the right arrangement of bits for each problem.

The Central Idea: Organization Determines Cost

A computer’s memory is, at bottom, a vast array of numbered cells. Everything else is a convention layered on top. A data structure is such a convention (an agreement about how to arrange data in those cells and how to navigate it) chosen to make the operations a program performs most often as cheap as possible.

The key insight, formalized by the field of algorithm analysis, is that the same task can have wildly different costs depending on the structure used. Finding an item in an unsorted list of a million elements might take a million steps; in a hash table, roughly one; in a balanced tree, about twenty. These differences are described with Big-O notation, which expresses how an operation’s cost grows as the data grows: O(1) (constant), O(log n) (logarithmic), O(n) (linear), O(n log n), O(n²), and worse. Choosing a data structure is choosing your Big-O, and at scale, the difference between O(n) and O(log n) is the difference between a program that works and one that doesn’t.

Every data structure embodies trade-offs. There is no universally best one. A structure that makes lookups fast may make insertions slow; one that saves memory may cost speed. The art is matching the structure to the access pattern.

The Primitives: Arrays and Linked Lists

Two structures sit at the foundation, and almost everything else is built from them.

The array is a block of contiguous memory holding elements of the same type. Its superpower is random access: because every element is the same size and laid out end to end, the address of element i is a simple arithmetic calculation: O(1) to reach any element. Its weakness is rigidity: inserting or removing an element in the middle requires shifting everything after it, and a fixed-size array cannot grow. Arrays map directly onto how hardware memory actually works, which makes them not only simple but cache-friendly, a property that matters enormously on modern processors, where reading from memory the CPU has already cached is vastly faster than fetching fresh from RAM.

The linked list takes the opposite trade. Each element (a node) holds its data plus a pointer to the next node, so the list can live scattered across memory. Inserting or removing an element is O(1) if you already hold the spot, just rewire two pointers, no shifting. But there is no random access: reaching element i means walking the chain from the start, O(n), and the scattered layout is hostile to the CPU cache.

The linked list is usually credited to LISP, and that credit is off by several years. Allen Newell, Cliff Shaw and Herbert Simon built lists as the central structure of their Information Processing Language (IPL) in 1955 and 1956 at RAND and Carnegie Tech, because their Logic Theory Machine had to grow and rearrange symbolic expressions whose size nobody could predict in advance (see Newell and Simon: The Thinking Machines). They described the structure in IRE Transactions on Information Theory in 1956, and Newell and Shaw’s “Programming the Logic Theory Machine” (February 1957) carried the diagram that taught the idea to everyone else. Chained lists appear even earlier, inside Hans Peter Luhn’s January 1953 IBM memo on hashing. John McCarthy’s LISP, from 1958, inherited lists rather than invented them; what LISP added was the name (“LISt Processor”), the cons cell, and the garbage collector its lists made necessary (see Garbage Collection).

Stacks, Queues, and Discipline

Some structures are defined not by their layout but by the discipline they impose on access.

A stack is LIFO, last in, first out. You push items on top and pop them off the top. Stacks are everywhere in computing’s plumbing: the call stack that tracks function calls and returns is a stack, which is why a runaway recursion produces a “stack overflow.” Expression evaluation, undo systems, and depth-first search all run on stacks.

The stack has an unusually well-documented origin, and much of it is German. Konrad Zuse’s Z4 used a two-level stack for subroutines in 1945, and Alan Turing described the mechanism in 1946 under the names “bury” and “unbury.” The general principle came from Klaus Samelson and Friedrich L. Bauer at the Technical University of Munich, who worked it out in 1955 as the Operationskeller, the operation cellar, for evaluating arithmetic expressions in a compiler. They filed a patent on it on 30 March 1957 (see Germany’s Computing Pioneers). The Australian philosopher Charles Hamblin had reached the same idea independently in 1954. Bauer received the IEEE Computer Pioneer Award for the stack principle in 1988; Samelson had died eight years earlier.

A queue is FIFO, first in, first out, like a line at a counter. Queues model anything processed in arrival order: scheduler run queues (see Operating System Concepts), print spoolers, message buffers, and the breadth-first traversal of graphs.

Both are typically built on top of arrays or linked lists; their importance is conceptual; they capture a pattern of use, not a memory layout.

The Hash Table: Average-Case Magic

The hash table (or hash map, dictionary, associative array) is arguably the most consequential data structure in everyday programming. It stores key–value pairs and offers O(1) average-time insertion, deletion, and lookup, find any value by its key in essentially constant time, regardless of how many items the table holds.

It was invented twice over in the 1950s inside IBM. In January 1953, Hans Peter Luhn circulated an internal memorandum describing what is now called hashing with chaining: compute an address from the key, and hang a list off each slot for the keys that collide. Luhn never published it. The first published account came from Arnold Dumey in Computers and Automation in December 1956, which proposed taking the remainder modulo a prime as the address function, still the textbook default. Open addressing, where collisions probe onward into the table instead of hanging off it, came out of the IBM 701 assembler group around Gene Amdahl, Elaine McGraw, Nathaniel Rochester and Arthur Samuel; Andrey Ershov arrived at linear probing independently in the Soviet Union, and W. Wesley Peterson gave the technique its name in 1957. For the longer story, see Hashing.

It works by feeding the key through a hash function that maps it to an index in an underlying array. Good hash functions scatter keys evenly; collisions (two keys mapping to the same slot) are handled by chaining (a small list per slot) or open addressing (probing for the next free slot). The catch is the qualifier average: a poorly designed hash function or an adversarial set of inputs can degrade a hash table to O(n), a fact that has been weaponized in denial-of-service attacks. The hash table is the engine behind language built-ins like Python’s dict, JavaScript’s objects, and the in-memory indexes of countless databases.

Trees: Hierarchy and Logarithmic Search

A tree organizes data hierarchically: a root node with children, each of which may have children, and so on. Trees turn up wherever data is naturally nested, file systems (see File Systems), the abstract syntax trees compilers build (see The Compiler), the DOM of a web page, organizational charts.

The most important variant is the binary search tree (BST), where each node has at most two children and the left subtree holds smaller keys, the right subtree larger. This ordering allows binary search through the structure: O(log n) lookup, provided the tree stays balanced. An unbalanced BST can degenerate into a glorified linked list, O(n), which is why self-balancing trees were invented:

AVL trees (Adelson-Velsky and Landis, 1962), the first self-balancing BST, kept rigidly balanced for fast lookups.
B-trees, wide, shallow trees designed for disk and database storage, where the cost of a disk seek dwarfs the cost of comparing keys. Rudolf Bayer and Edward McCreight devised them at Boeing Research Labs and presented them at the ACM SIGFIDET workshop in July 1970; the journal version, “Organization and Maintenance of Large Ordered Indices,” appeared in Acta Informatica in 1972. Both dates circulate, which is why sources disagree. McCreight has said the meaning of the B was left deliberately open (“Boeing”, “balanced”, “Bayer”), partly because naming it after the company would have required talking to Boeing’s lawyers. The B-tree and its B+-tree variant sit underneath nearly every relational database index (see The Database Revolution) and many file systems.
Red–black trees, slightly looser balancing with cheaper updates; the workhorse behind many standard-library ordered maps (C++ std::map, Java TreeMap). They are Bayer’s too: he published them in 1972 as symmetric binary B-trees, and Leonidas Guibas and Robert Sedgewick recast them in “A Dichromatic Framework for Balanced Trees” (1978). Bayer moved to TU München in 1972 and stayed, which puts two of the most-used structures in database engineering in the same Munich office (see Germany’s Computing Pioneers). The colours were an accident of equipment: Guibas and Sedgewick were at Xerox PARC, and red was the best-looking colour their laser printer produced (see Gary Starkweather, who built it).
Splay trees (Sleator and Tarjan, 1985), self-adjusting trees that rotate each accessed item to the root, giving strong amortized performance and adapting to access patterns without storing any balance information.

Other specialized trees tune the basic idea for a particular access pattern. The heap, for priority queues that always yield the smallest or largest element, came from J. W. J. Williams in 1964 as the machinery of heapsort, published in Communications of the ACM as Algorithm 232; Robert Floyd contributed the faster in-place construction the same year as Algorithm 245 (see The History of Sorting). The trie, for prefix-based string lookup, was described by René de la Briandais in 1959 and named by Edward Fredkin in 1960 after the middle syllable of retrieval, which is why half the field pronounces it “tree” and the other half “try” (see String Matching). Spatial trees like the quadtree and k-d tree follow the same logic for coordinates.

Graphs: Modeling Relationships

A graph is the most general structure: a set of nodes (vertices) connected by edges. Where a tree is a strict hierarchy, a graph allows arbitrary connections, cycles, many-to-many links, the works. Graphs model the things hierarchies cannot: social networks, road maps, the web’s hyperlink structure, dependency relationships, and computer networks themselves (see Distributed Systems).

Graphs are stored as adjacency lists (each node keeps a list of its neighbors, memory-efficient for sparse graphs) or adjacency matrices (a grid of which nodes connect, fast lookup, memory-hungry). The famous graph algorithms (Dijkstra’s shortest path, breadth-first and depth-first search, PageRank) operate on these representations, and the choice of representation shapes their performance.

What Came After the Textbook

The canon above was largely fixed by 1970. The structures added since answer problems the early designers did not have: concurrency, immutability, and storage hardware whose write behaviour differs from its read behaviour.

Skip lists (William Pugh, 1989, published in CACM in 1990) reach balanced-tree performance by flipping coins. Each element is promoted to higher “express lane” levels with fixed probability, so searches skip ahead, and no rebalancing code is needed. Pugh’s argument was that they are simpler and faster in practice than balanced trees, which turned out to matter most for concurrent code: rewiring a few pointers is easier to make lock-free than rotating a tree. Redis stores its sorted sets in skip lists, RocksDB uses one for its in-memory write buffer, and Java ships ConcurrentSkipListMap (see Randomness in Algorithms).

Persistent structures keep every previous version alive after an update. Driscoll, Sarnak, Sleator and Tarjan gave the general technique in “Making Data Structures Persistent” (1986); Chris Okasaki’s 1996 Carnegie Mellon thesis, published as Purely Functional Data Structures in 1998, showed how to get competitive performance when nothing may be mutated at all. The practical vehicle is the hash array mapped trie, described by Phil Bagwell in 2001 and made persistent by Rich Hickey for Clojure’s collections, from where it spread to Scala and to JavaScript libraries. Copying a “modified” map that shares almost all of its structure with the original is what makes immutable-by-default languages affordable.

LSM trees invert the B-tree’s bargain. The log-structured merge-tree (Patrick O’Neil, Edward Cheng, Dieter Gawlick and Elizabeth O’Neil, Acta Informatica, 1996) buffers writes in memory and flushes them as immutable sorted files that background compaction merges later, turning random writes into sequential ones. Reads pay for it by consulting several files. Google’s Bigtable tablet design works this way, LevelDB (Jeff Dean and Sanjay Ghemawat, 2011) reimplemented it in the open, and RocksDB, Facebook’s 2012 fork of LevelDB, is explicitly an LSM store, as are Cassandra and HBase. The B-tree still rules relational indexes; the LSM tree took the write-heavy key-value systems built after 2005.

Text editors got their own branch. A rope (Hans-J. Boehm, Russ Atkinson and Michael Plass, 1995) represents a document as a tree of string fragments, so inserting a character in a 500-page file costs a few pointer changes instead of copying megabytes. The simpler gap buffer, used by Emacs, keeps the whole text contiguous with an empty gap at the cursor, which makes typing cheap and jumping across the file the expensive operation. Both are bets on the same observation: edits cluster.

The Theoretical Backbone

Data structures are inseparable from the analysis of algorithms, the discipline of reasoning rigorously about how cost scales. Donald Knuth’s multi-volume The Art of Computer Programming (from 1968) is the field’s monumental reference, cataloging structures and their analyses with mathematical precision. Few people shaped the modern toolkit more than Robert Tarjan: with collaborators he devised splay trees and Fibonacci heaps, proved in 1975 the near-linear (inverse-Ackermann) bound on the union–find structure that Bernard Galler and Michael Fischer had published in CACM in 1964 as “An Improved Equivalence Algorithm”, and gave the standard linear-time algorithm for a graph’s strongly connected components. He shared the 1986 Turing Award with John Hopcroft “for fundamental achievements in the design and analysis of algorithms and data structures.” The combination of Knuth’s analytical rigor and the practical structures above turned programming from craft toward science: a programmer can now predict, before writing a line, whether a chosen structure will scale to the required size.

Dead End: The Self-Balancing Trade and the Cache Reckoning

For decades, theory ranked data structures purely by their Big-O complexity, and the elegant self-balancing trees reigned as the “correct” answer for ordered data. The modern reckoning has been humbling: Big-O counts operations but ignores that on real hardware, where data sits matters as much as how many steps an algorithm takes. The deep memory hierarchies of modern CPUs (registers, multiple cache levels, RAM, disk, each an order of magnitude slower than the last) mean that a cache-friendly array can crush a pointer-chasing tree or linked list that the textbook declares its equal or superior, because every pointer hop risks a cache miss costing hundreds of cycles. The result has been a quiet rehabilitation of flat, contiguous structures and “cache-oblivious” and “cache-aware” data-structure research, and a recognition that the pristine asymptotic complexity that dominated teaching for half a century was always only half the story. The data structure has not changed; our understanding of what makes one “efficient” has.