[Follow here] for daily coding insights

DSA Series Chapter 9 - CIRCULAR DOUBLY LINKED LIST (CDLL) PYTHON VERSION

1. Node Structure

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

   ┌──────────────┐
   │    Node      │
   ├──────────────┤
   │ data         │
   │ prev  ───────┼───┐

   | next  ───────┼───┘
   └──────────────┘

Explanation

Each node stores:
- data
- prev pointer
- next pointer
In a CDLL:
- head.prev will point to the last node
- last.next will point back to the head

2. Circular Doubly Linked List Class

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

Empty Node

 head
  ↓
 NULL

Explanation

head points to the first node.
If list is empty → head = None.

3. Insert at Beginning

┌──────────────┐

│ data = 10 │

│ prev → self │

│ next → self │

└──────────────┘

↑

head ┘

Meaning:

head = Node(10)
head.next = head
head.prev = head

head

↓

[10] ⇆ (back to itself)

head

↓

┌────────────┐

│ [5] │

└────────────┘

↑ ↓

prev next

│ │

[10] ←─────┘

↑ ↓

└─────────┘

┌─────────┐ ┌─────────┐

head ---> │ 5 │ ---> │ 10 │

└─────────┘ └─────────┘

↑ ↑ ↑ ↑

│ └─────────────┘ │

└────────────────────┘

    def insert_at_beginning(self, data):
        new_node = Node(data)

        if self.head is None:
            new_node.next = new_node.prev = new_node
            self.head = new_node
            return

        last = self.head.prev

        new_node.next = self.head
        new_node.prev = last

        last.next = new_node
        self.head.prev = new_node

        self.head = new_node

Explanation

If list empty → new node points to itself (both ways)
Otherwise:
- Find last node using head.prev
- Update circular backward & forward links
- Move head to new node

4. Insert at End

[5] ⇆ [10]

^ |

|______|

head

↓

[5] ⇆ [10] ⇆ [20]

^ |

|_______________|

┌───────┐ ┌───────┐ ┌────────┐

│ 5 │ --> │ 10 │ --> │ 20 │

└───────┘ └───────┘ └────────┘

↑ ↑ ↑

│ │ │

└─────┴─────┘

    def insert_at_end(self, data):
        new_node = Node(data)

        if self.head is None:
            new_node.next = new_node.prev = new_node
            self.head = new_node
            return

        last = self.head.prev

        last.next = new_node
        new_node.prev = last
        new_node.next = self.head
        self.head.prev = new_node

Explanation

Uses head.prev to directly reach last node (O(1))
Inserts after last and before head
Circular linking preserved

5. Insert at a Given Position

    def insert_at_position(self, data, pos):
        if self.head is None:
            self.insert_at_beginning(data)
            return

        new_node = Node(data)
        temp = self.head
        count = 1

        while count < pos and temp.next != self.head:
            temp = temp.next
            count += 1

        new_node.next = temp.next
        new_node.prev = temp

        temp.next.prev = new_node
        temp.next = new_node

Explanation

Traverse until the desired position
Insert between temp and temp.next
Update both prev and next pointers for circular consistency

6. Delete from Beginning

    def delete_at_beginning(self):
        if self.head is None:
            print("List is empty")
            return

        temp = self.head

        if temp.next == temp:
            self.head = None
            return

        last = temp.prev
        self.head = temp.next

        last.next = self.head
        self.head.prev = last

Explanation

If only one node → head becomes None
Otherwise:
- Move head to second node
- Link last node to new head
- Update new head’s prev

7. Delete from End

    def delete_at_end(self):
        if self.head is None:
            print("List is empty")
            return

        last = self.head.prev

        if last == self.head:
            self.head = None
            return

        second_last = last.prev
        second_last.next = self.head
        self.head.prev = second_last

Explanation

Access last node through head.prev → O(1)
If only one node → remove
Otherwise:
- Link second-last node with head

8. Delete from a Position

    def delete_at_position(self, pos):
        if self.head is None:
            print("List is empty")
            return

        temp = self.head
        count = 1

        while count < pos and temp.next != self.head:
            temp = temp.next
            count += 1

        if temp.next == temp:
            self.head = None
            return

        temp.prev.next = temp.next
        temp.next.prev = temp.prev

        if temp == self.head:
            self.head = temp.next

Explanation

Traverse to the node at the given position
Update its previous node’s next and next node’s prev
If deleted node is head → move head to next node

9. Forward Traversal

    def display_forward(self):
        if self.head is None:
            print("List is empty")
            return

        temp = self.head
        while True:
            print(temp.data, end=" <-> ")
            temp = temp.next
            if temp == self.head:
                break
        print("(Head)")

Explanation

Use loop until we return back to head
Ensures circularity is respected

10. Backward Traversal

    def display_backward(self):
        if self.head is None:
            print("List is empty")
            return

        temp = self.head.prev   # last node
        start = temp

        while True:
            print(temp.data, end=" <-> ")
            temp = temp.prev
            if temp == start:
                break
        print("(Tail)")

Explanation

Start from head.prev (last node)
Move backward using prev links
Stop when we come back to last

11. Complete Working Demo

cdll = CircularDoublyLinkedList()

cdll.insert_at_beginning(10)
cdll.insert_at_end(20)
cdll.insert_at_end(30)
cdll.insert_at_position(15, 1)

print("Forward:")
cdll.display_forward()

print("Backward:")
cdll.display_backward()

cdll.delete_at_position(2)
cdll.display_forward()