Data Structures
The containers themselves: how each one is laid out, and which operation that layout makes cheap.
Array: Insert 7 at index 2
A data structure is a layout decision plus the operations that layout makes cheap. An array puts values side by side, so any index is one address calculation. A linked list scatters them and joins them with pointers, so an insert is two writes instead of a shift. Nothing about the values themselves changes. Only where they sit.
Every structure here buys one operation by giving up another. A hash table says whether a key is present in expected O(1) but cannot tell you the next largest key. A balanced search tree answers that in O(log n) but pays for a rotation on the way back up. A heap hands you the smallest element in O(1) and will not say a word about the second smallest without more work.
So the question is never which structure is best, but which operations you run a million times and which you run once. Read the cost line on each page as a profile: the operations marked O(1) are what the structure was built for, and the O(n) ones are the price it charges for them.
After this you can
- Read a structure by its cost line and say which operation it was built for
- Choose between an array, a linked list, a hash table and a search tree for a given access pattern
- Explain why a hash table lookup is expected O(1) and what its worst case costs
- Say what keeping a search tree balanced buys, and what it charges per insert
- Recognise when a structure is a plain array underneath, as a heap and a hash table both are
In this order
Also in this category
Graph Representations
Graph Structures
Hash Tables and Collision Handling
Range Structures
Caches and Filters
Balanced Search Trees
Linked Lists
String Structures
Where people go wrong
Expected is not guaranteed
A hash table is O(1) expected, which assumes keys spread across the buckets. With a poor hash function or a nearly full table, every operation walks a chain and the worst case is O(n). Structures with a log n bound have no such assumption.
A search tree is only log n if something keeps it balanced
Insert sorted keys into a plain binary search tree and you get a linked list with extra pointers, height n and searches to match. Sorted input is not a rare case, and AVL and red-black trees exist because of it.
Counting the pointers
A linked node carries a pointer per link, which for small values can double the memory, and it puts the values anywhere in the heap. A traversal then misses cache lines that an array walk of the same data would have hit.