Data Structures are organised methods for representing and storing data so that required operations can be performed efficiently. A data structure specifies relationships among stored values and provides a conceptual and often programmatic framework for accessing, inserting, deleting, searching, updating, ordering, or otherwise manipulating those values. Common structures include arrays, linked lists, stacks, queues, hash tables, trees, heaps, graphs, sets, maps, and specialised structures such as tries, union-find structures, interval trees, and spatial indexes.
The choice of structure affects the computational cost of operations and can therefore determine whether an application remains practical as its data volume increases. A data structure is not simply a container for values; it embodies organisational assumptions and supported operations. An array emphasises indexed contiguous storage, a linked list emphasises linked elements, a stack imposes last-in-first-out access, and a priority queue exposes elements according to priority.
Data Structures are closely connected to the development of programming languages, algorithms, and computer architecture. Early computing systems necessarily represented data using memory locations, records, arrays, and linked structures, while later research formalised abstract data types and efficient representations. An abstract data type describes the behaviour and operations of a data collection without requiring a particular representation, allowing the same logical interface to be implemented using different structures.
For example, a priority queue can be implemented using a binary heap, an ordered array, or other structures, with different performance characteristics. Modern languages provide built-in or standard-library implementations of many structures, but their internal representations remain important when performance, memory usage, concurrency, persistence, or specialised behaviour matters. Data Structures have consequently become a foundational subject in computer science because they connect mathematical models of information with concrete machine storage and algorithmic operations.
Arrays store elements in an indexed arrangement and typically provide constant-time access when an index can be translated directly into a memory address. Contiguous arrays can have excellent cache locality, but inserting or removing elements from the middle may require shifting many elements. Linked lists represent elements as nodes connected by references, allowing certain insertions and deletions to occur without moving neighbouring elements, but they generally require additional memory for links and can have poorer cache locality and slower indexed access.
Stacks restrict access according to last-in-first-out behaviour, while queues normally use first-in-first-out behaviour. Deques support efficient insertion and removal at both ends. These structures illustrate a general principle: there is usually no universally optimal representation, because improving one operation or property often involves trade-offs in another. Performance must therefore be considered according to the operations an application performs most frequently.
Trees organise elements hierarchically and support a broad range of operations. Binary search trees maintain an ordering relationship that can permit efficient searching, insertion, and deletion when their height is controlled. Balanced structures such as AVL trees and red-black trees maintain constraints that prevent pathological height growth. Heaps provide efficient access to a minimum or maximum element and are widely used to implement priority queues.
B-trees and related multiway structures are particularly important for storage systems and databases because their high branching factors reduce the number of expensive external-memory accesses. Tries organise strings according to their prefixes and can support specialised prefix operations. Tree structures also form the basis of expression representations, file-system hierarchies, syntax trees, indexes, decision structures, and numerous other computational representations.
Hash tables organise data using a hash function that maps keys to locations or buckets. A well-designed hash table can provide expected constant-time insertion, deletion, and lookup under suitable assumptions, although collisions occur because many possible keys may map to a finite number of positions. Collision-resolution techniques include separate chaining and open addressing, with variants such as linear probing, quadratic probing, and double hashing.
Performance depends on the hash function, table capacity, load factor, collision pattern, resizing strategy, and implementation details. Hash tables are particularly useful for dictionaries, symbol tables, caches, sets, memoisation, and indexes. They differ fundamentally from ordered structures because they generally prioritise fast equality-based lookup rather than maintaining a sorted traversal order. Cryptographic hash functions can also be used in specialised contexts, but ordinary hash-table hash functions are normally optimised for distribution and speed rather than adversarial security properties.
Graphs represent relationships among entities using vertices and edges and may be directed, undirected, weighted, unweighted, cyclic, or acyclic. Graph representation is itself a data-structure decision. An adjacency matrix uses a two-dimensional representation and provides direct edge-existence checks but requires space proportional to the square of the number of vertices. An adjacency list stores neighbouring vertices and is usually more space-efficient for sparse graphs.
Edge lists simply store collections of edges and can be useful for algorithms that process edges directly. More specialised representations may exploit regularity, geometric structure, compression, or parallel hardware. Graph representations strongly influence algorithmic performance because operations such as finding neighbours, testing adjacency, iterating edges, and modifying connections have different costs under different structures.
Data Structures involve significant practical trade-offs involving time, memory, locality, mutability, ordering, persistence, and concurrency. Contiguous structures can benefit from CPU caches and predictable memory access, whereas pointer-heavy structures can incur indirection and allocation overhead. Dynamic structures may grow or shrink as required but can introduce resizing or fragmentation costs. Immutable structures can simplify reasoning and concurrency at the expense of additional allocations or structural sharing complexity.
Persistent data structures preserve previous versions of data, which is useful for functional programming, version control, transactional systems, and undo mechanisms. Concurrent data structures are designed to support simultaneous access by multiple threads while controlling races and maintaining consistency. External-memory and distributed structures must additionally account for storage blocks, network communication, replication, and failures rather than assuming all data resides in one uniform memory space.
A common misconception is that a more sophisticated Data Structure is automatically superior to a simpler one. In practice, performance depends on workload, scale, operation frequency, memory hierarchy, implementation quality, and required semantics. An array may outperform a linked list for many workloads despite less attractive theoretical insertion characteristics because contiguous memory provides superior locality. A hash table may provide rapid lookup but cannot naturally provide ordered traversal without additional mechanisms.
Trees can provide predictable ordering and bounds but may require more complex balancing. Choosing a data structure therefore requires identifying the dominant operations and constraints before selecting an implementation. Data Structures and algorithms are inseparable in practice: the structure determines which operations are naturally efficient, while algorithms determine how those operations are combined into useful computations. A strong computational design consequently treats data representation and algorithm selection as interdependent decisions rather than independent stages.
