Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 225 ยท Linked Lists

Doubly Linked List

Build a doubly linked list in Python: prev and next pointers, sentinel nodes, O(1) deletion of a node you hold, two-way iteration and complexity.

In a singly linked list every node knows only its successor. That makes some jobs awkward: to delete a node you need the node before it, and the only way to find that node is to walk from the head. Walking backwards is simply impossible.

A doubly linked list fixes this by giving each node two links: next to the following node and prev to the previous one. You pay a little extra memory per node and a little extra care when rewiring pointers. In return, you can walk in both directions, and you can remove a node in O(1) when you already hold a reference to it. That single property is why doubly linked lists sit inside LRU caches, text editors and browser histories.

The picture

flowchart LR
    H["HEAD<br/>(dummy)"] <--> A["10"] <--> B["20"] <--> C["30"] <--> T["TAIL<br/>(dummy)"]

Every node holds a value and two references. If a.next is b, then b.prev is a. This pairing is the invariant of the structure, and almost every bug in doubly linked code is a place where one half of the pair was updated and the other was forgotten.

Notice the two extra boxes labeled dummy at both ends. They are sentinel nodes: fake nodes that hold no real value and exist only so that every real node always has a neighbor on each side.

Why sentinel nodes help

Without sentinels, inserting into an empty list, removing the only node, and removing the first or last node are all special cases, each with its own if node.prev is None branch. With a dummy head and a dummy tail, an empty list looks like this:

TEXT
 head <-> tail

Every real node sits strictly between the two sentinels, so its prev and next are never None. Insert and delete then become the same short routine, no matter where in the list they happen. You trade two nodes of memory for much simpler code, and that is almost always a good trade.

Nodes and the list class

Python Node and an empty list with sentinels

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop condition node is not self.tail replaces the usual while node is not None. Use is, not ==, to compare nodes: you want to ask "is this the very same object?", not "do they look equal?" (see memory and data layout).

The two core operations

Everything else is built from two private helpers.

Insert a new node between two neighbors. Given left and right where left.next is right:

TEXT
before:  left <-> right
after:   left <-> new <-> right

1. new.prev = left
2. new.next = right
3. left.next = new
4. right.prev = new

Set the new node's own pointers first, then rewire the neighbors. If you rewired the neighbors first you could lose a reference you still need.

Unlink a node. Given node, connect its two neighbors to each other:

TEXT
before:  prev <-> node <-> next
after:   prev <-> next

1. node.prev.next = node.next
2. node.next.prev = node.prev

The node is now unreachable from the list. Python's garbage collector will free it once no variable refers to it. We also clear its own pointers, which helps catch bugs where someone keeps using a removed node.

Python Insert and unlink helpers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that append, prepend, pop and pop_left are all one or two lines each. There is no if self.head is None anywhere. That is the sentinel payoff. Also notice that append and prepend return the node. Hand that reference to the caller and they can later delete it in O(1).

O(1) deletion given a node

This is the headline feature. Suppose you stored the node returned by append somewhere (in a dictionary, say). To remove it from a singly linked list you would need its predecessor, which costs O(n) to find. Here, node.prev is the predecessor:

Python Delete a node you already hold

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Removing the first, a middle and the last node all use the identical two lines. That is what sentinels buy you.

Watch out: only call remove_node with a node that is currently in this list, and only once. A node you removed has prev and next set to None, so removing it again raises AttributeError. A real library would verify membership; the O(1) speed comes from trusting the caller.

Insert, find and delete by index

The positional operations still need a walk. Because we can go either way, we can start from the nearer end and roughly halve the worst case:

Python Index-based operations from the nearer end

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Index 1 and index 8 each cost only one move, because they are near an end. Even from the nearer end, an index in the middle costs about n/2 moves in the worst case, which is still O(n). Starting from the nearer end improves the constant, not the growth rate.

Doubly linked list versus the alternatives

Operation Array / list Singly linked Doubly linked
Access by index O(1) O(n) O(n)
Insert/delete at front O(n) O(1) O(1)
Insert/delete at back O(1) amortized O(n), or O(1) for insert with a tail pointer O(1)
Delete a node you hold O(n) O(n) (need predecessor) O(1)
Walk backwards easy impossible easy
Memory per element 1 slot value + 1 pointer value + 2 pointers

Space for the whole list is O(n) in all cases; the doubly linked version just has the biggest constant. Python's own collections.deque is implemented as a linked chain of small blocks, and it already gives you O(1) at both ends. Reach for a hand-built doubly linked list when you need O(1) removal from the middle, which deque cannot do.

A real use: an ordered history

A browser's back and forward buttons are a natural doubly linked structure. This toy version keeps a current node and moves along prev and next:

Python Back and forward history

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will build a version with two stacks in stack applications, and see an O(1) middle-removal use in the linked list problems lesson (LRU cache preview).

Common mistakes

  • Updating only one direction. Writing left.next = node but forgetting right.prev = node leaves a list that looks fine going forward and is broken going backward.
  • Wrong order of assignments. Overwriting left.next before you have saved the old value loses the rest of the list. Set the new node's pointers first.
  • Forgetting size. Keep it in step in exactly two places: the insert helper and the unlink helper.
  • Comparing nodes with ==. Use is for identity.
  • Using a removed node. Clearing prev/next on removal turns silent corruption into a loud error.
  • Skipping sentinels and then special-casing everywhere. If you use None ends instead, test the empty, one-element, first and last cases separately.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a doubly linked list allow that a singly linked list does not?

    Because each node knows its predecessor, you can rewire the neighbors without searching. Index access is still O(n), and the extra prev pointer costs more memory, not less.
  2. 2. What is the purpose of the dummy head and tail (sentinel) nodes?

    Real nodes always sit between the sentinels, so insert and delete use the same code at the front, middle and back.
  3. 3. After inserting new between left and right, which assignments are required?

    Four links change: new.prev, new.next, left.next and right.prev. Skipping any one breaks the invariant that a.next is b implies b.prev is a.
  4. 4. A list holds 100 nodes. Using the nearer-end trick, about how many pointer moves does _node_at(95) need?

    Index 95 is 4 steps from the last node (index 99), so walking backward from the tail takes 4 moves.
  5. 5. When is collections.deque not enough and a custom doubly linked list worthwhile?

    deque is excellent at both ends but removing from the middle is O(n). A linked list with node handles removes in O(1).

Summary

  • A doubly linked list node has value, prev and next; the invariant is that a.next is b exactly when b.prev is a.
  • Sentinel head and tail nodes remove every empty-list and end-of-list special case.
  • Insert and unlink are tiny helpers (four and two assignments); all other operations call them.
  • Deleting a node you already hold is O(1); finding by index or value is O(n), though starting from the nearer end roughly halves the walk.
  • Space is O(n), with two pointers per node.
  • Use it when you need O(1) middle removal or two-way traversal; otherwise a list or deque is simpler and faster in practice.

Next: Circular Linked Lists