In this article, we will learn about Circular Linked List and its implementation using Python.
A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle.Circular Linked List Implementation in Python
# Python code to perform circular linked list operations
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 != None:
return self.last
# allocate memory to the new node and add data to the node
newNode = Node(data)
# assign last to newNode
self.last = newNode
# create link to iteself
self.last.next = self.last
return self.last
# add node to the front
def addFront(self, data):
# check if the list is empty
if self.last == None:
return self.addToEmpty(data)
# allocate memory to the new node and add data to the node
newNode = Node(data)
# store the address of the current first node in the newNode
newNode.next = self.last.next
# make newNode as last
self.last.next = newNode
return self.last
# add node to the end
def addEnd(self, data):
# check if the node is empty
if self.last == None:
return self.addToEmpty(data)
# allocate memory to the new node and add data to the node
newNode = Node(data)
# store the address of the last node to next of newNode
newNode.next = self.last.next
# point the current last node to the newNode
self.last.next = newNode
# make newNode as the last node
self.last = newNode
return self.last
# insert node after a specific node
def addAfter(self, data, item):
# check if the list is empty
if self.last == None:
return None
newNode = Node(data)
p = self.last.next
while p:
# if the item is found, place newNode after it
if p.data == item:
# make the next of the current node as the next of newNode
newNode.next = p.next
# put newNode to the next of p
p.next = newNode
if p == self.last:
self.last = newNode
return self.last
else:
return self.last
p = p.next
if p == self.last.next:
print(item, "The given node is not present in the list")
break
# delete a node
def deleteNode(self, last, key):
# If linked list is empty
if last == None:
return
# If the list contains only a single node
if (last).data == key and (last).next == last:
last = None
temp = last
d = None
# if last node is to be deleted
if (last).data == key:
# find the node before the last node
while temp.next != last:
temp = temp.next
# point temp node to the next of last i.e. first node
temp.next = (last).next
last = temp.next
# travel to the node to be deleted
while temp.next != last and temp.next.data != key:
temp = temp.next
# if node to be deleted was found
if temp.next.data == key:
d = temp.next
temp.next = d.next
return last
def traverse(self):
if self.last == None:
print("The list is empty")
return
newNode = self.last.next
while newNode:
print(newNode.data, end=" ")
newNode = newNode.next
if newNode == self.last.next:
break
# Driver Code
if __name__ == "__main__":
cll = CircularLinkedList()
last = cll.addToEmpty(6)
last = cll.addEnd(8)
last = cll.addFront(2)
last = cll.addAfter(10, 2)
cll.traverse()
last = cll.deleteNode(last, 8)
print()
cll.traverse()
Output:
2 10 6 8
2 10 6
Related Data Structures in Python
- Stack Implementation in Python
- Queue Implementation in Python
- Deque Implementation in Python
- Singly Linked List Implementation in Python
- Doubly Linked List Implementation in Python
- Circular Linked List Implementation in Python
- PriorityQueue Implementation in Python
- Circular Queue Implementation in Python
- Binary Search Tree Implementation in Python
- Stack Implementation Using Linked List in Python
- Stack Implementation Using Doubly Linked List in Python