Overview

In computer science, a data structure is a systematic way to organize and store values and information so that specific operations can be performed efficiently. A data structure pairs a concrete in-memory layout or storage scheme with the algorithms that operate on that layout. This distinguishes it from an abstract data type (ADT), which specifies the logical behavior and operations without committing to a particular implementation. For example, the ADT called a "list" can be realized as an array, a singly or doubly linked list, or other structures depending on requirements.

Key characteristics and components

Data structures are characterized by how they store elements, how elements are connected or indexed, and what operations they support. Important aspects include physical layout (contiguous versus linked), element size and fields, pointers or indices, memory allocation strategy (static or dynamic), and auxiliary metadata such as size counters or balancing factors. Choices here affect performance properties like time complexity, memory use, and cache behavior.

Common types and brief descriptions

  • Array: Contiguous storage with constant-time indexed access; resizing may be costly.
  • Linked list: Nodes linked by pointers allowing fast insertions and deletions at arbitrary positions; sequential access only; see list abstractions.
  • Stack and queue: LIFO and FIFO structures used in recursion, parsing, and scheduling.
  • Tree (binary search tree, AVL, B-tree): Hierarchical structure for ordered data enabling efficient search, insertion, and range queries when balanced.
  • Heap: Priority-ordered structure for quickly finding and removing the largest or smallest element.
  • Hash table: Key-value map with expected constant-time lookup using hashing, subject to collision management.
  • Graph: Nodes and edges representing networks; represented with adjacency lists or matrices depending on density.

Operations and algorithmic considerations

Typical operations include search, insertion, deletion, traversal, and update. The efficiency of each operation depends on the chosen structure and implementation. Time and space complexity—often expressed in Big O terms—guide these choices. Some structures offer worst-case guarantees (balanced trees), while others give good average or amortized performance (hash tables, dynamic arrays). The choice of algorithms to operate on a structure is an integral part of its practical use; data structures and algorithms are closely paired in system design.

History and evolution

Basic ideas for storing and organizing data have existed since early computing and mathematics, but formal study of data structures became central with the rise of high-level languages and structured programming. Over time, standard libraries in modern languages provided well-tested implementations, and research produced specialized structures for concurrency, persistence (immutable structures), and external memory use (B-trees for disk-based databases).

Applications and choosing a structure

Data structures underpin nearly all software: databases and indexes use B-trees and hash indexes; compilers use symbol tables and abstract syntax trees; networks and routing use graph structures; search engines and caches rely on priority queues and hash maps. Practical selection depends on expected operation mix, data size, memory limits, locality of reference, concurrency needs, and ease of maintenance. Benchmarking with realistic workloads often reveals trade-offs not apparent from theoretical analysis alone.

Distinctions and notable considerations

Important distinctions include ADT versus implementation, mutable versus immutable representations, and single-threaded versus concurrent safety. Low-level details such as memory alignment, pointer overhead, and CPU cache behavior can dominate performance in tight loops. Finally, well-chosen data structures simplify algorithms, reduce bugs, and improve maintainability; selecting the right one is a fundamental skill in programming and system design.

For background reading and definitions, follow the linked topics above to explore foundational material and implementation examples.