Linked lists

A linked list is a chain of separate little boxes, where each box holds one item plus a pointer to the next box (and, in a doubly linked list, the previous one too). The boxes can live anywhere in memory; the pointers are what hold the order together. That makes inserting or removing an item cheap once you’re standing at the right spot, since you only rewire a couple of pointers and nothing else moves. The catch is that reaching item 500 means walking 499 links, and the scattered memory is slow for the CPU to scan. They earn their place in LRU caches, schedulers and memory allocators.