The question this module answers: what if you need to insert and remove in the middle, often, without moving everything else? An array keeps items side by side, so position i is one multiplication away, but inserting at the front shifts every item. A linked list keeps each item in its own node with a pointer to the next one: inserting or removing next to a node you hold is O(1), and finding position i is O(i).
ML context. You rarely write a linked list in Python application code, but linked structures are everywhere underneath:
- Caches: an LRU cache (lesson 7.7) is a hash map plus a doubly linked list, so moving an entry to "most recent" and evicting the oldest are both O(1). Embedding caches and prompt caches work this way.
- Memory allocators: serving engines split the KV cache into fixed-size blocks and keep the free ones in a free list; allocating and freeing a block is O(1) (Section 5).
- Queues:
collections.dequeis a doubly linked list of fixed-size blocks.
1. The problem: inserting at the front
Task: keep a sequence where new items are often added at the front, like the most recent requests or a history you prepend to.
A Python list is a contiguous array of pointers. Inserting at position 0 moves all n of them: O(n) per insert, O(n²) for n inserts.