Doubly & Circular Linked List

A singly linked list has two real limitations: you can only walk forward, and deleting a node requires a separate scan just to find its predecessor. Doubly linked lists fix the first problem by storing a backward reference too; circular linked lists solve a different problem entirely — giving every node a path back to the start, useful for anything that cycles.

Doubly Linked List

Each node now carries two references: next, as before, and prev, pointing back at the node before it. That extra reference is what makes backward traversal and O(1) deletion (given a direct reference to the node) possible — no predecessor scan needed, because the node already knows its own predecessor.

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

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

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

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

    def delete_node(self, node):
        # O(1) given a direct reference to the node - no scan needed, unlike a singly linked list
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.head = node.next  # deleting the head

        if node.next is not None:
            node.next.prev = node.prev
        else:
            self.tail = node.prev  # deleting the tail

insert_at_head / insert_at_tail: Time complexity: O(1) each — maintaining both a head and a tail reference means neither insertion needs a traversal. Space complexity: O(1) — one new node per call.
delete_node: Time complexity: O(1) — given a direct reference to the node (as opposed to searching by value), no traversal is needed at all, because the node already holds pointers to both its neighbors. Space complexity: O(1) — no new memory allocated, just reference updates.

Circular Linked List

A circular linked list is a small structural tweak, usually applied on top of a singly (or doubly) linked list: instead of the last node's next being None, it points back at the head. There is no true "end" to stop at — traversal logic must detect that it has looped back around instead of checking for None.

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

class CircularLinkedList:
    def __init__(self):
        self.tail = None  # keeping tail (not head) makes append O(1)

    def insert_at_tail(self, val):
        node = CNode(val)
        if self.tail is None:
            node.next = node       # single node points to itself
            self.tail = node
        else:
            node.next = self.tail.next  # new node -> old head
            self.tail.next = node       # old tail -> new node
            self.tail = node

    def traverse(self):
        if self.tail is None:
            return []
        values = []
        head = self.tail.next
        curr = head
        while True:
            values.append(curr.val)
            curr = curr.next
            if curr is head:  # stop when we loop back to the start
                break
        return values

insert_at_tail: Time complexity: O(1) — with a tail reference kept, both linking the new node in and updating the "head" (via tail.next) are constant-time reference updates. Space complexity: O(1) — one new node per call.
traverse: Time complexity: O(n) — visits every node exactly once before the loop detects it has returned to its starting node. Space complexity: O(n) for the collected values list (O(1) extra if you process each value immediately instead of collecting it).

Singly vs Doubly vs Circular — When to Pick Each