Data Structure

A data structure is a way of organizing information, usually in computer memory, so that it can be accessed and manipulated systematically. It specifies how elements are represented, how they relate to one another, and what properties their organization must preserve. In computer science, data structures work together with algorithms: the representation determines which operations are efficient, while algorithms perform searches, insertions, deletions, and other transformations. A structure may also group related information for conceptual clarity, as in a record containing a person's name and address. (xlinux.nist.gov)

Abstraction and representation

An abstract data type describes a collection of possible values and precisely defined operations without specifying their implementation. A concrete data structure supplies the representation and procedures that realize this specification. The distinction separates what a collection does from how it works. For example, a stack supports last-in, first-out access, but its elements can be stored in an array or a linked list. Both implementations can satisfy the same abstract contract while having different performance characteristics. (xlinux.nist.gov)

A queue commonly provides first-in, first-out access, whereas a priority queue removes an element according to its priority. Lists provide positional access; sets represent distinct elements; dictionaries associate keys with values. Libraries in a programming language often express these abstractions through interfaces and offer several interchangeable implementations. Java's collections framework, for example, distinguishes collection interfaces from array-based, linked, hash-based, and tree-based implementations. (opendatastructures.org)

Sequential structures

An array stores indexed elements in contiguous locations. Under the usual constant-time memory-access model, an element can be retrieved or replaced in $O(1)$ time using its index. Inserting or removing an element within a packed array-based sequence may require shifting subsequent elements, producing an $O(n)$ worst-case cost for a sequence of $n$ elements. (opendatastructures.org)

A dynamic array uses a backing array whose capacity can change. When capacity is exhausted, an implementation allocates a larger array and copies existing elements. Geometric growth makes appending $O(1)$ amortized, although an individual append that triggers copying can take $O(n)$. Logical length and allocated capacity are therefore distinct quantities. (opendatastructures.org)

A linked list consists of nodes containing values and references to neighboring nodes. Singly linked lists provide a next reference; doubly linked lists also provide a previous reference. Updating links permits constant-time insertion or deletion when the necessary node references are already available. Finding a node by position generally requires traversal and can take $O(n)$. Links also consume additional memory, and nodes need not occupy adjacent locations. (opendatastructures.org)

Associative and hierarchical structures

A hash table implements key-based storage by using a hash function to map keys to array positions. Different keys can map to the same position, creating a collision. Chaining stores colliding entries in auxiliary collections; open addressing searches for another position within the table. With suitable hashing and controlled occupancy, lookup can have expected $O(1)$ cost, but performance depends on the hashing scheme and collision handling rather than being an unconditional guarantee. (xlinux.nist.gov)

A binary search tree organizes keys through an ordering rule: keys in one subtree precede the node's key, while those in the other follow it. Search, insertion, and deletion depend on tree height. An unbalanced tree can become a chain and require $O(n)$ time; balancing schemes, such as those used in a red-black tree, maintain logarithmic height and support $O(\log n)$ operations. Unlike ordinary hash tables, ordered search trees directly support traversal in key order. (opendatastructures.org)

A binary heap is a complete binary tree with a heap-order property. In a min-heap, each parent's key is no greater than its children's keys, placing a minimum at the root. It is commonly represented in an array, with parent and child positions calculated from indices. A binary heap supports constant-time inspection of the minimum and logarithmic insertion or removal, making it a standard priority-queue implementation. Heap order does not completely sort the elements. (xlinux.nist.gov)

Graph representations

A graph represents vertices and edges and may be directed or undirected. An adjacency list stores each vertex's neighbors, requiring $O(V+E)$ space for $V$ vertices and $E$ edges. An adjacency matrix uses a matrix of vertex-pair entries and requires $O(V^2)$ space. It provides constant-time edge-existence tests, whereas neighbor enumeration in a basic adjacency list is proportional to the number of stored neighbors. The representation affects the cost of graph traversal and other operations. (opendatastructures.org)

Complexity and practical trade-offs

Data structures are compared through time complexity and space complexity, commonly expressed using Big-O notation. An analysis must identify whether a bound concerns worst-case, expected, or amortized cost and state its computational assumptions. Amortized analysis bounds the total cost of a sequence of operations; it does not require a probability distribution over inputs. Dynamic-array resizing illustrates how occasional expensive operations can coexist with a constant amortized cost. (opendatastructures.org)

Physical organization also matters. Arrays provide compact sequential storage, while linked structures introduce references and potentially scattered allocations. Consequently, asymptotic bounds do not alone determine actual execution time or memory consumption. (opendatastructures.org)

External storage and versioning

A B-tree is a balanced, multiway search tree. Its high branching factor reduces tree height and the number of accesses needed when information resides in slower external storage. External-memory analysis therefore considers block transfers as well as computation within memory. (xlinux.nist.gov)

A persistent data structure preserves previous versions after updates, allowing older states to remain queryable. In this technical sense, persistence means retaining versions, not merely saving information to disk. (xlinux.nist.gov)