Reference
Data structures
Average and worst-case cost of the common operations, then the structures that answer narrower questions, then the three ways to store a graph.
Common data structure operations
| Data structure | Time complexity | Space complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average (or amortized, see notes) | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stacka | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queuea | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-linked listb | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-linked listb | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip listc | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | O(n) | O(n) | O(n) | O(n) | O(n log n) |
| Hash tabled | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| Binary search treee | N/A | O(h) | O(h) | O(h) | N/A | O(n) | O(n) | O(n) | O(n) |
| Cartesian treef | N/A | Θ(log n) | Θ(log n) | Θ(log n) | N/A | O(n) | O(n) | O(n) | O(n) |
| B-tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Red-black tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Splay treeg | N/A | Θ(log n) | Θ(log n) | Θ(log n) | N/A | O(n) | O(n) | O(n) | O(n) |
| AVL tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| KD treeh | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | O(n) | O(n) | O(n) | O(n) | O(n) |
Average, amortized, and worst case
These three words describe different things, so the tables do not treat them as interchangeable.
- Worst case
- The most work a single operation can need, on the least favorable input. It holds no matter what the data looks like.
- Average (expected) case
- The cost averaged over a stated assumption, such as random keys, random insertion order, or a hash function that spreads keys evenly. If the assumption fails, the bound can fail with it.
- Amortized case
- The cost per operation when you average over a whole sequence of operations, with no randomness involved. An occasional expensive operation (like a resize) is paid for by many cheap ones, but a single operation can still be slow.
Where a bound is tight, it is written with Θ; worst-case columns use O as an upper bound. Implementation details and assumptions behind specific rows are in the notes below.
- Stack and queue. Push, pop, enqueue, and dequeue are O(1) when built on a linked list, a circular buffer, or a dynamic array used at one end (a dynamic array's push is amortized O(1)). A queue on a plain array that shifts every element after removing from the front, such as Python's
list.pop(0), takes O(n) per dequeue. - Linked lists. Insertion and deletion are O(1) only when you already hold a reference to the position: the head, or the node before it in a singly-linked list. Finding that position takes O(n).
- Skip list. Search, insertion, and deletion are expected bounds that come from random level choices; the worst case is O(n). Space is O(n) in expectation; O(n log n) is the worst case when levels are capped at log n.
- Hash table. Θ(1) is the expected cost assuming a good hash function that spreads keys evenly and a load factor kept bounded by resizing. If many keys collide, a single operation can take O(n). Insertion is also amortized, because a resize rehashes every key.
- Binary search tree. An ordinary BST costs O(h) for search, insertion, and deletion, where h is its height. That is Θ(log n) when the tree is balanced or keys arrive in random order, and O(n) in the worst case, such as inserting sorted keys. Self-balancing trees (AVL, red-black, B-tree) keep h at O(log n) and so give a worst-case guarantee. A BST does not support access by position.
- Cartesian tree. The Θ(log n) figures assume random priorities, as in a treap. A tree built from adversarial or already-ordered input can degrade to O(n).
- Splay tree. Θ(log n) is an amortized bound over a sequence of operations. A single operation can take O(n), even though the average over many operations is O(log n).
- KD tree. The Θ(log n) figures assume points that keep the tree reasonably balanced. Nearest-neighbor search in high dimensions can degrade toward O(n).
More data structures
These structures answer different questions than the table above, so each lists the operations it is actually used for. In the trie rows, m is the key length.
| Data structure | Operation | Time | Space | Notes |
|---|---|---|---|---|
| Dynamic array | Access by index | O(1) | O(n) | Python list, Java ArrayList, C++ vector. Capacity grows geometrically, so most appends are cheap and an occasional append copies everything. |
| Append | O(1) amortized, O(n) worst | |||
| Insert or delete in the middle | O(n) | |||
| Remove last | O(1) | |||
| Search (unsorted) | O(n) | |||
| Binary heap | Peek min or max | O(1) | O(n) | Stored in an array. Heaps give fast access to one extreme, not sorted order or fast search. |
| Insert | O(log n) worst, O(1) average* | |||
| Extract min or max | O(log n) | |||
| Build from n items | O(n) | |||
| Update or delete at a known position | O(log n) | |||
| Search for a value | O(n) | |||
| Trie | Insert | O(m) | O(n·m) nodes | Cost depends on key length, not on how many keys are stored. Child arrays multiply space by the alphabet size; hash-map children save space. |
| Search | O(m) | |||
| Delete | O(m) | |||
| Find all keys with a prefix | O(m + k) for k results | |||
| Disjoint-set union (Union-Find) | Make set | O(1) | O(n) | With path compression and union by rank or size, find and union cost amortized O(α(n)), which is at most 4 for any practical n. Without both, a find can take O(n). |
| Find | O(α(n)) amortized | |||
| Union | O(α(n)) amortized | |||
| Monotonic stack | Push or pop | O(1) | O(n) | A stack that keeps its items in sorted order by popping anything that breaks the order. Each item is pushed and popped at most once, so problems like next greater element take O(n) in total, not O(n2). |
| Peek | O(1) | |||
| Process n items (whole pass) | O(n) amortized | |||
| Deque | Push or pop at either end | O(1) | O(n) | C++ deque supports O(1) indexing. Java ArrayDeque supports end operations but has no indexed-access API. Python collections.deque uses linked blocks, so indexing near the middle is O(n). A monotonic deque solves sliding-window maximum in O(n). |
| Peek either end | O(1) | |||
| Access by index | O(1) ring buffer, O(n) linked blocks | |||
| Search | O(n) |
Priority queue implementations
A priority queue is an interface, not a single structure. The cost of each operation depends on what sits underneath.
| Implementation | Peek | Insert | Extract min or max | Decrease key | Notes |
|---|---|---|---|---|---|
| Unsorted array | O(n) | O(1) | O(n) | O(1) at a known index | Fine for small n or when extracts are rare. |
| Sorted array | O(1) | O(n) | O(1) from the sorted end | O(n) | Fine when extracts far outnumber inserts. |
| Binary heap | O(1) | O(log n) | O(log n) | O(log n) | The default choice. Python heapq, Java PriorityQueue, and C++ priority_queue use it. Most do not support decrease-key directly. |
| Fibonacci heap | O(1) | O(1) amortized | O(log n) amortized | O(1) amortized | Best asymptotics for Dijkstra and Prim, but large constants make binary heaps faster in practice. |
- * Inserting into a binary heap built from random data moves up a constant number of levels on average. The worst case is still O(log n).
Graph representations
A graph has V vertices and E edges. The representation you pick decides which operations are cheap. Here deg(v) is the number of edges at vertex v.
| Operation | Adjacency list | Adjacency matrix | Edge list |
|---|---|---|---|
| Space | O(V + E) | O(V2) | O(E) |
| Check whether edge (u, v) exists | O(deg(u))* | O(1) | O(E) |
| Iterate neighbors of v | O(deg(v)) | O(V) | O(E) |
| Iterate all edges | O(V + E) | O(V2) | O(E) |
| Add edge | O(1) | O(1) | O(1) |
| Remove edge | O(deg(u))* | O(1) | O(E) |
| Add vertex | O(1) | O(V2)** | O(1) |
| Best for | Sparse graphs and traversals such as BFS, DFS, and Dijkstra. | Dense graphs and algorithms that test many edges, such as Floyd–Warshall. | Algorithms that sort or scan every edge, such as Kruskal and Bellman–Ford. |
- * Storing each vertex's neighbors in a hash set makes edge lookup and removal O(1) on average, at the cost of more memory per vertex.
- ** Growing a matrix means copying it. Preallocating capacity for the maximum number of vertices avoids the copy.
- For an undirected graph, adjacency lists and edge lists store each edge once or twice depending on the implementation; the asymptotic bounds are the same.
The same graph three ways
An undirected graph with four vertices and edges 0–1, 0–2, 1–3, and 2–3.
Adjacency list
0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]Adjacency matrix
0 1 2 3
0 [ 0 1 1 0 ]
1 [ 1 0 0 1 ]
2 [ 1 0 0 1 ]
3 [ 0 1 1 0 ]Edge list
(0, 1)
(0, 2)
(1, 3)
(2, 3)Topics on this page
Each one has its own page with an explanation, code, and the mistakes people make.
- Dynamic array
Index O(1); append O(1) amortized; insert or delete in the middle O(n)
- Hash table (dict and set)
Lookup, insert, delete O(1) expected; O(n) worst case
- Stack
Push, pop, peek O(1)
- Queue and deque
Enqueue and dequeue O(1) with a deque
- Linked list
Insert or delete at a known node O(1); search O(n)
- Binary heap and priority queue
Peek O(1); push and pop O(log n); build from n items O(n)
- Binary search tree
Search, insert, delete O(h): O(log n) balanced, O(n) worst case
- Balanced search tree (AVL, red-black)
Search, insert, delete O(log n) worst case
- Trie
Insert and search O(m) for a key of length m
- Union-Find (disjoint-set union)
Amortized O(α(n)) per find or union
- Monotonic stack
O(n) total
- Graph representations
Edge check: matrix O(1), list O(deg(u))