Doubly Linked List

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

Insert at head	O(1)
Insert at tail	O(1)
Delete a node you have a reference to	O(1)
Search / access by value	O(n)
Reverse whole list	O(n)

The Idea

Singly Linked List was a one-way scavenger hunt: each clue tells you the next clue's location, but nothing about where you came from. Get to node 5 and you have no way back to node 4 — your only option is to restart from the head and walk forward again. A doubly linked list fixes that by giving every node a second pointer, prev, alongside next. Now each clue also remembers the clue before it, so you can retrace your steps without restarting the hunt.

That second pointer isn't free — every node now carries two addresses instead of one, so the list costs roughly double the pointer memory. What you buy with that cost is backward traversal, and — the real reason doubly linked lists exist — the ability to delete a node you already have a reference to in O(1), with no walk required to find what points at it. Singly Linked List's deleteValue had to walk from the head just to find the node before the target, because that's the only node whose next it could rewrite. Here, the target node already knows its own neighbors.

You're trading memory (a second pointer per node) for two things: walking backward, and O(1) removal of a node in hand. If you never need either, the extra pointer is dead weight — that's exactly why Singly Linked List still exists as the default choice.

Build It

Structures

structure Node:
    value
    next          // -> next Node, or NULL
    prev          // -> previous Node, or NULL

structure DoublyLinkedList:
    head          // -> first Node, or NULL if empty
    tail          // -> last Node, or NULL if empty — kept in sync on every insert/delete

insertAtHead — O(1)

function insertAtHead(list, value):
    newNode = Node(value)
    newNode.next = list.head
    newNode.prev = NULL
    if list.head is not NULL:
        list.head.prev = newNode   // old first node now points back to the new one
    list.head = newNode
    if list.tail is NULL:          // list was empty — new node is head AND tail
        list.tail = newNode

insertAtTail — O(1), thanks to the tail pointer

function insertAtTail(list, value):
    newNode = Node(value)
    newNode.next = NULL
    newNode.prev = list.tail
    if list.tail is not NULL:
        list.tail.next = newNode
    else:                          // list was empty — new node is head AND tail
        list.head = newNode
    list.tail = newNode

Remember Singly Linked List's insertAtTail? It had to walk the whole list just to find the last node. Here the list always keeps a hand on the last node already, so inserting at the tail costs the same one-pointer rewrite as inserting at the head.

deleteNode(node) — O(1), given a direct reference

function deleteNode(list, node):
    if node.prev is not NULL:
        node.prev.next = node.next
    else:
        list.head = node.next      // node was the head
    if node.next is not NULL:
        node.next.prev = node.prev
    else:
        list.tail = node.prev      // node was the tail

This is the whole point of the second pointer. Singly Linked List's deleteValue is O(n) because the only way to unlink a node is to rewrite the next of whatever points at it — and finding that requires walking from head. Here, node.prev and node.next are sitting on the node itself. No search, no walk — just relink two neighbors directly.

reverse — O(n) time, O(1) space

function reverse(list):
    curr = list.head
    while curr is not NULL:
        nextNode = curr.next     // save it before we overwrite curr.next
        curr.next = curr.prev    // flip the forward arrow backward
        curr.prev = nextNode     // flip the backward arrow forward
        curr = nextNode
    oldHead = list.head
    list.head = list.tail
    list.tail = oldHead

Same three-pointer walk as Singly Linked List's reverse, but now there are two arrows to flip per node instead of one. Miss the final head/tail swap and you'll have correctly reversed every node's pointers but still be calling the wrong end 'head.'

Know It

Same rule as Singly Linked List: anything that only touches head or tail is O(1); anything that has to walk to find a spot is O(n). What's different here is which operations get to skip the walk. Deleting a node you already hold a reference to used to force a search for its predecessor — now it doesn't, because the node carries its own neighbors. That upgrade isn't free: every node here pays for two pointers instead of one, so a doubly linked list costs roughly double the pointer memory of a singly linked one for the same values. Don't reach for it if you never need to go backward or delete by reference.

Operation	Time	Space	Why
Insert at head	O(1)	O(1)	Rewrite a few pointers around the new node and the old head. Never touches the rest of the chain.
Insert at tail	O(1)	O(1)	The tail pointer means no walk is needed — contrast Singly Linked List, where this was O(n) without one.
Delete a node you have a reference to	O(1)	O(1)	node.prev and node.next already name the neighbors to relink — no search. Singly Linked List's delete-by-value is O(n) because it must walk from head to find the predecessor first.
Search / access by value	O(n)	O(1)	Still no index to jump to — prev only helps once you're already standing on a node, it doesn't get you to one faster.
Reverse whole list	O(n)	O(1)	Visit each node once, swap its two pointers, move on.

Break It

Empty

head and tail are both NULL

HEAD→NULL

Insert, delete, search, and reverse must all check this first and return cleanly — there's no node to dereference and nothing to relink.

Single node

head == tail, and that one node's next and prev are both NULL

HEAD→3•→NULL

Deleting the only node has to change both head and tail, not just one. The classic bug: code sets head to NULL when the target was deleted but leaves tail pointing at the now-gone node (or the reverse) — the list looks empty from one end and haunted from the other.

Broken pointer symmetry

a node's next is updated without updating the neighbor's prev to match — or vice versa

This is the signature doubly-linked-list bug, and Singly Linked List simply can't have it — with one pointer per link there's only one thing to keep consistent. Here there are two, and they must always agree about the shape of the chain: every next needs a prev pointing back at it. Insert or delete and fix only one direction, and forward traversal can look perfectly fine while backward traversal is silently corrupted (or the reverse) — a bug that can hide for a long time because half your code never walks that way.

Value not found

walking off either end without hitting the target

HEAD→1•→NULL

Now there are two directions to walk off the end of: a forward search must stop on a NULL next, a backward search must stop on a NULL prev. Skipping either check turns a missing value into a crash instead of a clean 'not found.'

Use It

Design Linked List

Implement get/addAtHead/addAtTail/addAtIndex/deleteAtIndex directly on Node{value,next,prev} — a straight-line exercise in the operations above.

Medium

LRU Cache

The flagship real-world use case: a hash map from key to node, plus a doubly linked list for order. Access moves a node to the front in O(1); eviction removes the tail in O(1) — both need the deleteNode trick, not a search.

Medium

Design Browser History

Back and forward are literally walking prev and next from your current position.

Medium

Design Circular Deque

O(1) insert/delete from both ends — the headline benefit of keeping a tail pointer, applied directly.

Medium

Design Circular Queue

Same idea as Circular Deque, queue-shaped: enqueue at tail, dequeue at head, both O(1).

Medium

Flatten a Multilevel Doubly Linked List

Direct prev/next/child pointer surgery — splice each child list in where it branches, then keep prev/next symmetric on the way out.

Medium

Copy List with Random Pointer

Not a doubly linked list itself, but the same discipline: copy nodes carefully while wiring up a second kind of pointer without corrupting the first.

Medium

Palindrome Linked List

Revisit from Singly Linked List: there, checking this required finding the middle and reversing the second half. With prev pointers, you can just walk inward from both head and tail — no reversal needed.

Easy

Reverse Linked List

Revisit from Singly Linked List: same one-pass walk, but now swap both next and prev on every node, per the reverse() pattern above.

Easy

Sort List

Merge sort on a linked list — ties back to Sorting Intuition's merge step, adapted to splice nodes instead of copying into a new array.

Medium