The Project | About Us | Contribute | Donations | License

HOME

The singly linked list we built in the previous lesson has an awkward asymmetry: each node knows who comes after it, but is completely unaware of who comes before. That blindness forced us into the two-reference dance (prev and current) to remove, and makes traversing the list backward outright impossible. In this lesson we add the missing arrow: each node will carry two references, prev and next, and we will obtain the doubly linked list, with O(1) removals and insertions when we already hold the node in hand and traversals in both directions. The price, as always, exists and we will put it on the scales. For TaskFlow, this structure is the perfect piece for a navigable task history: moving forward and backward through the tasks you've worked on, like a browser's "back" and "forward" buttons.

The double node: two arrows per node
Head and tail: the structure and its invariants
Inserting at both ends
Inserting and removing in O(1) given the node
Traversing in both directions
Singly vs doubly linked: the full balance
TaskFlow: the navigable task history
A bridge to collections.deque

The double node: two arrows per node

The modification is small to write and big in its consequences:

class DoubleNode:
    """A data item and two references: to the previous node and to the next."""
    def __init__(self, data):
        self.data = data
        self.prev = None    # reference to the previous node (None = it is the first)
        self.next = None    # reference to the following node (None = it is the last)

graph LR
    H[head] --> A
    A["task 1"] -- next --> B["task 2"]
    B -- prev --> A
    B -- next --> C["task 3"]
    C -- prev --> B
    T[tail] --> C

Each pair of neighboring nodes is joined by two arrows, one in each direction. From that follow the two new properties:

From any node you can walk backward (current = current.prev), not just forward.
Any node knows its previous neighbor without searching for it: the previous-node pattern from 02-02 stops being necessary.

And the new burden: every operation must keep twice as many arrows consistent. Where the singly linked list rewired 2 references, the doubly linked one rewires up to 4. No operation changes cost class because of it (rewiring is still O(1)), but the code has more places to get wrong, and we will see them.

Head and tail: the structure and its invariants

class DoublyLinkedList:
    """Doubly linked list: traversable in both directions."""
    def __init__(self):
        self.head = None    # first node
        self.tail = None    # last node
        self.size = 0

In the singly linked list, the tail was an optional trick to make insert_back cheap. Here it is an essential part of the design: without it there would be nowhere to start the backward traversal from. It is worth putting the invariants in writing — the conditions every method must leave true when it finishes:

self.head.prev is always None (nothing precedes the first).
self.tail.next is always None (nothing follows the last).
If the list is empty, head and tail are both None; if it has one element, both point to the same node.
For every interior node n: n.next.prev is n and n.prev.next is n (the outbound and return arrows match).

When a method leaves the arrows inconsistent, the symptoms appear far from the culprit (a backward traversal that gets cut short, a removal that resurrects nodes). Mentally checking the invariants after writing each method is the best insurance.

Inserting at both ends

The structure's symmetry shows in the code: the two methods are mirror images of each other.

    def insert_front(self, data):
        """Cost: O(1)."""
        new_node = DoubleNode(data)
        if self.head is None:            # empty list
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head        # 1: the new node looks at the old first
            self.head.prev = new_node        # 2: the old first looks back at the new one
            self.head = new_node             # 3: the head moves
        self.size += 1

    def insert_back(self, data):
        """Cost: O(1)."""
        new_node = DoubleNode(data)
        if self.tail is None:            # empty list
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail        # exact mirror of the previous method
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

Look at step 2 of insert_front, which did not exist in the singly linked list: the old first node must return the gaze to the new one (self.head.prev = new_node). It is the extra assignment that maintains the matched-arrows invariant. Forgetting it doesn't break the forward traversal — the bug lies in ambush — but it cuts the backward traversal at exactly that point: the kind of silent error that is hardest to debug.

Inserting and removing in O(1) given the node

