Doubly & circular linked lists

In the singly linked lists post, we hit a limitation: you can only go forward. That sounds small, but it creates two very real problems. First, if someone hands you a pointer to a node like 30, you still cannot efficiently delete it, because the link you need to change lives in the previous node. Second, you cannot traverse backward at all. If you overshoot something, you do not get to simply step back one node the way you can with an array index.

That is exactly what doubly linked lists fix. Every node stores not just next, but also prev, so the list can move in both directions and can detach a node in O(1) time once you already have a reference to it.

Circular linked lists solve a different problem. Instead of ending in null, the tail points back to the head. That makes the structure feel like a loop rather than a line, which is perfect for round-robin behavior such as schedulers, repeating playlists, or “keep cycling through all active workers.”

So think of today as two upgrades to the singly linked list idea: one improves local edits, and the other improves cyclic traversal.

Doubly linked list basics

A doubly linked list node stores three things:

1. a value,
2. a pointer to the next node,
3. and a pointer to the previous node.

That one extra pointer changes the feel of the structure completely. In a singly linked list, each node is like a one-way street: you can only drive forward. In a doubly linked list, the street becomes two-way.

For a standard linear doubly linked list:

• the head node has prev = null
• the tail node has next = null
• every middle node has both pointers filled in

Most implementations keep both a head pointer and a tail pointer. That matters because it makes insert-at-front and insert-at-back both fast.

flowchart LR
  N0[null] --> A[10]
  A <--> B[20]
  B <--> C[30]
  C <--> D[40]
  D --> N1[null]

Here is the basic node shape in Python:

class DNode:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

Notice the tradeoff already. Compared with the version from the singly linked list post, we spend more memory per node because every node carries an extra pointer. That is the cost. The payoff is that local updates become much easier.

This is also a good place to remember the lesson from the arrays post: linked lists are flexible because they are pointer-based, not because they are contiguous in memory. The nodes can live anywhere in memory; the pointers are what hold the structure together.

Insertion in a doubly linked list

Insertion rules are easiest if you think in terms of “which pointers must now point at the new node?”

Insert at the head

If the list is 10 ⇄ 20 ⇄ 30 and you want to insert 5 at the front:

• new.next = head
• head.prev = new
• head = new

That is O(1) because no traversal is needed.

Insert at the tail

With a maintained tail pointer, appending 40 to 10 ⇄ 20 ⇄ 30 is also O(1):

• new.prev = tail
• tail.next = new
• tail = new

Without a tail pointer, you would have to walk the whole list first, which would degrade to O(n).

Insert in the middle

Suppose you want to insert 25 between 20 and 30. Once you have navigated to that spot, you need to update four references:

• new.prev = node20
• new.next = node30
• node20.next = new
• node30.prev = new

That sounds fiddly, and it is. Doubly linked lists are more convenient than singly linked lists for deletion, but they also give you more pointers to keep consistent.

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def push_front(self, val):
        node = DNode(val, None, self.head)
        if self.head:
            self.head.prev = node
        else:
            self.tail = node
        self.head = node

    def push_back(self, val):
        node = DNode(val, self.tail, None)
        if self.tail:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node

class DNode {
    int val;
    DNode prev, next;

    DNode(int val) {
        this.val = val;
    }
}

void insertAfter(DNode node, int val) {
    DNode fresh = new DNode(val);
    fresh.prev = node;
    fresh.next = node.next;

    if (node.next != null) {
        node.next.prev = fresh;
    }
    node.next = fresh;
}

The pattern to memorize is simple: in the middle, singly linked lists usually change two links, while doubly linked lists often change four.

Deletion in a doubly linked list

This is the section that makes doubly linked lists worth learning.

In a singly linked list, deleting a node is easy only when you also know the node before it. If all you have is a pointer to node 30, you still need to scan from the head to find 20, because 20.next is the pointer that must change.

In a doubly linked list, the previous node is already sitting right there as node.prev.

If 20 ⇄ 30 ⇄ 40 is the neighborhood around the node you want to remove, the core idea is:

node.prev.next = node.next
node.next.prev = node.prev

That is the killer feature: O(1) deletion given a pointer to the node. No search for the predecessor. No restart from the head.

Of course, edge cases still matter:

• if the node is the head, update head = node.next
• if the node is the tail, update tail = node.prev
• if the list has one node, both head and tail become null

def delete(node, dll):
    if node.prev:
        node.prev.next = node.next
    else:
        dll.head = node.next

    if node.next:
        node.next.prev = node.prev
    else:
        dll.tail = node.prev

