DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Basics

Advanced

Circular Doubly Linked List

The most powerful linked list variant — bidirectional pointers in a closed ring. No NULL anywhere. Used in LRU caches and the Linux kernel.

Circular Ring

Bidirectional

No NULL Pointers

Circular Doubly Linked List

Prev ← and next → pointers are both circular. head.prev = tail, tail.next = head.

Color Legend

DefaultTraversingTarget foundComplete

Speed:

List is empty — insert to begin

Size

–

HEAD

–

TAIL

Insert, delete, search, or traverse forward/backward to explore this ring structure.

Complexity

O(1)

Insert Head / Tail

O(n)

Insert at Index

O(1)

Delete (with ptr)

O(n)

Search by Value

O(n) Space

n nodes × (value + prev ptr + next ptr)

Structural Invariants

tail.next = head

Forward direction is circular — no NULL at the end

head.prev = tail

Backward direction is circular — no NULL at the start

Single node

node.prev = node.next = itself — a ring of one

4 updates always

Every insert/delete updates prev and next on both sides

Real-World Uses

LRU Cache

Move recently used node to head in O(1) — doubly for delete, circular for wrap-around

Linux kernel list_head

The kernel's generic linked list macro used in thousands of subsystems

Text editor cursor

Vim's undo ring — navigate forward/backward through infinite history

Browser tab cycling

Ctrl+Tab wraps from last tab back to first seamlessly

Test Yourself

Q1/3

In a circular doubly linked list, what do head.prev and tail.next point to?

Python Implementation

Python

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

class CircularDoublyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    @property
    def tail(self):
        return self.head.prev if self.head else None

    def insert_head(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            node.prev = node.next = node  # self-loop
            self.head = node
        else:
            tail = self.head.prev
            node.next = self.head
            node.prev = tail
            self.head.prev = node        # 4 pointer updates
            tail.next = node
            self.head = node
        self.size += 1

    def insert_tail(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            node.prev = node.next = node
            self.head = node
        else:
            tail = self.head.prev
            node.next = self.head
            node.prev = tail
            tail.next = node
            self.head.prev = node        # head.prev = new tail
        self.size += 1

    def delete(self, node):              # O(1) with pointer
        if self.size == 1:
            self.head = None
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
            if node == self.head:
                self.head = node.next
        self.size -= 1

    def traverse_forward(self):          # O(n)
        if not self.head: return
        cur = self.head
        while True:
            yield cur.value
            cur = cur.next
            if cur == self.head: break

    def traverse_backward(self):         # O(n)
        if not self.head: return
        cur = self.head.prev             # start from tail
        while True:
            yield cur.value
            cur = cur.prev
            if cur == self.head.prev: break

DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

Back to Basics

Advanced

Circular Doubly Linked List

The most powerful linked list variant — bidirectional pointers in a closed ring. No NULL anywhere. Used in LRU caches and the Linux kernel.

Circular Ring

Bidirectional

No NULL Pointers

Circular Doubly Linked List

Prev ← and next → pointers are both circular. head.prev = tail, tail.next = head.

Color Legend

DefaultTraversingTarget foundComplete

Speed:

List is empty — insert to begin

Size

–

HEAD

–

TAIL

Insert, delete, search, or traverse forward/backward to explore this ring structure.

Complexity

O(1)

Insert Head / Tail

O(n)

Insert at Index

O(1)

Delete (with ptr)

O(n)

Search by Value

O(n) Space

n nodes × (value + prev ptr + next ptr)

Structural Invariants

tail.next = head

Forward direction is circular — no NULL at the end

head.prev = tail

Backward direction is circular — no NULL at the start

Single node

node.prev = node.next = itself — a ring of one

4 updates always

Every insert/delete updates prev and next on both sides

Real-World Uses

LRU Cache

Move recently used node to head in O(1) — doubly for delete, circular for wrap-around

Linux kernel list_head

The kernel's generic linked list macro used in thousands of subsystems

Text editor cursor

Vim's undo ring — navigate forward/backward through infinite history

Browser tab cycling

Ctrl+Tab wraps from last tab back to first seamlessly

Test Yourself

Q1/3

In a circular doubly linked list, what do head.prev and tail.next point to?

Python Implementation

Python

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

class CircularDoublyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    @property
    def tail(self):
        return self.head.prev if self.head else None

    def insert_head(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            node.prev = node.next = node  # self-loop
            self.head = node
        else:
            tail = self.head.prev
            node.next = self.head
            node.prev = tail
            self.head.prev = node        # 4 pointer updates
            tail.next = node
            self.head = node
        self.size += 1

    def insert_tail(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            node.prev = node.next = node
            self.head = node
        else:
            tail = self.head.prev
            node.next = self.head
            node.prev = tail
            tail.next = node
            self.head.prev = node        # head.prev = new tail
        self.size += 1

    def delete(self, node):              # O(1) with pointer
        if self.size == 1:
            self.head = None
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
            if node == self.head:
                self.head = node.next
        self.size -= 1

    def traverse_forward(self):          # O(n)
        if not self.head: return
        cur = self.head
        while True:
            yield cur.value
            cur = cur.next
            if cur == self.head: break

    def traverse_backward(self):         # O(n)
        if not self.head: return
        cur = self.head.prev             # start from tail
        while True:
            yield cur.value
            cur = cur.prev
            if cur == self.head.prev: break