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
- singly linked list — A linked list in which each node points only to the next node, so it can be walked in one direction.
- deque — A double-ended queue: a sequence that adds and removes items at either end in O(1) time; Python provides it as collections.deque.
- LRU cache — A fixed-size cache that, when full, throws out the entry that has gone unused the longest.
Taught in
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers