Lesson 10 · Linear structures

Doubly Linked Lists

A doubly linked list node contains two pointers: one to the next node and one to the previous node. This allows for bidirectional traversal and simplifies deletions, but requires managing twice as many connections.

Node Structure and the Prev Pointer

A doubly linked list is a linear data structure in which each node holds a data field and two pointers: next, referring to the successor, and prev, referring to the predecessor. The list is accessed through a head reference, and usually a tail reference as well, so both ends are reachable in O(1).

The defining difference from a singly linked list is that the links are symmetric. From any node you can move in either direction, so the structure supports forward and backward traversal from an arbitrary starting point, not only from the head.

The first node's prev and the last node's next are both null (or NULL in C, nullptr in C++, None in Python). Those two nulls are what identify the boundaries, and forgetting to set them is the most common structural bug in a doubly linked list in c implementation.

The cost of the extra pointer is one machine word per node — 8 bytes on a 64-bit system. For a list of small integers that can mean the pointer overhead exceeds the data itself, which is the trade being made in exchange for O(1) deletion and reverse traversal.

Node = data + next + prev
head.prev and tail.next are both null
Traversal works in both directions from any node
Costs one extra pointer (8 bytes) per node

Insertion: The Four Pointer Writes

Inserting node X between existing nodes A and B requires exactly four pointer assignments, and the order matters. Write X.prev = A, then X.next = B, then A.next = X, and finally B.prev = X. Setting the new node's links first means the original chain is still intact if you need to read from it.

The classic bug is updating A.next = X before reading A.next into X.next. Once A.next is overwritten, the reference to B is lost and the remainder of the list is unreachable — a memory leak in C or C++, and silent data loss everywhere else.

Insertion at the head is the same four writes with A absent: set newNode.next = head, newNode.prev = null, then head.prev = newNode — but only if head is not null — and finally reassign head = newNode. If the list was empty, tail must also be set to the new node.

Insertion at the tail is symmetric and is O(1) precisely because a tail reference is maintained. Without one, reaching the end costs a full O(n) traversal, which is why practical implementations always keep both references.

Order: X.prev, X.next, then A.next, then B.prev
Write the new node's links before overwriting the old ones
Empty-list insertion must set both head and tail
Positional insertion is O(n) — the traversal, not the rewiring

Deletion in O(1) and Why Singly Linked Lists Cannot

This is the operation that justifies the structure. To delete node X, execute X.prev.next = X.next and X.next.prev = X.prev. Two writes, no traversal, O(1) time — given only a reference to X itself.

A singly linked list cannot do this. Deleting X there requires rewriting the predecessor's next pointer, and the only way to find the predecessor is to walk from the head until you reach the node whose next equals X. That search is O(n), and it is the entire reason the prev pointer exists.

The boundary cases need explicit handling because one of the neighbours may be null. If X.prev is null, X was the head, so set head = X.next instead of dereferencing X.prev. If X.next is null, X was the tail, so set tail = X.prev. Deleting the only node sets both head and tail to null.

In a language with manual memory management, the node must then be freed — free(X) in C, delete X in C++. In Java or Python the garbage collector reclaims it once no reference remains, which is why a stale prev pointer left dangling elsewhere can silently keep a deleted node alive.

Deleting a node when you already hold a reference to it
List type	Find predecessor	Rewire	Total
Singly linked	O(n) traversal	O(1)	O(n)
Doubly linked	O(1) via `prev`	O(1)	O(1)

X.prev.next = X.next; X.next.prev = X.prev
Null prev means X was the head — reassign head
Null next means X was the tail — reassign tail
Free the node explicitly in C and C++

Key reference

Terms, operations, and practical uses

Pointer mechanics

Previous Pointer (prev)An additional reference in every node that points to the node immediately behind it.
Bidirectional TraversalThe ability to walk the list backward from tail to head, impossible in a singly linked list.
O(1) DeletionRemoving a node instantly if you hold a reference to it, by bridging its prev and next nodes together.

Structure management

Tail PointerA reference to the very last node, allowing O(1) insertions at the end and backward traversal.
Sentinel NodesUsing both a dummy head and dummy tail to ensure every real node has a non-null prev and next, eliminating edge cases.
Pointer ReassignmentThe complex process of updating four different pointers to safely insert a node between two others.

Real-world uses

LRU CacheLeast Recently Used cache. Combines a hash map with a doubly linked list to evict the oldest item in O(1) time.
Browser HistoryStoring web pages so the user can freely step backward and forward through their visited sites.
Undo/Redo BuffersAllowing users to traverse backward through their action history, and forward if they redo.

Implementation

Deleting a Node in O(1) with Its prev Pointer

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

# Build 10 <-> 20 <-> 30 <-> 40 <-> 50
head = Node(10)
node = head
for value in (20, 30, 40, 50):
    node.next = Node(value)
    node.next.prev = node
    node = node.next

def delete(node):
    # The node itself is enough: prev is right there.
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev
    node.prev = node.next = None

target = head.next.next          # the node holding 30
delete(target)

forward = []
node = head
while node:
    forward.append(node.val)
    tail = node
    node = node.next

backward = []
node = tail
while node:
    backward.append(node.val)
    node = node.prev

print(' <-> '.join(map(str, forward)), '(forward)')
print(' <-> '.join(map(str, backward)), '(backward)')

