18-2. Circular Linked Lists

A circular linked list is a variant of a linked list where the first and last nodes are interconnected, creating a loop or circle within the list structure.

The next node of the last node is indicating to the first node.

Circular Linked List Implementation

class CircularLinkedList:
    def __init__(self):
        self.__head = None
        self.__tail = None
        self.__size = 0

def getFirst(self):
        if self.__size == 0:
            return None
        else:
            return self.__head.element

def getLast(self):
        if self.__size == 0:
            return None
        else:
            return self.__tail.element

def addFirst(self, e):
        newNode = Node(e)
        if self.__size == 0:
            self.__head = self.__tail = newNode
            self.__tail.next = self.__head
        else:
            newNode.next = self.__head
            self.__head = newNode
            self.__tail.next = self.__head
        self.__size += 1

def addLast(self, e):
        newNode = Node(e)
        if self.__size == 0:
            self.__head = self.__tail = newNode
            self.__tail.next = self.__head
        else:
            self.__tail.next = newNode
            self.__tail = newNode
            self.__tail.next = self.__head
        self.__size += 1

def insert(self, index, e):
        if index == 0:
            self.addFirst(e)
        elif index >= self.__size:
            self.addLast(e)
        else:
            current = self.__head
            for i in range(1, index):
                current = current.next
            newNode = Node(e)
            newNode.next = current.next
            current.next = newNode
            self.__size += 1

def removeFirst(self):
        if self.__size == 0:
            return None
        else:
            temp = self.__head
            self.__head = self.__head.next
            self.__tail.next = self.__head
            self.__size -= 1
            if self.__size == 0:
                self.__tail = None
            return temp.element

def removeLast(self):
        if self.__size == 0:
            return None
        elif self.__size == 1:
            temp = self.__head
            self.__head = self.__tail = None
            self.__size = 0
            return temp.element
        else:
            current = self.__head
            for i in range(self.__size - 2):
                current = current.next
            temp = self.__tail
            self.__tail = current
            self.__tail.next = self.__head
            self.__size -= 1
            return temp.element

def removeAt(self, index):
        if index < 0 or index >= self.__size:
            return None
        elif index == 0:
            return self.removeFirst()
        elif index == self.__size - 1:
            return self.removeLast()
        else:
            previous = self.__head
            for i in range(1, index):
                previous = previous.next
            current = previous.next
            previous.next = current.next
            self.__size -= 1
            return current.element

def isEmpty(self):
        return self.__size == 0

def getSize(self):
        return self.__size

def __str__(self):
        result = "["
        current = self.__head
        for i in range(self.__size):
            result += str(current.element)
            current = current.next
            if current != self.__head:
                result += ", "
            else:
                result += "]"
        return result

def clear(self):
        self.__head = self.__tail = None
        self.__size = 0

def __iter__(self):
        return CircularLinkedListIterator(self.__head)

# The Node class
class Node:
    def __init__(self, e):
        self.element = e
        self.next = None

class CircularLinkedListIterator:
    def __init__(self, head):
        self.current = head

def __next__(self):
        if self.current is None:
            raise StopIteration
        else:
            element = self.current.element
            self.current = self.current.next
            return element

Last updated: April 23, 2025

Python Programming

18-2. Circular Linked Lists