Data Structures
These are fundamental structures in computer science which enable complex operations. This chapter only covers data structures that are significant/well-known in computer science, or that are broadly applicable to most computer science fields. You will not find data structures in this chapter that have very specific, niche use cases, or are only applicable to specific fields of computer science.
Cheat Sheet
For the lazy among you...
Abstract Data Types
- List: ordered, not necessarily unique, not finite
- Set: not necessarily ordered, unique, not finite
- Tuple: ordered, not necessarily unique, finite, a composite type in some (probably most) languages
- Stack: first-in-last-out,
pop(),push(),peek() - Queue: first-in-first-out,
enqueue(),dequeue(), can be prioritized (priority queue) - Bag: random or full reads only,
grab()/pick() - Multimap/Associative Array: key-value mappings (e.g. hash table),
getValue(key),insert(key, value)
Performance Tables
If multiple values, the order is Worst-Case | Amortized .
Arrays & Lists
| Structure | Indexing | Insert/Delete [0] | Insert/Delete [n-1] | Insert/Delete [i] | Wasted Space |
|---|---|---|---|---|---|
| Array | Θ(1) | N/A | N/A | N/A | 0 |
| Dynamic Array | Θ(1) | Θ(n) | Θ(n) | Θ(1) | Θ(n) | Θ(n) |
| Hashed Array Tree* | Θ(1) | Θ(n) | Θ(n) | Θ(1) | Θ(n) | Θ(√n) |
| Linked List | Θ(n) | Θ(1) | Θ(1), Θ(n)** | *** | Θ(n) |
| Balanced Tree**** | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) |
** Θ(1) when the last element is known; Θ(n) when the last element is unknown.
*** Insertions/Deletions from the middle of a list are dependent how that element is found (it is Θ(n) to simply go to the ith element, but searching without knowing the index has a different complexity). There is a Θ(1) tax on that algorithm.
**** Not technically a list structure, but included to compare indexing.
| Structure | Search | Insert | Delete | Space |
|---|---|---|---|---|
| Skip List | O(n) | O(log n) | O(n) | O(log n) | O(n) | O(log n) | O(n log n) | O(n) |
| Hash Table | O(n) | O(1) | O(n) | O(1) | O(n) | O(1) | O(n) |
Trees
| Structure | Search | Insert | Delete |
|---|---|---|---|
| Binary Tree | O(n) | O(n) | O(n) |
| Binary Search Tree | O(n) | O(log n) | O(n) | O(log n) | O(n) | O(log n) |
| Cartesian Tree | O(n) | O(log n) | O(n) | O(log n) | O(n) | O(log n) |
| K-D Tree | O(n) | O(log n) | O(n) | O(log n) | O(n) | O(log n) |
| AVL Tree | O(log n) | O(log n) | O(log n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) |
| Splay Tree | Θ(n) | O(log n)* | Θ(n) | O(log n) | Θ(n) | O(log n) |
| B-Tree | O(log n) | O(log n) | O(log n) |
| Trie** | O(m) | O(m) | O(m) |
| Van Emde Boas Tree*** | O(log m) | O(log m) | O(log m) |
| Radix Tree** | O(m) | O(m) | O(m) |
** Tries are a type of associative array, and radix trees are a type of trie. Here, m represents the length of the key.
*** Van Emde Boas trees are also a type of associative array. Here, m is the bit length of the keys and the maximum number of elements that can be stored in the tree is 2m.
Heaps
| Structure | Find-Min* | Delete-Min* | Insert | Decrease-Key | Meld |
|---|---|---|---|---|---|
| Binary Heap | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
| Fibonacci Heap | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
Graphs
There aren't that many types of graphs, and the most common non-standard type is a flow network.
Graphs can be searched in \( O(\left\lvert V \right\rvert + \left\lvert E \right\rvert) \) time using \( O(\left\lvert V \right\rvert) \) space, where \( \left\lvert V \right\rvert \) and \( \left\lvert E \right\rvert \) are the number of vertices and the number of edges, respectively.
The performance of finding the shortest path between two vertices depends on the type of graph (directed, acyclic, does/does not contain negative edge weights, etc.) and the algorithm used. See more in the algorithms chapter.