When The List Wins

Open Data Structures summarises the linked list trade in one line: you lose constant-time get(i), but given a reference to a node you can insert or delete next to it in constant time.

Four teams each want to swap a contiguous array for a doubly linked list. In which case does the linked list actually pay for its pointer overhead and cache misses?

A list that receives many middle insertions, where the insertion position is given as an index

An LRU cache whose hash map already stores a node handle for every key, and every hit moves that node to the front

A sorted collection that is scanned often and receives an occasional insertion in the middle

A work queue of ten million small structs pushed at one end and consumed at the other