Data structures

Ways to lay data out in memory so the operations a program runs most are fast; you choose one by the operations you need and what each one costs.

How it works

A data structure is a layout plus the algorithms that work on it. The same items can sit side by side in one array, in nodes joined by pointers, in a table indexed by a hash of the key, or in a tree kept in sorted order, and each layout makes different operations cheap. An array reads item i in O(1) but has to shift everything after a slot it inserts into. A linked list inserts at its head in O(1) but walks from the head to reach item i. A hash table finds a key in O(1) expected time but keeps no order. A balanced search tree pays O(log n) for every lookup and in return keeps keys sorted, so it can also answer “smallest”, “next after k” and ranges. Costs are written in Big-O: how the work grows with the number of items n. Three refinements matter in practice. Amortized costs spread a rare expensive step over many cheap ones: a dynamic array grows by a multiple of its size, so appending is O(1) amortized even though one append now and then copies everything. Expected costs assume a hash function that spreads keys evenly; bad luck or a crafted input pushes them to O(n). And Big-O ignores memory layout: following a pointer to a node elsewhere in memory can miss the CPU cache, which is why Rust’s docs say array-based containers are almost always better than its linked list, and why its sorted map is a B-tree with many keys per node rather than a binary tree.

Think of it as

A kitchen. Plates stacked in a cupboard are a stack: you take the top one. A numbered spice rack is an array: go straight to slot 12. A recipe-card box sorted by name is a search tree: find “lasagne”, then flip forward to whatever comes next. A coat check is a hash table: your ticket number takes you straight to the hook, but the coats aren’t in any useful order.

Reach for it when

Start from the dynamic array and the hash map; Rust’s collection docs say Vec and HashMap cover most use cases
A work queue that takes from the front: use a deque, because Python’s list.pop(0) shifts every remaining item
Keys you need in sorted order, by range, or “the next one after k”: a balanced tree or B-tree map
Always handling the most urgent item next: a binary heap

Think twice when

Reaching for a linked list for speed: array-based containers are generally faster, smaller and kinder to the CPU cache
Choosing by Big-O alone: two O(1) structures can differ a lot (on ties, Rust’s docs rank Vec ahead of VecDeque, and VecDeque ahead of LinkedList)
Hashing untrusted keys with a fixed, predictable hash function: crafted collisions push lookups toward O(n), the HashDoS attack

A real example

A job runner keeps 100,000 pending jobs in a Python list and takes the oldest with jobs.pop(0). Each pop shifts every remaining item one slot, so draining the queue moves about n²/2, or 5 billion, references. Switching to collections.deque and popleft() makes each removal O(1): in the snippet below the drain drops from 0.8 s to 0.002 s. The same runner checks job_id in seen to skip duplicates. Against a list that scans up to 100,000 items; against a set it is a single hash lookup.

What each structure costs#

Worst case unless marked; n is the number of items and L the length of a key. The figures come from MIT 6.006’s lecture notes and the Python, Java, C++, Rust and Go documentation listed under sources.

Structure	Read item i	Find a key or value	Insert or delete	Min, max, next in order
Dynamic array	O(1)	O(n) scan	O(1) amortized at the end; O(n) elsewhere, since later items shift	O(n)
Sorted array	O(1)	O(log n) by binary search	O(n)	O(1) for min and max; O(log n) for next
Linked list	O(n) walk (doubly linked: from the nearer end)	O(n)	O(1) at the head, or at a node you already hold; O(n) to reach position i	O(n)
Deque (ring buffer or blocks)	O(1) in C++ and Rust; slow in the middle for Python’s	O(n)	O(1) at either end (amortized when it has to grow); O(n) in the middle	O(n)
Hash table	n/a	O(1) expected; O(n) worst	O(1) expected, amortized; O(n) worst	O(n): keys have no order
Balanced search tree (AVL, red-black, B-tree)	O(log n) if nodes store subtree sizes	O(log n)	O(log n)	O(log n)
Binary heap	n/a	O(n)	push O(log n); pop the top O(log n); build from n items O(n)	O(1), but only for the top
Trie	n/a	About L character steps for a hit, however many keys there are	About L steps	Keys come out in order by walking the tree; prefix queries are cheap

