Sign in to watch this lesson
Algorithms - Linear Data Structures · 4:41
Linked Lists and the LRU Cache
A linked list gives every value its own node, so once you hold a node you can insert, erase or splice next to it in O(1). We reverse 1 to 5 in place with prev, cur and next, then measure the price on this Mac: summing a million ints from a scattered std::list is more than a thousand times slower than from a vector, which is why fast code keeps lists in index arrays. Finally a hash map from keys to list nodes turns the list into an LRU cache with O(1) get and put.
You will learn
- Reverse a singly linked list in place with three pointers and explain why next must be saved before the arrow is flipped
- Explain why traversing a std::list is much slower than a vector (one heap node per element, a likely cache miss per hop) and build a linked list in index arrays instead
- Implement an LRU cache with O(1) get and put from a list ordered by recency plus a hash map from key to list iterator, using splice
- Use an array-based doubly linked list (prv[], nxt[] with sentinels) to answer delete-and-find-neighbours queries in O(1)