Doubly linked lists: relink known nodes safely

Last updated: 5 Oct 20269 min read

tutorial

A doubly linked list gives each node a previous and next reference. Given a valid node belonging to the list, removal changes a bounded number of links in O(1) time. Searching for the node by value remains O(n). A sentinel head and tail simplify edge cases because insertion and removal use the same link operations at both ends. The representation invariant requires adjacent nodes to agree: if A.next is B, then B.previous is A. A removed node should lose its old links so an accidental second removal cannot quietly corrupt neighbors.

Operational case

A session tracker keeps active cards C-47, C-52, and C-61. Its hash map holds direct node references, allowing the card C-52 to move to the front after access without a list search. The list supplies recency order; the map supplies keyed lookup. When C-52 is removed, C-47 and C-61 become neighbors. The data structure is worthwhile only if the map and list are updated together; a map entry pointing to a detached node makes later operations incorrect even though both containers still exist.

Working Python program

class CardNode:
    def __init__(self, card_id):
        self.card_id = card_id
        self.previous = None
        self.next = None

first, middle, last = (CardNode(card_id) for card_id in ("C-47", "C-52", "C-61"))
first.next, middle.previous = middle, first
middle.next, last.previous = last, middle
first.next, last.previous = last, first
middle.previous = middle.next = None
print(first.card_id, first.next.card_id, last.previous.card_id)

Output

C-47 C-61 C-47

Time, space, and tradeoff

Known-node removal changes four endpoint references in O(1) time and needs no new node. The structure stores two references per node, and the map used for keyed access consumes O(n) additional space. A complete implementation should guard against removing a sentinel or a node owned by another list; the small example shows the relink itself, not a concurrent production cache. Under concurrency, map and list mutations need one consistency boundary so observers cannot see an index pointing at a detached node.

Common Mistakes

Do not describe lookup by value as constant time without an index.
Do not detach only one side of a neighboring pair.
Do not keep an index entry for a removed node.

Connected lessons

data structures

linked-lists