Amortized: averaged over a long run of operations. One call can cost O(n) when the backing array is reallocated.
Expected: assumes the hash function spreads keys evenly over the table.
Rust’s BinaryHeap::push is O(1) expected for keys in random order, and O(log n) amortized when keys arrive in ascending order.

What people actually use#

The standard library type for each structure, from each language’s own docs.

Structure	Python	Java	C++	Rust	Go
Dynamic array	`list`	`ArrayList`	`std::vector`	`Vec`	slice and `append`
Stack	`list` with `append` and `pop`	`ArrayDeque` (the `Stack` docs point to `Deque`)	`std::stack`, over `std::deque` by default	`Vec`	slice
Queue or deque	`collections.deque`	`ArrayDeque`	`std::deque`	`VecDeque`	slice, or `container/list`
Linked list	`collections.deque` covers the queue uses	`LinkedList`	`std::list`, `std::forward_list`	`LinkedList`	`container/list`
Hash map and set	`dict`, `set`	`HashMap`, `HashSet`	`std::unordered_map`	`HashMap`, `HashSet`	built-in `map`
Sorted map	`bisect` over a sorted `list`	`TreeMap` (red-black)	`std::map` (usually red-black)	`BTreeMap`	sorted slice and `slices.BinarySearch`
Priority queue	`heapq` (min-heap on a `list`)	`PriorityQueue`	`std::priority_queue` (largest first by default)	`BinaryHeap` (max-heap)	`container/heap`

Amortized, expected and worst case#

A dynamic array that is full allocates a larger block and copies everything across, which takes O(n). MIT’s 6.006 notes show why that is still cheap: if the array grows by Θ(n) extra slots each time, Θ(n) more items fit before the next copy, so any run of n appends costs Θ(n) in total and each append is O(1) amortized. Java’s ArrayList docs say the same thing in plain terms: “adding n elements requires O(n) time.” Rust marks such costs with a * in its tables and notes that its collections never shrink on their own, so removals aren’t amortized.

Hash tables add a second qualifier. Their O(1) is expected: it holds when the hash function spreads keys evenly, and Rust marks it with a ~. Python’s complexity table lists the worst case for dict lookups, inserts and deletes as O(n). MIT’s notes point out that any fixed hash function has some set of keys that all collide, which is why they choose the function at random from a universal family. Rust’s HashMap seeds its default hash randomly for the same reason, to resist HashDoS attacks.

Worst-case bounds matter when one slow call is a problem, such as a latency budget or a real-time loop. Rust’s docs suggest LinkedList for exactly the case where you “can’t tolerate amortization”. Balanced trees give O(log n) per operation with no averaging at all: Java’s TreeMap promises “guaranteed log(n) time cost” for get, put and remove.

Memory layout and the CPU cache#

Big-O counts steps, not where the data lives. Rust’s LinkedList docs say it is almost always better to use Vec or VecDeque, because array-based containers are generally faster, more memory efficient, and make better use of CPU cache. CPython’s list is a contiguous array of references, and its deque is described as a doubly linked list of arrays rather than of single objects, “for greater efficiency”.

The same reasoning shapes trees and hash tables. Rust’s BTreeMap docs explain that in a binary search tree every element sits in its own heap-allocated node, so “every comparison is a potential cache-miss due to the indirection”. A B-tree node instead holds B−1 to 2B−1 elements in one contiguous array, which cuts allocations by a factor of B and improves cache efficiency, at the price of more comparisons per search. Swiss Tables, the hash table design behind Rust’s HashMap and Go 1.24’s maps, keep all slots in one array, split into groups of 8 with a control word of hash fragments, so one comparison checks a whole group of 8 slots at once.

In code · python

import bisect
import heapq
import timeit
from collections import deque

n = 100_000
items = list(range(n))

def drain_list():
    q = list(items)
    while q:
        q.pop(0)       # shifts every remaining item one slot left: O(n)

def drain_deque():
    q = deque(items)
    while q:
        q.popleft()    # O(1) at either end

