Circular Linked List

A Circular Linked List is a variation of a linked list where the last node points back to the first node, forming a circular loop.

Key Features

• The last node links to the first node instead of NULL.
• List can be traversed starting from any node, continuously looping through the nodes.
• Useful in applications where wrap-around behavior is needed like buffering and task scheduling.

Types

• Circular Singly Linked List: Each node points to the next node, and the last node points to the first.
• Circular Doubly Linked List: Similar to singly, but nodes have pointers to both next and previous nodes forming a doubly linked circle.

Example of Circular Singly Linked List in Python

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

class CircularLinkedList:
    def __init__(self):
        self.last = None

    def addToEmpty(self, data):
        if self.last is not None:
            return self.last

        newNode = Node(data)
        self.last = newNode
        self.last.next = self.last
        return self.last

    def addFront(self, data):
        if self.last is None:
            return self.addToEmpty(data)

        newNode = Node(data)
        newNode.next = self.last.next
        self.last.next = newNode
        return self.last

    def traverse(self):
        if self.last is None:
            print("List is empty")
            return

        temp = self.last.next
        while True:
            print(temp.data, end=" ")
            temp = temp.next
            if temp == self.last.next:
                break

# Usage
cll = CircularLinkedList()
cll.addToEmpty(5)
cll.addFront(4)
cll.addFront(3)
cll.traverse()  # Output: 3 4 5

This basic example creates and traverses a circular singly linked list in Python.