void delete(DNode node) {
    if (node.prev != null) {
        node.prev.next = node.next;
    }
    if (node.next != null) {
        node.next.prev = node.prev;
    }
}

This ability to remove or move nodes in constant time is exactly why doubly linked lists show up in LRU caches, browser history, undo/redo systems, and other “move this item to the front/back right now” problems.

LRU cache preview

A Least Recently Used (LRU) cache keeps the most recently touched items near the front and evicts the least recently used item from the back when capacity is full.

To make that fast, we combine two structures:

• a hash map for O(1) lookup by key
• a doubly linked list for O(1) reordering and O(1) tail eviction

Why not use only a hash map? Because a hash map can tell you where key "user:42" lives, but it does not naturally maintain “most recent to least recent” order.

Why not use only a linked list? Because then finding whether key "user:42" exists would take O(n).

The combo works like this:

1. get(key) checks the hash map.
2. If found, move that node to the front of the doubly linked list.
3. put(key, value) either updates an existing node and moves it to the front, or inserts a new node at the front.
4. If capacity is exceeded, evict the tail node and remove its key from the hash map.

flowchart TD
  M["Hash map
key -> node pointer"] --> N1["A"]
  M --> N2["B"]
  M --> N3["C"]

  subgraph LRUOrder["Doubly linked list: most recent -> least recent"]
    N1 --> N2 --> N3
  end

  H["head = most recent"] --> N1
  T["tail = evict here"] --> N3

We will build a full LRU cache later in the series, but the big takeaway today is this: the list is not there for lookup. It is there for cheap removal and cheap reordering.

Circular linked lists

A circular linked list changes one rule: the last node does not point to null. Instead, it points back to the beginning.

So if the values are 5 → 10 → 15 → 20, the tail’s next pointer points back to 5.

That means the structure has no “natural end.” You can keep walking forever:

5 → 10 → 15 → 20 → 5 → 10 → 15 → ...

Circular lists can be:

• singly circular: each node stores only next
• doubly circular: each node stores both prev and next, and both directions loop

The most important rule is traversal. In a normal singly linked list, you stop when the current pointer becomes null. In a circular list, that condition never happens. Instead, you usually stop when you return to the starting node.

def traverse_circular(head):
    if not head:
        return

    current = head
    while True:
        print(current.val)
        current = current.next
        if current == head:
            break

Circular lists are a great example of how one small pointer rule can change the whole personality of a data structure. They are not mainly about easier deletion like doubly linked lists. They are mainly about modeling rotation or repetition.

Use cases for circular lists

The most natural use case is round-robin scheduling. Imagine four workers taking turns:

W1 → W2 → W3 → W4 → W1 → ...

Once a worker finishes its time slice, the scheduler advances to the next node. Operating systems, networking systems, and load balancers often use this “keep cycling through active participants” idea.

Another use case is a circular buffer mindset. We will revisit this in the queues post, but the intuition starts here: instead of thinking “the data ends,” you think “the position wraps.”

A classic interview/math puzzle is the Josephus problem, where people stand in a circle and every k-th person is eliminated. A circular list is a natural structural model because the process keeps looping around the participants.

And there are very everyday examples too. A playlist on repeat is basically circular behavior:

• after the last song, go back to the first song
• no special end-of-list logic required

That is the key design question to ask yourself:

Does this problem feel like a line with an end, or a cycle that should keep repeating?

If it is the second one, a circular structure may be a better mental fit than a normal linked list or even an array.

Complexity comparison

Common mistakes

Practice problems

• LRU Cache (#146) - Medium
• Flatten a Multilevel Doubly Linked List (#430) - Medium
• Design Circular Queue (#622) - Medium
• Insert into a Sorted Circular Linked List (#708) - Medium (Premium)
• Copy List with Random Pointer (#138) - Medium

Key takeaways

1. A doubly linked list adds a prev pointer, which enables backward traversal.
2. If you already have a pointer to a node, deletion in a doubly linked list is O(1).
3. The price of that convenience is extra memory per node and more pointer updates during insertion.
4. A circular linked list replaces the null tail with a link back to the head.
5. Circular traversal needs a new stopping rule: stop when you return to the starting node.
6. Real systems use these structures when they need cheap local edits, recency ordering, or round-robin behavior.

What’s next

Next up: stacks — one of the most important data structures in all of computing, built on top of the linked list (or array) ideas you already know.