What Are Data Structures?

Data structures are organized formats for storing, managing, and accessing data in a computer program so that operations such as retrieval, insertion, and deletion can be performed efficiently. The choice of data structure shapes the time and space complexity of an algorithm, making it a foundational concern in software design and systems engineering. A well-matched data structure can reduce a search that would otherwise take linear time to logarithmic or even constant time, while a poor choice can render an otherwise correct algorithm impractically slow. The discipline of data structures sits at the intersection of computer science theory, algorithm design, and practical software implementation.

Data structures are defined and manipulated through programming and computer languages; different languages expose different built-in structures and abstraction mechanisms, but the underlying structural concepts, whether a linked list in C or a dictionary in Python, map to the same theoretical models. Formal study of data structures draws on discrete mathematics, particularly graph theory and combinatorics, and is closely related to algorithm analysis.

Linear Data Structures

Linear structures organize elements in a sequential order where each element has a predecessor and a successor (except at the ends). Arrays store elements at contiguous memory addresses, allowing constant-time random access by index and making them the basis for many higher-level abstractions. Linked lists store elements as nodes, each holding a value and a pointer to the next node, enabling efficient insertion and deletion without the need to shift elements but sacrificing the constant-time random access that arrays provide. Stacks enforce last-in, first-out (LIFO) access, supporting operations such as function call management, expression parsing, and backtracking algorithms. Queues enforce first-in, first-out (FIFO) access and underpin task scheduling and breadth-first traversal. Priority queues, typically implemented as heaps, allow the element with the highest (or lowest) priority to be retrieved in O(log n) time, which is essential in shortest-path algorithms such as Dijkstra's.

Trees and Graphs

Trees and graphs represent non-linear relationships between elements. A binary search tree (BST) organizes elements so that left children are smaller than their parent and right children are larger, enabling O(log n) search, insertion, and deletion on balanced variants such as AVL trees and red-black trees. B-trees generalize the binary search tree to nodes with many children and are the dominant index structure in relational database engines, because their shallow depth minimizes disk seeks; the original B-tree paper by Bayer and McCreight (1972) introduced the structure that still underlies most production database indexes. Heaps are complete binary trees used to implement priority queues with guaranteed logarithmic operations. Graphs consist of vertices and edges and can represent arbitrary pairwise relationships; they are processed with traversal algorithms including depth-first search and breadth-first search, and with path algorithms including Bellman-Ford and Dijkstra's. The ACM Computing Surveys publishes ongoing research on graph data structures and their algorithmic properties.

Hash-Based Structures

Hash tables map keys to values through a hash function that computes an array index from a key. Under ideal conditions, insertion, deletion, and lookup all run in O(1) expected time, making hash tables the implementation behind Python dictionaries, Java HashMaps, and database join accelerators. Collision resolution strategies include chaining, where multiple keys that hash to the same slot are stored in a linked list, and open addressing, where collisions are resolved by probing adjacent slots. Cryptographic hash functions, while not used directly for in-memory lookup, underpin information assurance by enabling integrity verification: a cryptographic digest of a message changes detectably if any bit is altered, making hashing central to digital signatures and secure communication protocols. NIST's guidelines on hash functions and cryptographic standards define the approved algorithms used in security-critical systems.

Applications

Data structures have applications in a wide range of disciplines, including:

• Database indexing and query optimization using B-trees and hash indexes
• Compiler design, where symbol tables and abstract syntax trees are core data structures
• Network routing algorithms that traverse graph structures
• Information assurance and cryptographic systems relying on hash functions
• Operating system scheduling and memory management using priority queues and free lists
• Geographic information systems representing spatial data with quadtrees and k-d trees