Doubly Linked Lists

A doubly linked list adds a backward pointer to each node, allowing traversal in both directions and O(1) deletion given only the node.

Two pointers per node

Each node in a doubly linked list stores a value, a next pointer, and a prev pointer. The list keeps both a head and a tail. This symmetry means you can walk forwards or backwards and, crucially, remove a node in O(1) time given only a reference to that node, because you can reach both of its neighbours directly.

Why the back pointer earns its keep

In a singly linked list, deleting a node requires its predecessor, which costs an O(n) search unless you already have it. The prev pointer removes that search. This is why doubly linked lists back structures like LRU caches, where an item must be unlinked from the middle the instant it is accessed.

• Insert or delete given a node: O(1)
• Append at tail: O(1)
• Traverse forward or backward: O(n)
• Access k-th element: O(k)

Sentinel nodes

A common implementation trick uses two dummy sentinel nodes for head and tail. Every real node then always has a non-null neighbour on both sides, so insertion and deletion code needs no special cases for the ends. This eliminates a whole class of null-pointer bugs at the cost of two extra nodes.

def remove(node):
    node.prev.next = node.next
    node.next.prev = node.prev
    # node is now unlinked in O(1)

Cost of the extra pointer

Every node carries an additional pointer, so memory overhead per element roughly doubles the pointer cost, and every insertion or deletion must maintain two links instead of one. When you only ever traverse in one direction and never delete from the middle, a singly linked list is leaner.