Lesson 6 of 14

Circular and Doubly Linked Lists

To play the first song after the last, connect the end of a playlist to its beginning. To move directly to the previous song, add a backward link. The links stored in a node determine how you can move.

Circular linked lists

The last node points to the first, forming a cycle such as A → B → C → A. This suits recurring turns or repeat playback.

A loop waiting for None will never stop. Instead, detect a return to the starting node or limit the number of moves. An empty list also needs handling.

Doubly linked lists

Each node stores both next and prev. In A ↔ B ↔ C, B directly reaches either neighbor. The extra reference requires storage, and insertions or deletions must keep both directions consistent.

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

a, b, c = Node("A"), Node("B"), Node("C")
a.next, b.prev = b, a
b.next, c.prev = c, b

# Remove the middle node B.
a.next = c
c.prev = a
b.prev = b.next = None

print(a.next.value)
print(c.prev.value)

The output is C, then A. Moving forward from A and backward from C now gives consistent links. B’s links are cleared to make its removal explicit.

Cases to handle

• Removing the first node requires updating head.
• If you keep a separate reference to the last node, update it when that node is removed.
• A one-node circular list points back to itself.
• Python manages memory reclamation, but the programmer must still update the intended links correctly.

Check your understanding

What happens if you execute a.next = c but forget c.prev = a?