Circular Linked List Implementation in Python

Introduction

A circular linked list is a variation of a singly linked list where the last node points back to the first node instead of having a None reference. This forms a circular structure, allowing for continuous traversal.

In this article, we will implement a circular linked list in Python using a linked list data structure.

Python Implementation of Circular Linked List

# Circular linked list using linked list in Python

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

# Function to insert a new node at the beginning of the list
def push(head, data):
    if not head:
        return Node(data)
    
    newNode = Node(data)
    newNode.next = head
    head = newNode
    return head

# Function to convert singly linked list into circular linked list
def circular(head):
    start = head
    
    while head.next is not None:
        head = head.next
    
    head.next = start  # Connecting last node to first node
    return start

# Function to display elements of the circular linked list
def displayList(node):
    start = node
    while node.next is not start:
        print("{} ".format(node.data), end="")
        node = node.next
    print("{} ".format(node.data), end="")

# Driver Code
if __name__ == '__main__':
    # Initialize an empty list
    head = None

    head = push(head, 15)
    head = push(head, 14)
    head = push(head, 13)
    head = push(head, 22)
    head = push(head, 17)

    # Convert the list into a circular linked list
    circular(head)
    
    print("Display List:")
    displayList(head)

Explanation of Code

1. Node Class: Defines the structure of a linked list node, consisting of data and next pointer.
2. push() Function: Inserts a new node at the beginning of the list.
3. circular() Function: Converts a singly linked list into a circular linked list by pointing the last node to the first node.
4. displayList() Function: Traverses and prints the elements of the circular linked list.
5. Driver Code: Creates a circular linked list with sample values and displays the elements.

Output

Display List:
17 22 13 14 15

Advantages of Circular Linked List

• Efficient Traversal: Can continuously loop through elements without worrying about reaching the end.
• Better Performance: Useful in applications like buffering, scheduling, and multiplayer games.
• Simplified Operations: Deletion and insertion operations are often easier than in singly linked lists.

Conclusion

A circular linked list is a useful data structure in various real-world applications. Python makes it simple to implement using classes and pointers. This article covered creating, converting, and displaying a circular linked list.