Card 06/ 06
Recap: Combining Data Structures
Name the operation each structure is slow at, let the other cover it, and update both every time.
Combining data structures means keeping the same items in two structures, so that each covers the operation the other is slow at. The topic comes down to the five ideas below, each listed with the card that covers it. One rule links them: two structures over the same items are one structure, so every change goes to both.
| The idea | Where |
|---|---|
| An LRU cache pairs a hash map, which finds a key, with a doubly linked list, which keeps the order of use; the map stores a reference to each node | Combining Two Structures to Cover Each Other's Slow Operation |
| Every get or put moves its key to the front, and a full cache evicts the key at the back from both structures | Trace an LRU Cache Through Gets and Puts |
Sentinel nodes remove the edge cases; OrderedDict, an access-ordered LinkedHashMap and a re-inserted Map are the built-in versions | LRU Cache in Python, Java and TypeScript |
| An array and a map of indexes pick a random item in O(1), and delete by moving the last item into the gap | Combining Example: A Set That Picks a Random Item in O(1) |
| A change to one structure but not its partner fails later, so one method updates both | Updating One Structure but Not Its Partner |
The cache's costs show the method at work: each structure alone fails one operation, and the pair makes all three O(1).
| Operation | Hash map alone | Doubly linked list alone | Both together |
|---|---|---|---|
| Get the value for a key | O(1) on average | O(n) | O(1) |
| Mark a key as most recently used | Not possible | O(1) once found | O(1) |
| Evict the least recently used key | O(n) | O(1) | O(1) |
The same method applies beyond these two designs: write down the operations, find the one each candidate structure is slow at, and look for a partner that makes it cheap. Together these ideas let you design a structure from two parts when no single one fits, trace both parts through any sequence of operations, and keep them in step so that neither tells a different story from the other.
← → move through sections and cards