Doubly & Circular Linked Lists

What you'll learn

A singly linked list can only move forward. Add a second pointer — prev — and you get a doubly linked list you can traverse both ways and delete from in O(1). Join the ends and you get a circular list with no beginning or end.

By the end you'll be able to:

• Explain what the prev pointer buys you
• Delete a known node in O(1) without tracking the predecessor
• Describe circular lists and where they shine

The prev pointer

Each node now stores two pointers: next and prev. You can walk backward as easily as forward, and every node knows both of its neighbors. The cost is one extra pointer per node and a little more bookkeeping on every insert and delete (you maintain two links instead of one).

O(1) deletion

This is the big win. In a singly list you had to walk from the head to find a node's predecessor before you could unlink it. In a doubly list the node already points to its predecessor, so removal is a pure pointer rewire:

Circular lists

In a circular linked list the last node's next points back to the head (and in a circular doubly list, the head's prev points to the tail). There's no null terminator — you can loop around forever:

In code

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

def delete(node):          # O(1) — no search needed if you hold the node
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev

Where they're used

Recap & quick check

You've mastered chains of nodes. Now we constrain where you can add and remove — and get two of the most useful structures in computing. Next up: Module 7 — Stacks.