doubly linked list

A linked list in which each node points to both the next and the previous node, so it can be walked either way and any held node removed in O(1).

In more detail

The extra pointer costs memory but means a node can unlink itself without searching for its predecessor. LRU caches pair one with a dict for O(1) moves to the front. Python's deque is a doubly linked list of fixed-size blocks rather than of single items.

Related terms

Taught in

References