# timings from one run on Python 3.14, Apple M1 Pro; yours will differ
print(f"list.pop(0)     {timeit.timeit(drain_list, number=1):.3f} s")   # 0.806 s
print(f"deque.popleft() {timeit.timeit(drain_deque, number=1):.3f} s")  # 0.002 s

# membership: a list scans every item, a set hashes straight to a slot
as_set = set(items)
print(f"x in list  {timeit.timeit(lambda: n - 1 in items, number=1000):.4f} s")   # 0.9357 s
print(f"x in set   {timeit.timeit(lambda: n - 1 in as_set, number=1000):.4f} s")  # 0.0001 s

# a sorted list: binary search finds the slot, but inserting still shifts
scores = [3, 8, 15, 42]
bisect.insort(scores, 10)
print(scores)                   # [3, 8, 10, 15, 42]

# a binary heap: the smallest item is always at index 0
tasks = [(3, "write docs"), (1, "page on-call"), (2, "review PR")]
heapq.heapify(tasks)
print(heapq.heappop(tasks))     # (1, 'page on-call')

Often confused with

Purely functional data structures Caching Graph databases Search indexes Database indexes

Where it came from1953–2025

The first data structures were answers to slow searches. In a 1953 internal IBM memo, Hans Peter Luhn suggested putting items into “buckets” chosen from the key and chaining overflow in a linked list: the hash table with chaining. In 1954 Gene Amdahl, Elaine McGraw and Arthur Samuel used open addressing on the IBM 701, and W. Wesley Peterson published the idea in 1957. René de la Briandais (1959) and Edward Fredkin (1960) described tries for searching files with variable-length keys, and Fredkin named them after “retrieval”.

Trees made sorted data cheap to change. Georgii Adelson-Velskii and Evgenii Landis published the first balanced binary search tree, the AVL tree, in 1962. J. W. J. Williams published Heapsort in 1964. In 1970 Rudolf Bayer and Edward McCreight, at Boeing Scientific Research Laboratories, described B-trees for indexes stored on discs and drums, and Bayer’s symmetric binary B-trees of 1972 got the red-black name and colouring from Leo Guibas and Robert Sedgewick in 1978. By 1979 Douglas Comer could call the B-tree the de facto standard for database indexes.

The classic structures have since been retuned for CPU caches rather than replaced. Rust’s sorted map is a B-tree in memory because a binary tree’s scattered nodes cost a cache miss per comparison, and its docs steer people away from linked lists. Google presented Swiss Tables in 2017, an open-addressed hash table that checks a group of 8 slots with one comparison; Rust’s HashMap is a port of it, and Go 1.24 rebuilt its built-in map on it in 2025.

Why it’s built this way

Contiguous arrays over linked nodes: An array finds item i by arithmetic and needs one allocation; linked nodes need one allocation each and a pointer chase per step. Rust’s docs say array-based containers are generally faster, smaller and better for the CPU cache.
Grow by a multiple, not one slot at a time: Growing an array exactly to fit would copy every element on every insert. Allocating Θ(n) spare slots means Θ(n) cheap inserts before the next copy, so appends cost O(1) amortized.
Many keys per node for slow storage: Bayer and McCreight’s indexes were too big for main memory and lived on discs and drums with long access times but high transfer rates once reading began. Pages of many keys made each slow access count, so operations cost time proportional to log_k of the index size.
Choose the hash function at random: Any fixed hash function has some set of keys that all collide and turn O(1) into O(n). Choosing from a universal family, or seeding the hash randomly as Rust’s HashMap does, keeps an attacker from building such a set (HashDoS).

Timeline

1953
Hans Peter Luhn’s IBM memo describes hashing into buckets with linked-list overflow
1960
Edward Fredkin’s “Trie Memory” appears in Communications of the ACM
1962
Adelson-Velsky and Landis publish the AVL tree, the first balanced binary search tree
1964
J. W. J. Williams publishes Algorithm 232, Heapsort, in CACM
1970
Bayer and McCreight describe B-trees in a Boeing research report
1978
Guibas and Sedgewick give red-black trees their name
2025
Go 1.24 rebuilds its built-in map on the Swiss Table design

Sources33

Improve this page on GitHub