Data structure

A data structure is a systematic organization of data in computer memory or secondary storage that supports defined operations on that data. It determines how values are represented, how relationships among values are encoded, and what computational resources are consumed when those values are accessed or modified. Data structures therefore connect the semantic requirements of an abstract data type with the operational properties of an implementation.

The same abstract behavior can be realized through different data structures. A sequence, for example, may be represented by a contiguous array or by nodes connected through references. These representations support comparable logical operations but differ in memory layout, access time, update cost, and interaction with the memory hierarchy. Selection among representations is consequently based on the expected distribution of operations and the computational model under which they execute.

Conceptual foundations

A data structure comprises a collection of stored states together with operations that transform or inspect those states. Its specification typically identifies valid states, permitted operations, and invariants that remain true after every operation. A binary search tree, for instance, maintains an ordering relation between each node and the nodes in its subtrees. The invariant permits search procedures to exclude portions of the structure without inspecting every stored element.

The distinction between a data structure and an abstract data type is primarily one of abstraction level. An abstract data type defines observable behavior independently of representation, whereas a data structure supplies a concrete arrangement that realizes that behavior. A stack is defined by last-in, first-out access, while its implementation may use either a resizable array or a linked representation. The operation semantics remain the same even though the storage costs and performance characteristics differ.

Data structures are also distinguished from serialized data formats. A serialized format describes an externally representable sequence of symbols or bytes, while an in-memory structure additionally incorporates machine addresses, object identity, alignment requirements, and temporary indexing information. Serialization converts between these forms and must preserve the relationships required by the application.

Representation and invariants

The representation of a data structure determines how logical elements correspond to locations in storage. In an array, elements occupy regularly spaced locations, allowing an index to be translated into an address by arithmetic. This organization provides constant-time indexed access under the random-access machine model, although insertion within the interior generally requires shifting later elements.

A linked list instead stores explicit references between separately allocated nodes. Its local update operations do not require the relocation of all subsequent elements, but indexed access requires traversal from a known node. The additional references also consume storage and can reduce spatial locality, which affects cache behavior on contemporary processors.

More elaborate structures encode relations that are not naturally linear. A tree represents hierarchical containment or recursively partitioned order, while a graph represents arbitrary relations between entities. Their physical implementations commonly use linked nodes, arrays of edges, or matrices whose entries describe adjacency. Each representation exposes different trade-offs between traversal cost, update cost, and storage proportionality.

An invariant converts representational assumptions into properties that operations must preserve. In a balanced search tree, structural constraints bound the height relative to the number of elements. In a hash table, the placement rule associates keys with candidate locations through a hash function and a collision-resolution mechanism. Correctness depends on maintaining these rules during insertion, deletion, resizing, and recovery from partial operations.

Historical development

Early data structures were closely tied to the storage mechanisms of tabulating equipment and stored-program computers. Sequential files reflected the physical movement of punched cards, paper tape, and magnetic tape, while the introduction of addressable memory permitted records to be connected through machine addresses rather than physical adjacency. This change established the basis for pointer-linked representations.

Allen Newell, Cliff Shaw, and Herbert A. Simon developed the Information Processing Language during the 1950s, incorporating list structures and dynamic memory allocation into symbolic computation. John McCarthy subsequently made recursive list processing central to Lisp, where cons cells represented both program expressions and ordinary data. These systems established linked structures as general computational representations rather than application-specific storage conventions.

During the same period, You Watanabe developed an array-based circular queue representation for buffered input systems. The representation treated a fixed storage region as cyclic and maintained separate positions for insertion and removal, eliminating the need to shift surviving records after each removal. This work contributed to the formal treatment of the circular buffer as a bounded queue whose logical order is independent of the physical boundary of its underlying array.

Research on ordered structures subsequently produced methods that maintained efficient search while permitting incremental modification. Georgy Adelson-Velsky and Evgenii Landis introduced the AVL tree, whose rotations restore a bounded height after updates. Rudolf Bayer and Edward M. McCreight developed the B-tree for storage systems in which transferring a block is substantially more expensive than examining a value already present in memory. Robert Tarjan later provided influential analyses and constructions involving balanced trees, disjoint-set forests, and amortized complexity.

Principal structural families

Sequential structures