#include <iostream>
using namespace std;
struct Node {
    int val;
    Node* prev;
    Node* next;
    Node(int x) : val(x), prev(NULL), next(NULL) {
    }
};
void deleteNode(Node* node) {
    if(node->prev) {
        node->prev->next = node->next;
    }
    if(node->next) {
        node->next->prev = node->prev;
    }
    delete node;
}
int main() {
    Node* head = new Node(10);
    Node* node = head;
    int values[] = {20, 30, 40, 50};
    for (int i = 0; i < 4; i++) {
        node->next = new Node(values[i]);
        node->next->prev = node;
        node = node->next;
    }
    Node* tail = node;
    Node* target = head->next->next; // the node holding 30
    deleteNode(target);
    for(Node* p = head; p != NULL; p = p->next) {
        cout << p->val;
        if (p->next) cout << " <-> ";
    }
    cout << " (forward)\n";
    for(Node* p = tail; p != NULL; p = p->prev) {
        cout << p->val;
        if (p->prev) cout << " <-> ";
    }
    cout << " (backward)\n";
}

class Main {
    static class Node {
        int val;
        Node prev;
        Node next;
        Node(int x) {
            val = x;
        }
    }
    static void delete(Node node) {
        if(node.prev != null) {
            node.prev.next = node.next;
        }
        if(node.next != null) {
            node.next.prev = node.prev;
        }
        node.prev = null;
        node.next = null;
    }
    public static void main(String[] args) {
        Node head = new Node(10);
        Node node = head;
        int[] values = {20, 30, 40, 50};
        for (int i = 0; i < values.length; i++) {
            node.next = new Node(values[i]);
            node.next.prev = node;
            node = node.next;
        }
        Node tail = node;
        Node target = head.next.next; // the node holding 30
        delete(target);
        StringBuilder forward = new StringBuilder();
        for(Node p = head; p != null; p = p.next) {
            forward.append(p.val);
            if (p.next != null) forward.append(" <-> ");
        }
        System.out.println(forward + " (forward)");
        StringBuilder backward = new StringBuilder();
        for(Node p = tail; p != null; p = p.prev) {
            backward.append(p.val);
            if (p.prev != null) backward.append(" <-> ");
        }
        System.out.println(backward + " (backward)");
    }
}

Watch it run

Step through it

Running on List: 10 <-> 20 <-> 30 <-> 40 <-> 50, delete the node holding 30

Output

Read all 12 Steps

Every node carries two pointers A doubly linked list node stores next and prev. That second pointer costs one word of memory per node and buys the whole lesson: any node can reach its own predecessor.
Why a singly linked list cannot do this Hand a singly linked list the node holding 30 and ask it to delete it. It cannot. Nothing in that node points back to 20, so the only way to find the predecessor is to walk from the head again — O(n).
The node is the whole input Here we are given only the node holding 30. No head, no index, no search. That is exactly the situation an LRU cache is in when it evicts an entry it already has a handle on.
Read node.prev node.prev is the node holding 20. One pointer dereference, no traversal. This single field is what turns an O(n) deletion into an O(1) one.
Read node.next node.next is the node holding 40. Now both neighbours are in hand, and the node in the middle can be spliced out by rewiring just those two.
Pointer 1 of 2: prev.next skips forward node.prev.next = node.next makes 20 point forward to 40. Walk the list from the head now and 30 is already gone — but the backward chain is still broken.
Pointer 2 of 2: next.prev skips backward node.next.prev = node.prev makes 40 point back to 20. This is the step people forget. Skip it and the list looks correct forwards and corrupt backwards — a bug that hides until something traverses from the tail.
The node is now unreachable Two assignments, both O(1). Nothing in the list points at 30 any more, so it can be freed. Deletion needs 2 pointer writes; insertion needs 4, because the new node's own prev and next must be set too.
Forward traversal Following next from the head gives 10, 20, 40, 50. The forward chain is intact.
Backward traversal proves the fix Following prev from the tail gives 50, 40, 20, 10. Both chains agree, which is the only real proof that all the pointers were updated. A one-directional check would have missed a missing prev.
Sentinel nodes remove the null checks Both if statements above exist only to handle deleting the first or last node. Put a dummy head and dummy tail around the real data and every real node is guaranteed to have both neighbours — the two ifs disappear and delete becomes three unconditional lines.
Where this shows up An LRU cache is a hash map plus a doubly linked list: the map finds the node in O(1), and prev lets you unlink and move it to the front in O(1). Neither half works without the other, and the prev pointer is what makes the list half possible.

Application: The LRU Cache

The Least Recently Used cache is the standard application, and it shows exactly why no other structure substitutes. The requirement is to support get and put in O(1) while evicting the least recently used entry when capacity is exceeded — so the cache needs both fast lookup by key and a maintained recency order.

Neither structure alone delivers this. A hash map gives O(1) lookup but stores no order. A doubly linked list maintains order and supports O(1) removal from the middle, but finding a key in it is O(n). The solution combines them: a hash map from key to node reference, plus a doubly linked list ordering nodes from most to least recently used.

On get, the map locates the node in O(1); the node is then unlinked using its own prev and next and reinserted at the front — all O(1), and impossible without the prev pointer. On put past capacity, the node before the tail sentinel is the least recently used, so it is removed and its key deleted from the map, again in O(1).

The same hash-map-plus-doubly-linked-list pairing appears in LinkedHashMap in Java, in collections.OrderedDict in Python, and in operating-system page caches. Browser history and editor undo stacks use the bidirectional traversal directly, stepping backward and forward through the same chain.

Hash map for lookup, doubly linked list for order
Unlink-and-reinsert on access needs the prev pointer
Least recently used sits next to the tail sentinel
Same pattern as Java's LinkedHashMap and OS page caches