A data structure is a method of organising, storing, and representing data so that a program can access and manipulate it efficiently and correctly. It defines how individual values and their relationships are arranged in memory or in an abstract computational model, together with the operations that can be performed on that organisation. Common data structures include arrays, linked lists, stacks, queues, hash tables, trees, heaps, graphs, sets, maps, tries, and specialised structures such as Bloom filters or B-trees.
The choice of data structure affects the computational complexity, memory usage, locality, mutability, ordering properties, and implementation complexity of algorithms operating on the data. A data structure therefore cannot be evaluated independently of the operations a program needs to perform. An array may provide excellent indexed access but costly insertion in the middle, whereas a linked list can support local insertion efficiently when the relevant node is known but offers poor random access.
Data structures exist at several levels of abstraction. An abstract data type describes the behaviour and operations that a collection should provide without specifying its concrete representation. A stack, for example, is an abstract last-in-first-out collection supporting operations such as push and pop. It can be implemented using an array, a linked list, or another representation. A queue is conceptually first-in-first-out and can likewise have multiple implementations.
A map associates keys with values, while a set represents unique elements under an appropriate equality relation. Concrete data structures determine how these abstractions are physically or logically represented. This distinction between abstract data type and data structure is important because the same abstract behaviour can be implemented through different structures with different performance characteristics. Programming languages and libraries frequently expose abstract interfaces while hiding the underlying representation so implementations can change without changing client code.
Arrays are among the most fundamental data structures. A conventional array stores elements in contiguous memory or in a representation providing equivalent indexed access, allowing an element to be located directly from its index under the relevant model. This generally gives constant-time indexed access, but resizing may require allocating a larger region and copying elements. Inserting or removing an element in the middle of a dense array usually requires shifting subsequent elements.
Dynamic arrays address resizing by maintaining extra capacity and growing according to a strategy that can provide amortised constant-time append operations. Linked lists instead store elements in nodes connected by references or pointers. They can make insertion and removal efficient when a node or position is already known, but accessing the nth element normally requires traversing preceding nodes. These contrasting characteristics illustrate why data-structure selection is an algorithm-design decision rather than merely a storage preference.
Trees and graphs represent relationships rather than simple linear sequences. A tree is a connected hierarchical structure without cycles under the conventional definition, consisting of nodes and edges and often organised around a root. Binary search trees maintain ordering relationships that can support efficient search when balanced, while heaps provide efficient access to a minimum or maximum element and are commonly used to implement priority queues.
B-trees and related multiway trees are widely used in databases and filesystems because their branching structure can reduce the number of expensive storage accesses. Graphs generalise relationships between entities through vertices and edges and may be directed, undirected, weighted, cyclic, acyclic, sparse, or dense. Graph representations include adjacency matrices, adjacency lists, edge lists, and compressed specialised formats. Algorithms such as breadth-first search, depth-first search, shortest-path methods, and network-flow algorithms depend on these representations.
Hash tables provide key-based access by applying a hash function to keys and using the resulting value to determine where entries are stored. Because multiple keys can produce the same hash value, collision-resolution techniques such as separate chaining or open addressing are required. Under suitable assumptions, hash tables can provide expected constant-time lookup, insertion, and deletion, although worst-case behaviour can be linear for common implementations.
Hash-table performance depends on factors such as load factor, hash-function quality, table resizing, key equality, memory layout, and collision handling. Ordered maps and sets instead use structures such as balanced trees when operations need sorted traversal, range queries, or deterministic ordering characteristics. The distinction demonstrates that "fast lookup" is not a single property: the appropriate structure depends on whether the program needs ordering, range operations, stable iteration, memory efficiency, predictable worst-case bounds, or other requirements.
Data structures are closely connected to memory management and representation. A structure may contain values directly or references to other memory locations. In languages with manual memory management, dynamically allocated nodes must be explicitly managed or otherwise governed by ownership rules, while garbage-collected languages generally reclaim unreachable objects automatically. Pointer-heavy structures can introduce allocation overhead and poor cache locality because logically adjacent elements may be physically distant in memory.
Contiguous structures often have better locality and can therefore outperform theoretically comparable pointer-based structures for some workloads. Memory alignment, object headers, allocator behaviour, pointer width, compression, and representation overhead can materially affect the real memory footprint. Persistent and immutable data structures use techniques such as structural sharing to create new versions while preserving older ones. Concurrent data structures additionally require synchronisation or lock-free techniques to maintain invariants when multiple execution contexts access shared state.
The performance of a data structure is normally evaluated in relation to operations such as lookup, insertion, deletion, traversal, indexing, minimum or maximum retrieval, membership testing, and iteration. Complexity notation provides a way to compare how these operations scale with the number of stored elements, but practical performance also depends on memory hierarchy, allocation costs, concurrency, workload distribution, and implementation details.
A priority queue may use a binary heap because it provides logarithmic insertion and removal of the highest-priority element, whereas a simple sorted array may be preferable in a workload dominated by reads and with few updates. A database index may use a B-tree family structure because storage access patterns differ from main-memory computation. A routing system may use specialised graph structures. A compiler may use symbol tables, syntax trees, control-flow graphs, intermediate representations, and dependency graphs. Thus data structures are fundamental building blocks through which algorithms become practical software systems.
Common misconceptions arise from treating data structures as interchangeable containers. They are not merely different syntaxes for storing the same information: their structural invariants determine which operations are efficient and what relationships can be represented naturally. A stack does not mean any particular physical representation, and a linked list is not inherently faster than an array. A hash table does not guarantee constant-time operations in every circumstance, while a balanced tree does not guarantee that every implementation has identical performance.
Data structures can also be combined to create more specialised structures, such as a graph represented by hash maps of adjacency lists or a priority queue built from a heap. Advanced structures can exploit problem-specific properties, including spatial locality, probabilistic membership, persistent versions, compression, or parallel access. Understanding a data structure therefore requires considering its abstract behaviour, concrete representation, invariants, supported operations, complexity, memory characteristics, and the workload for which it is intended.
