Doubly linked list

As explained in Advanced Algorithms and Data Structures

A doubly-linked list is a linked list whose nodes contain links to both their predecessors and successors.

A doubly linked list stores links from each node to both its predecessor and successor. In an LRU cache, placing new entries at the front and retaining a tail pointer makes least-recently-used removal take O(1) time. section 7.4.2

An LRU cache uses the list together with a hash table:

• Add new entries at the front of the list. section 7.4.2

LRU cache

A hash table finds a cache entry and points to its list node; the list maintains recency order without duplicating the stored object. The combined structure uses O(n) memory. section 7.4.2

Figure 7.5 Structure of an LRU cache. You can see the tree data elements that are stored for the cache and need to be updated after every operation: (1) The hash table. (2) The head of a doubly-linked list. (3) A pointer to the last element in the list. Notice how each element in the hash table points to a node in the list where all the data is stored. To get from a list entry to the corresponding hash entry, we have to hash the name of the company stored in the node, which is the key for the table. For the sake of simplicity, collision resolution is not considered in this and the following figures.

Trace how the hash table, list head, tail pointer, and shared nodes cooperate in an LRU cache. section 7.4.2

How Advanced Algorithms and Data Structures covers it

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 it assumes

Assumes familiarity with running times and the difference between singly and doubly linked lists.

What you can do after

Build an LRU cache by combining a doubly linked list with a hash table and maintaining synchronized references.

How it connects

Connects doubly linked lists to LRU caches, hash tables, linked lists, queues, FIFO ordering, and arrays.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Data StructuresA 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.

Compare how 2 books explain 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.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.