Here is the lesson's headline, and it must be read with its fine print: holding a reference to the node, removing it (or inserting next to it) is pure O(1), without walking the list or searching for the previous node — the node already carries it along.

    def remove_node(self, node):
        """Unhooks the given node. Cost: O(1) — no searching, just rewiring."""
        if node.prev is not None:
            node.prev.next = node.next       # forward bridge
        else:
            self.head = node.next            # it was the first
        if node.next is not None:
            node.next.prev = node.prev       # backward bridge
        else:
            self.tail = node.prev            # it was the last
        node.prev = None      # hygiene: the loose node doesn't hold onto the list
        node.next = None
        self.size -= 1
        return node.data

    def insert_after(self, node, data):
        """Inserts a data item right after the given node. Cost: O(1)."""
        if node is self.tail:
            self.insert_back(data)
            return
        new_node = DoubleNode(data)
        new_node.prev = node                  # 1: the new node looks both ways
        new_node.next = node.next
        node.next.prev = new_node             # 2: the neighbors return the gaze
        node.next = new_node
        self.size += 1

graph LR
    A["prev"] -- "next bridge" --> C["next"]
    C -- "prev bridge" --> A
    A -.-> B["removed node"]
    B -.-> C

Details that make the difference:

remove_node builds two bridges, one per direction, and each has its edge case (first/last). Four branches, all necessary.
The two "hygiene" lines (node.prev = None, etc.) prevent an already-removed node from still holding references into the living list — and, along the way, prevent anyone from using it as the starting point of a ghost traversal.
Compare with the singly linked list: there, removing required having arrived with the prev/current pair (an O(n) prior search except at the head). Here, if you kept the reference to the node (for instance, the history node where you are standing), the removal is instantaneous. The advantage only materializes if you keep references to nodes; if you always start searching from the head, the doubly linked list does not spare you the O(n) search.

Traversing in both directions

    def __iter__(self):
        """Forward traversal: for data in my_list. Cost: O(n)."""
        current = self.head
        while current is not None:
            yield current.data
            current = current.next

    def __reversed__(self):
        """Backward traversal: for data in reversed(my_list). Cost: O(n)."""
        current = self.tail
        while current is not None:
            yield current.data
            current = current.prev

    def __len__(self):
        return self.size

    def __str__(self):
        parts = [f'[{d["id"]}:{d["title"]}]' if isinstance(d, dict) and "title" in d
                 else f"[{d}]" for d in self]
        return " <-> ".join(parts) if parts else "(empty)"