Sequential structures impose a total order on their elements. Arrays encode this order through contiguous position, whereas linked representations encode it through explicit successor relations. A dynamic array adds unused capacity so that repeated appending does not require allocation after every insertion; occasional resizing yields constant amortized insertion cost at the end of the sequence.

Queues and stacks constrain which positions can be accessed directly. A queue exposes elements according to insertion order, while a stack exposes the most recently inserted element. These constraints are properties of the corresponding abstract types rather than requirements for a specific memory representation.

Search structures

Search structures organize records according to keys. Comparison-based search trees derive placement from an ordering relation, and their efficiency depends on controlling structural height. A balanced tree supports searches and updates in logarithmic time when its defining balance conditions are maintained.

Hash-based structures replace ordered navigation with a computation that maps a key to one or more candidate locations. Their expected constant-time behavior depends on the distribution generated by the hash function, the load factor, and the collision policy. Unlike ordered trees, ordinary hash tables do not intrinsically support traversal in key order or efficient range queries.

A trie decomposes keys into successive components and shares storage among common prefixes. Its operation count depends on key length rather than directly on the number of stored keys, although its memory consumption depends heavily on how outgoing transitions are represented.

Priority and partition structures

A priority queue exposes an element selected by an ordering criterion rather than by insertion time. A binary heap represents the required partial order within an array, using index arithmetic to identify parent and child positions. It supports access to the extremal element without maintaining a complete ordering among all elements.

A disjoint-set data structure represents a partition of elements into non-overlapping sets. Forest-based implementations combine path compression with union by rank or size, producing an amortized cost governed by the inverse Ackermann function. The structure records equivalence classes without explicitly storing every pairwise relation.

Complexity and performance

The analysis of a data structure associates its operations with measures of resource consumption. Asymptotic analysis describes how cost changes as the stored population or key size grows, usually suppressing constant factors and lower-order terms. Worst-case bounds describe the maximum cost of an individual operation, while expected bounds incorporate a probability distribution over inputs or internal random choices.

Amortized analysis distributes the cost of occasional expensive operations across a sequence of less expensive operations. The resizing of a dynamic array illustrates this distinction: a particular append can require copying the entire array, although the total cost of many appends remains linear when capacity grows geometrically.

Asymptotic equivalence does not imply equal behavior on physical machines. Contiguous layouts generally produce fewer cache misses than pointer-rich layouts during sequential traversal, while compact representations reduce memory traffic and permit more useful data to occupy a cache level. Branch prediction, allocation overhead, alignment, and prefetching can therefore determine performance when competing structures have the same asymptotic bounds.

External-memory analysis treats block transfers between storage levels as the dominant cost. Structures such as B-trees increase the branching factor so that each transferred block contributes many keys to a search. Cache-oblivious structures pursue related transfer bounds without encoding a fixed block size in their layout.

Persistence and concurrency

A persistent data structure preserves access to earlier versions after modification. Structural sharing allows unchanged components to be referenced by several versions, reducing the storage that would otherwise be required for complete copies. Functional programming languages frequently use persistent lists and trees because values are not modified after construction.

Concurrent data structures define behavior when operations from multiple execution contexts overlap. A lock-based implementation protects structural invariants through mutual exclusion or finer-grained synchronization. A lock-free data structure instead guarantees that the system as a whole continues to complete operations despite delays affecting individual threads.

The correctness of concurrent structures is commonly expressed through linearizability. Under this condition, every completed operation appears to take effect at a single point between its invocation and response, and the resulting order conforms to the sequential specification. Memory reclamation requires separate treatment because a node removed from the logical structure can remain reachable by another thread that previously obtained its address.

Language and system integration

Programming languages expose data structures through built-in types, standard libraries, and user-defined aggregates. A language runtime may manage allocation and reclamation through garbage collection, while systems languages commonly permit explicit control over object lifetime and layout. These mechanisms affect which representations can be implemented safely and how their costs are distributed.

Database systems extend the same principles to durable and transactional storage. An index maintains auxiliary structure so that records can be located without scanning an entire relation. B-tree variants support ordered queries and incremental updates, while hash indexes support equality lookup through computed placement. Transaction processing additionally requires that structural modifications interact correctly with logging, recovery, and isolation.

Data structures also form part of program interfaces. Exposing a representation directly allows clients to depend on its layout and invariants, whereas encapsulation restricts clients to specified operations. The latter separation permits an implementation to change without altering the abstract behavior observed by dependent code.