Data Structures

Data Structures#

Data structures are the containers underneath the algorithms. The operations they support fast, and the ones they don’t, drive the choice of algorithm.

Arrays#

Contiguous, fixed-size (or growable) sequence with O(1) random access. The default for any “list of items” use case; cache-friendly because sequential access is the fastest pattern modern CPUs offer. Cost table.

Operation

Cost

Index access

O(1)

Append

O(1) amortized (dynamic), O(1) (fixed)

Prepend

O(n)

Insert middle

O(n)

Search

O(n) (unsorted)

  • Cache-friendly; sequential access is the fastest pattern in modern CPUs.

  • Bounded vs. dynamic (Vec, ArrayList, list).

Linked Lists#

Each node points to the next (singly) or both directions (doubly). Slower in practice than the Big-O suggests because pointer-chasing kills cache locality; useful in specific niches like free lists, intrusive lists in OS code, and certain functional structures.

Operation

Cost

Index access

O(n)

Append

O(1) (with tail pointer)

Prepend

O(1)

Insert middle

O(1) (with reference to position)

Search

O(n)

  • Pointer-chasing kills cache locality; linked lists are slower in practice than their Big-O suggests.

  • Useful in specific cases: free lists, intrusive lists in OS code, certain functional structures.

Stacks#

Last-in-first-out. Push and pop at the top, both O(1) amortized when backed by a dynamic array. Underlies function calls, expression evaluation, depth-first search, undo stacks, and most parser implementations.

  • Backed by an array (vector / dynamic array): O(1) amortized.

  • Used for: function calls, expression evaluation, DFS, undo, parsing.

Queues#

First-in-first-out. Enqueue at the back, dequeue at the front, both O(1). Backed by a ring buffer, an array-based deque, or a linked list with head and tail pointers. Used for breadth-first search, scheduling, buffering, and message queues.

  • Array-backed deque (ring buffer): O(1) for both ends.

  • Linked list (with head and tail): O(1).

  • Used for: BFS, scheduling, buffering, message queues.

Deques#

Double-ended queue with O(1) push/pop at both ends. Foundational; many “stack” or “queue” needs are better served by a deque, since switching directions costs nothing. Implementations. ring buffer, circular array, doubly-linked list, unrolled linked list.

  • Foundational; many “stack” or “queue” needs are better served by a deque.

  • Implementations: ring buffer, circular array, doubly-linked list, unrolled linked list.

Hash Tables#

Average O(1) lookup, insert, delete via a hash function and bucket array. The default associative-data structure in every modern language. Quality of the hash function and the load factor determine whether the average case actually holds; bad hashes degrade to linear scans.

Operation

Cost

Insert

O(1) average, O(n) worst

Lookup

O(1) average, O(n) worst

Delete

O(1) average, O(n) worst

Collision handling.

  • Separate chaining, each bucket is a list.

  • Open addressing, linear, quadratic, or Robin Hood probing.

Quality matters.

  • Bad hash → many collisions → linear behavior.

  • Adversarial input → DoS via hash flooding; use a randomized seed.

Used for: dictionaries / maps, sets, caches, deduplication.

Trees#

Hierarchical: each node has zero or more children. Trees are the workhorse for ordered data, prefix matching, hierarchical storage, and the underlying structure of every database index. The variants below are what operators encounter most often.

Binary trees (each node ≤ 2 children).

  • Binary Search Tree (BST), left subtree < node < right subtree. Unbalanced ones degrade to O(n).

  • Balanced BSTs, AVL, red-black, weight-balanced. O(log n) operations.

  • Heap, complete binary tree with parent > children (max-heap) or parent < children (min-heap). Underlies priority queues.

B-trees / B+-trees, many keys per node; the staple of databases and filesystems for disk- or page-friendly storage.

Tries (prefix trees), character per edge; O(m) lookup for length-m keys, regardless of dataset size. Used for autocomplete, IP routing, spell-check.

Heaps and Priority Queues#

Min- or max-heap as a binary tree, usually stored implicitly as an array. Underlies priority queues; if you’ve ever used Dijkstra’s algorithm, A*, top-k selection, or task scheduling, a heap was doing the work underneath.

Operation

Cost

Push

O(log n)

Pop top

O(log n)

Peek top

O(1)

Used for: Dijkstra’s algorithm, A*, top-k, scheduling.

Graphs#

Vertices and edges, the abstraction underneath everything from social networks to package dependencies. The choice of representation drives the cost of every graph operation; pick by sparsity (most graphs are sparse, which favors adjacency list).

  • Adjacency list, per vertex, a list of neighbors. Space O(V + E). Better for sparse graphs.

  • Adjacency matrix, V×V boolean / weight matrix. Space O(V²). Better for dense graphs and constant-time edge queries.

Variants: directed / undirected, weighted / unweighted, simple / multi, DAG, tree.

Disjoint Set (Union-Find)#

Tracks elements partitioned into disjoint sets, with two operations: find (which set is x in?) and union (merge two sets). With path compression and union by rank, both operations are amortized O(α(n)), effectively constant. Used for Kruskal’s MST, cycle detection, and dynamic connectivity.

  • find(x), representative of x’s set.

  • union(x, y), merge two sets.

With union by rank + path compression, both operations are amortized O(α(n)), effectively constant. Used for Kruskal’s MST, cycle detection in undirected graphs, dynamic connectivity.

Bloom Filters#

Probabilistic membership: “definitely not in the set” or “probably in the set” (configurable false-positive rate, no false negatives). Bit array plus multiple hash functions, with a small memory footprint. The classic use case is fast no-go checks that save a slow lookup.

Used for: cache pre-checks, spell check, network blocklists, anywhere a fast no-go answer saves a slow lookup.

Skip Lists#

Probabilistic, sorted, layered linked list. O(log n) expected for search, insert, and delete; simpler to implement than balanced BSTs and easier to make concurrent. Redis uses skip lists for its sorted-set type for exactly these reasons.

Segment Trees / Fenwick Trees#

Range queries on arrays, “sum/min/max of elements between index i and j, with point updates in between.” Standard tools in competitive programming and online statistics; segment trees are flexible, Fenwick trees (BITs) are smaller and faster for prefix-sum specific work.

  • Segment tree, O(log n) for range sum / min / max / update; flexible.

  • Fenwick tree (BIT), O(log n) prefix sums; small constant factor.

Used in competitive programming, time-series, online statistics.

Choosing#

Driven by the access pattern. Most production code reaches for the language’s built-ins; understanding the internals lets you pick the right one and recognize when a custom structure is justified.

  • Random access by index → array.

  • Insertion / deletion at ends → deque.

  • Insertion / deletion in middle → linked list (rare; usually swap-and-pop on array suffices).

  • Lookup by key → hash table.

  • Sorted by key → BST or skip list.

  • Min / max access → heap.

  • Set membership → hash set or bloom filter.

  • Range queries → segment / Fenwick tree.

  • Graph relationships → adjacency list (default).

Most production code uses the language’s built-ins; understanding the internals lets you choose well.

Contents