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.

A linked list in which the first and last nodes are interconnected, the last node linking 'back' to the head

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

AI Code Explainer

Paste any Python code below and get a plain-English explanation.