Data Structures

A data structure is a way of arranging data in a computer's memory so that the operations a program needs—look something up, insert something new, find the smallest item, list everything in order—can be done quickly and reliably.

11 frameworks, from 1945 to today · Algorithms · Computer Science

still a working view ended · each leads to its entry below

Overview

A data structure is a way of arranging data in a computer's memory so that the operations a program needs—look something up, insert something new, find the smallest item, list everything in order—can be done quickly and reliably1. The subject matters because almost every efficient program rests on it: a database index, a spell-checker, a route planner, and a text editor all succeed or fail on how their data is organized. The history of data structures is the story of inventing these arrangements, proving what they can and cannot do, and repeatedly rediscovering that the machine's physical realities—memory hierarchies, multiple processors, finite space—reshape what "good" organization means.

Arrays, Lists, and the First Stored-Program Machines

The earliest electronic computers already forced the question. The EDVAC design of the mid-1940s, and the machines that followed, stored both instructions and data in the same addressable memory, so programmers had to think explicitly about where things sat. The two primordial arrangements are still the reference points. An array places elements in consecutive memory cells, so any element can be reached instantly by arithmetic on its position, but inserting in the middle means shifting everything after it. A linked list stores each element with a pointer to the next, so insertion and deletion are cheap once you are there, but finding the n-th element means walking the chain12.

Early work on list processing made the linked list a first-class tool. Allen Newell, Cliff Shaw, and Herbert Simon built the Information Processing Language (IPL) at RAND in the mid-1950s for artificial-intelligence programs, and its list structures—chained cells with pointers—were among the first systematic uses of linked representation in software. John McCarthy's LISP, designed in 1958, made the linked list the fundamental data type of a whole language. The trade-off between contiguous and linked storage, and the pointer bookkeeping each demands, became the first lesson every programmer learned.

Hashing: Trading Order for Speed

If you only need to find things by key, not to keep them sorted, there is a faster route. Hashing computes an element's storage location directly from its key using a hash function, so lookup takes roughly constant time regardless of how many items are stored13. The idea was described by H. P. Luhn in an internal IBM memorandum in 1953, on chained hash tables for searching and updating punched-card files. It spread through the 1950s and 1960s into compilers, symbol tables, and file systems.

Hashing's weakness is collisions: two keys landing in the same slot. The field developed two broad answers—chaining, where each slot holds a list of colliding items, and open addressing, where collisions are resolved by probing other slots13. In 1957 W. Wesley Peterson analyzed open addressing for file organization, and in 1963 Donald Knuth gave the first thorough theoretical treatment of linear probing. The 1960s and 1970s produced a family of probing schemes and hash functions, and the analysis of their expected performance under random hashing became a model of probabilistic algorithm analysis. Hashing taught the field a lasting lesson: give up order, and you can buy speed.

Balanced Trees: Keeping Order Without Degrading

Sorted data supports far more operations—range queries, nearest-neighbor search, ordered traversal—but a plain binary search tree degrades to a linked list if keys arrive in sorted order. The fix was to keep the tree balanced automatically. In 1962 Georgy Adelson-Velsky and Evgenii Landis introduced the AVL tree, the first self-balancing search tree, which restores balance after each insertion or deletion by local rotations45. In 1972 Rudolf Bayer and Edward McCreight introduced B-trees, designed for storage where reading a block of data costs far more than comparing keys; a B-tree node holds many keys so the tree stays shallow. B-trees became the backbone of database indexes and file systems and remain so6.

A later, influential design was the red-black tree, formulated by Leonidas Guibas and Robert Sedgewick in 1978 as a simplified encoding of symmetric binary B-trees; it became the standard ordered map in many libraries. The deeper idea these structures share—rebalancing through local restructuring so that worst-case cost stays logarithmic—is one of the field's central achievements.

Heaps and Priority Queues

Many algorithms need to repeatedly extract the smallest (or largest) item: scheduling, simulation, shortest paths. A heap is a tree-shaped structure that keeps the minimum at the root while allowing fast insertion and removal. J. W. J. Williams described the binary heap and its sorting algorithm, heapsort, in 196478. The heap gave the priority queue—an abstract type supporting "insert" and "extract-min"—an efficient implementation, and it became a building block for Dijkstra's shortest-path algorithm and countless others7. Later variants, including binomial heaps (Jean Vuillemin, 1978) and Fibonacci heaps (Michael Fredman and Robert Tarjan, 1987), pushed the theoretical cost of certain operations lower, though their complexity made them rare in practice.

Self-Adjusting and Amortized Structures

