Doubly linked list
A doubly linked list is a linked sequence in which each node has references to both its predecessor and successor.
Grokking Data Structures
A doubly linked list is a linked list in which each node contains links to both its previous and next nodes, supporting traversal in both directions.
- How it is used
- Supports movement in both directions and efficient work at the list ends when backward traversal or retracing steps matters.
- How deep it goes
- Works through Python node links, insertion, search, deletion and concatenation, including edge cases and running-time tradeoffs.
- Examples
- Uses a room-navigation game, document layers, undo/redo actions and ordered task lists to illustrate backward movement and concatenation.
- What you can do after
- Build it from scratch with Python nodes and head–tail links, then choose it when bidirectional traversal justifies extra storage and maintenance.
Read how Grokking Data Structures explains doubly linked list →
Advanced Algorithms and Data Structures
A doubly-linked list is a linked list whose nodes contain links to both their predecessors and successors.
- How it is used
- Supports dynamic cache ordering when entries must be inserted at the front and removed efficiently from the tail.
- How deep it goes
- Explains predecessor links, tail removal, cache operations, and O(n) memory, without developing a general implementation.
- Examples
- Uses cache misses, cache hits, tail eviction, and pseudocode for insertion, lookup, updating, and eviction.
- What you can do after
- Build an LRU cache by combining a doubly linked list with a hash table and maintaining synchronized references.
Read how Advanced Algorithms and Data Structures explains doubly linked list →
Related concepts
- linked listkind of · An ordered sequence of elements stored in separate nodes connected by links or references rather than in one contiguous storage region.
- LRUused by · LRU is a cache replacement policy that evicts the item whose most recent access occurred furthest in the past.
- queueused by · A queue is an ordered collection that holds items for retrieval or processing, typically removing them in the order they were added.
- Mapused by · A map is an associative data structure that stores key-value pairs and supports retrieving values by key.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.