A doubly linked list gives each node two pointers — next and prev — so you can traverse in both directions and delete a node in O(1) when you already hold a reference to it (no need to walk from the head to find the predecessor).
A doubly linked list gives each node two pointers — next and prev — so you can traverse in both directions and delete a node in O(1) when you already hold a reference to it (no need to walk from the head to find the predecessor).
null <- [10] <-> [20] <-> [30] -> null
prev/next links in BOTH directions
class Node:
def __init__(self, val):
self.val, self.prev, self.next = val, None, None
def remove(node): # O(1) — no traversal needed
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
In a singly linked list, deleting a node requires finding its predecessor first → O(n).
| Aspect | Singly | Doubly |
|---|---|---|
| Pointers per node | 1 (next) | 2 (next, prev) |
| Traverse backward | no | yes |
| Delete known node | O(n) | O(1) |
| Memory overhead | lower | higher |
The O(1) splice-out of a known node is the key property that makes doubly linked lists the partner of hash maps in an LRU cache.
The extra prev pointer trades memory for the flexibility of bidirectional movement and constant-time deletion.
A library of IT interview questions with detailed answers — from Junior to Senior.
Donate