A different philosophy asked whether a structure could adapt to how it is actually used rather than maintain a rigid invariant. The splay tree, introduced by Daniel Sleator and Robert Tarjan in 1985, moves any accessed node to the root; a single operation can be slow, but a sequence of operations costs little on average. This required amortized analysis—reasoning about the total cost of a sequence of operations rather than the worst case of one—which Tarjan developed in the mid-1980s and which became a standard analytical tool across algorithms9. The splay tree showed that a structure need not be balanced at every instant to be efficient over time.

Text and String Indexing

Searching large bodies of text raised its own problems. The suffix tree, a structure indexing all suffixes of a string so any substring can be found quickly, was described by Peter Weiner in 1973; simpler constructions followed, and it became a workhorse of computational biology and text processing. The suffix array, a space-efficient alternative, was introduced by Udi Manber and Gene Myers in 1990. The trie, a tree keyed by characters along the path, had roots in earlier retrieval systems and became standard for dictionaries and autocomplete110. These structures made it possible to search genomes and document collections that would be hopeless to scan linearly.

Probabilistic and Approximate Structures

Sometimes exactness is too expensive, and a small, bounded error is acceptable. Bloom filters, introduced by Burton Bloom in 1970, answer "is this element in the set?" using a compact bit array; they can say "definitely not" or "probably yes," never a false negative11. They became ubiquitous in databases and networks for avoiding expensive lookups. Skip lists, described by William Pugh in 1990, use randomized levels to approximate a balanced tree with simpler code. This family—structures that trade certainty for space or speed—grew into a major strand, later joined by count-min sketches and similar summaries for streaming data.

Memory Hierarchies and External Storage

As processors outran memory, the cost of a cache miss or a disk seek dwarfed the cost of a comparison, and structures had to be redesigned around the memory hierarchy. B-trees were an early response. The field of cache-oblivious and external-memory structures, developed especially from the 1990s onward, asked how to organize data to minimize block transfers without knowing the cache size in advance; the van Emde Boas layout and the funnel heap (Michael Frigo, Charles Leiserson, and others, around 1999) are landmarks. These ideas underlie modern databases and search engines, where the bottleneck is almost always memory traffic rather than arithmetic.

Persistence, Concurrency, and Compression

Three further pressures shaped modern structures. Persistent data structures, studied systematically from the 1980s (notably by James Driscoll, Neil Sarnak, Daniel Sleator, and Robert Tarjan in 1986), keep old versions accessible after updates—essential for version control, functional programming, and databases with snapshots. Concurrent and lock-free structures, growing from the 1990s as multicore machines spread, let many threads access shared data without heavy locking; the compare-and-swap primitive and structures built on it became central. Succinct structures, developed from the late 1980s and 1990s (with foundational work by Guy Jacobson and later succinct-data-structure research), store data in space close to the information-theoretic minimum while still supporting fast queries—crucial for indexing enormous text and genomic collections.

The Present

Today's data structures descend directly from these strands. Standard libraries ship hash tables, balanced trees, heaps, and dynamic arrays as defaults1. Database engines rest on B-trees and their variants16. Search and genomics rely on suffix arrays, tries, and succinct indexes. Distributed systems use Bloom filters and sketches to avoid communication. Concurrent and persistent structures are routine in modern languages and runtimes. The open questions are active: how to organize data for heterogeneous memory and accelerators, how to make structures safe and fast under massive parallelism, how to compress indexes further, and how to design structures whose costs are provable rather than merely observed. The field's recurring move—re-examining the machine's real constraints and reorganizing data to meet them—remains its engine.

References

  1. Data structure (introduction, Implementation, Examples, Language support, Usage), Wikipedia
  2. Linked list, Wikipedia
  3. Hash table, Wikipedia
  4. AVL tree, Wikipedia
  5. Binary search tree, Wikipedia
  6. B-tree, Wikipedia
  7. Heap (data structure), Wikipedia
  8. Binary heap, Wikipedia
  9. Amortized analysis (History), Wikipedia
  10. Trie (introduction, History, etymology, and pronunciation), Wikipedia
  11. Bloom filter, Wikipedia

The frameworks of Data Structures

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1945-Present
  2. 1953-Present
  3. 1962-Present
  4. 1964-Present
  5. 1970-Present
  6. 1973-Present
  7. 1985-Present
  8. 1986-Present
  9. 1989-Present
  10. 1990-Present
  11. 1990-Present
A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Data Structures is a planet in Nousfarer

Its city has a tower for each of these 11 frameworks. Land, walk in, and climb one concept at a time.

Land on Data Structures

Related fields

More in Algorithms

See where Data Structures sits on the Map of Human Knowledge