__reversed__ is the magic method Python invokes when you write reversed(my_list): we start at the tail and walk along the prev arrows. In the singly linked list this method was simply impossible to write at a reasonable cost (you would have to re-hunt each node's predecessor, O(n²), or copy the whole list). The <-> separator in __str__ is a reminder that the arrows now run in both directions.

Singly vs doubly linked: the full balance

Criterion	Singly linked list	Doubly linked list
References per node	1 (`next`)	2 (`prev` and `next`)
Extra memory per node	One arrow	Two arrows (~30-50% more overhead per node)
Forward traversal	O(n)	O(n)
Backward traversal	Impractical	O(n)
Remove holding the node	O(n) — must locate the previous one	O(1)
Insert next to a given node	O(1) only after; before requires searching	O(1) on both sides
Insert/remove at the ends	O(1) (with a tail)	O(1)
Arrows to maintain per operation	2	Up to 4 (plus edge cases)
Code complexity	Lower	Higher (more points of failure)

When to choose each one?

Singly linked: when you only move in one direction and modifications concentrate at the ends or during a forward traversal. Less memory, less code, fewer possible errors.
Doubly linked: when you need to navigate backward, or to remove/move elements based on saved references to their nodes. The history coming up next is the canonical case.

TaskFlow: the navigable task history

Every time a team member opens a task, TaskFlow records it in their history. The user wants to move through that history like through a browser's pages: back and forward. With the doubly linked list, the history is the structure and the current position is simply a reference to a node:

class TaskHistory:
    """Navigable history of visited tasks, on a doubly linked list."""
    def __init__(self):
        self.tasks = DoublyLinkedList()
        self.current = None                   # node where we are standing

    def visit(self, task):
        """The user opens a task: record it at the end and stand on it."""
        self.tasks.insert_back(task)
        self.current = self.tasks.tail        # the freshly created node

    def back(self):
        """Steps back one position, if possible. Cost: O(1)."""
        if self.current is not None and self.current.prev is not None:
            self.current = self.current.prev
        return self.current.data if self.current else None

    def forward(self):
        """Steps forward one position, if possible. Cost: O(1)."""
        if self.current is not None and self.current.next is not None:
            self.current = self.current.next
        return self.current.data if self.current else None


history = TaskHistory()
history.visit({"id": 1, "title": "Design logo", "priority": 2, "status": "in_progress"})
history.visit({"id": 2, "title": "Configure server", "priority": 2, "status": "in_progress"})
history.visit({"id": 3, "title": "Production hotfix", "priority": 1, "status": "in_progress"})

print(history.back()["title"])      # Configure server
print(history.back()["title"])      # Design logo
print(history.forward()["title"])   # Configure server

Points to savor:

back() and forward() are pure O(1): moving one reference along one arrow. With a singly linked list, back() would have required walking from the head to the previous node — O(n) per button press.
self.current is the embodiment of "the advantage only counts if you keep references to nodes": the history lives precisely off keeping one.
The chained is not None checks guard against both an empty history and falling off the ends: at the first and last task, the buttons simply don't move.

In 02-05 you will complete this history with a classic browser nuance: what happens to the "forward" tasks when you visit a new one from the middle of the history.

A bridge to `collections.deque`

In module 1 the mention of collections.deque was planted, and now you can understand its identity card: deque is implemented in C as a doubly linked structure of blocks — not one node per element, but nodes that are blocks of 64 slots linked to each other in both directions. That hybridization gives it O(1) insertions and removals at both ends with much less memory overhead per element than our handcrafted doubly linked list. It is Python's professional answer to the "enter and leave at both ends" pattern, and it will star in module 4 when we build queues and deques; here it is enough to know that it exists and that, on the inside, it is a direct relative of what you just programmed.

Common Mistakes and Tips

Updating one arrow and forgetting the return one. The star mistake: after a.next = b, b.prev = a is almost always missing. The symptom is treacherous because the forward traversal works and the failure only surfaces when going backward. Verify every method against the invariant n.next.prev is n.
The four edge cases of remove_node. First, last, only element, and interior node touch different branches. Removing the only node must leave head and tail at None at the same time; always test that case.
Using an already-removed node. If you kept a reference to a node and someone later removed it, your arrows point into the void (or at None, thanks to the method's hygiene). In designs with live references, define who is responsible for invalidating them — as TaskHistory does by moving self.current only through its own methods.
Paying for the doubly linked list without using it. If your code never traverses backward or keeps references to nodes, you are paying an extra arrow per node and twice the rewirings in exchange for nothing: go back to the singly linked list. Choosing the minimal sufficient structure is optimizing too.
Tip: when debugging, print the list in both directions (list(my_list) and list(reversed(my_list))) and compare: they must be exact reverses. If they are not, some prev arrow has been betrayed, and the point where they diverge tells you which one.

Exercises

Exercise 1 — find_node and removal by id. Add to DoublyLinkedList a method find_node(condition) that returns the node (not the data) meeting the condition, or None. Use it together with remove_node to delete the task with id 2 from the history. What is the total cost of the combined operation, and where is it concentrated?

Exercise 2 — insert_before. Write the method insert_before(node, data), symmetric to insert_after, with O(1) cost. Careful with the case where node is the head. Verify with an example that the invariants hold by printing the list in both directions.

Exercise 3 — Detecting the betrayed arrow. Write a function check_invariants(lst) that returns True if the list satisfies the lesson's invariants (head with no prev, tail with no next, and matched arrows at every node) and False otherwise. Then deliberately break a prev arrow of a test list and confirm that check_invariants detects it.

Solutions

Solution 1:

    def find_node(self, condition):
        """Returns the first NODE whose data meets the condition. Cost: O(n)."""
        current = self.head
        while current is not None:
            if condition(current.data):
                return current
            current = current.next
        return None

# Combined operation:
node = history.tasks.find_node(lambda t: t["id"] == 2)   # O(n)
if node is not None:
    if history.current is node:                # don't leave 'current' dangling
        history.current = node.prev or node.next
    history.tasks.remove_node(node)            # O(1)

The total cost is O(n), but all of it lies in the search; the removal itself is O(1). This separation is the lesson's moral: the doubly linked list makes modifying cheap, not finding. To make finding cheap we will need the index by id from module 5 — which, combined with this list (a dict of id → node), will yield total removals in O(1). Note the detail of relocating history.current if it stood on the removed node: it is the "using an already-removed node" mistake cut off at the root.

Solution 2:

    def insert_before(self, node, data):
        """Inserts a data item right before the given node. Cost: O(1)."""
        if node is self.head:
            self.insert_front(data)
            return
        new_node = DoubleNode(data)
        new_node.next = node                  # the new node looks both ways
        new_node.prev = node.prev
        node.prev.next = new_node             # the neighbors return the gaze
        node.prev = new_node
        self.size += 1

# Invariant check:
lst = DoublyLinkedList()
for x in ("A", "B", "D"):
    lst.insert_back(x)
node_d = lst.find_node(lambda d: d == "D")
lst.insert_before(node_d, "C")
print(list(lst))             # ['A', 'B', 'C', 'D']
print(list(reversed(lst)))   # ['D', 'C', 'B', 'A']  ← exact reverse: healthy arrows

The order of the four assignments follows the usual rule, extended: first the new node looks both ways, then the neighbors return the gaze. And within the second part, node.prev.next = new_node must come before node.prev = new_node, because the first line still needs the old value of node.prev.

Solution 3:

def check_invariants(lst):
    """Checks the doubly linked list's invariants. Cost: O(n)."""
    if lst.head is None or lst.tail is None:
        return lst.head is None and lst.tail is None   # empty: both at None
    if lst.head.prev is not None or lst.tail.next is not None:
        return False
    current = lst.head
    while current.next is not None:
        if current.next.prev is not current:   # is the return arrow correct?
            return False
        current = current.next
    return current is lst.tail    # the walk must end exactly at the tail

# Controlled sabotage:
lst = DoublyLinkedList()
for x in (1, 2, 3):
    lst.insert_back(x)
print(check_invariants(lst))            # True
lst.head.next.prev = None    # we break a return arrow
print(check_invariants(lst))            # False

We check the arrows with is (node identity, not data equality) and finish by verifying that the walk dies at lst.tail — that way we also catch ghost tails. A function like this, called after every operation in your tests, turns silent arrow errors into loud, immediate failures: exactly what you want while developing.

Conclusion

With a second arrow per node, the doubly linked list removes the singly linked one's two limitations: you can now traverse backward (__reversed__ from the tail) and, holding the node, removing or inserting beside it is O(1) without searching for anyone — in exchange for more memory per node and up to four arrows to keep consistent on every operation, with their invariants and their edge cases. TaskFlow's navigable history showed where it shines: back() and forward() as simple movements of one reference. And collections.deque was introduced as the professional, hybrid version of this idea, waiting for us in module 4. Now then, all our lists — singly or doubly linked — share one trait: they have an end, that None that stops the traversals. In the next lesson we will remove it deliberately: we will make the last node point to the first and obtain circular lists, perfect for rotating turns — in TaskFlow, the cyclic distribution of tasks among team members — as long as we learn to traverse them without falling into the infinite loop.

Doubly Linked Lists

Contents

The double node: two arrows per node

Head and tail: the structure and its invariants

Inserting at both ends

Inserting and removing in O(1) given the node

Traversing in both directions

Singly vs doubly linked: the full balance

TaskFlow: the navigable task history

A bridge to `collections.deque`

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

Doubly Linked Lists

Contents

The double node: two arrows per node

Head and tail: the structure and its invariants

Inserting at both ends

Inserting and removing in O(1) given the node

Traversing in both directions

Singly vs doubly linked: the full balance

TaskFlow: the navigable task history

A bridge to collections.deque

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

A bridge to `collections.deque`