How to Create a Circular LinkedList

Question

Can anyone tell me how to create a Circular linked list?

Answer 1

To create a circular linked list in Python, you can define a class to represent the nodes and another class to handle the circular linked list operations. Here's an example implementation:

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

class CircularLinkedList:

    def __init__(self):

        self.head = None

    def append(self, data):

        new_node = Node(data)

        if not self.head:

            self.head = new_node

            new_node.next = self.head

        else:

            current = self.head

            while current.next != self.head:

                current = current.next

            current.next = new_node

            new_node.next = self.head

    def display(self):

        if not self.head:

            print("Circular Linked List is empty.")

            return

        current = self.head

        while True:

            print(current.data, end=" ")

            current = current.next

            if current == self.head:

                break

# Example usage:

circular_list = CircularLinkedList()

circular_list.append(1)

circular_list.append(2)

circular_list.append(3)

circular_list.append(4)

circular_list.display()

In this example, the Node class represents a single node with its data and a reference to the next node. The CircularLinkedList class manages the circular linked list, with methods to append nodes and display the list's contents. The circularity is achieved by connecting the last node's next pointer back to the head node.

You can create a CircularLinkedList object and use the append method to add elements to the list. Finally, you can use the display method to print the circular linked list's contents.

Answer 2

Check the below code for reference:

class Link:

    def __init__(self, data, next):

        self.data = data

        self.next = next

class CircularLinkedList:

    def __init__(self):

        self.head = Link(None, None) # this is the sentinel node!

        self.head.next = self.head   # link it to itself

    def add(self, data):             # no special case code needed for an empty list

        self.head.next = Link(data, self.head.next)

    def __contains__(self, data):    # example algorithm, implements the "in" operator

        current = self.head.next

        while current != self.head:

            if current.data == data: # element found

                return True

            current = current.next

        return False

Looking for a good python tutorial course? Join the python certification course and get certified.

For more details, do check out the below video tutorial...

Answer 3

Here is the following code to create a circular linked list:

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

class CircularLinkedList:

    def __init__(self):

        self.head = None

    def append(self, data):

        new_node = Node(data)

        if not self.head:

            self.head = new_node

            new_node.next = self.head

        else:

            current = self.head

            while current.next != self.head:

                current = current.next

            current.next = new_node

            new_node.next = self.head

    def display(self):

        if not self.head:

            print("Circular Linked List is empty.")

            return

        current = self.head

        while True:

            print(current.data, end=" ")

            current = current.next

            if current == self.head:

                break

# Example usage:

circular_list = CircularLinkedList()

circular_list.append(1)

circular_list.append(2)

circular_list.append(3)

circular_list.append(4)

circular_list.display()

Answer 4

The best-case time complexity for creating a circular linked list is O(1) when the list is empty, and the head node is inserted. Here's the code with the best-case time complexity analysis:

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

class CircularLinkedList:

    def __init__(self):

        self.head = None

    def append(self, data):

        new_node = Node(data)

        if not self.head:

            self.head = new_node

            new_node.next = self.head

        else:

            new_node.next = self.head

            current = self.head

            while current.next != self.head:

                current = current.next

            current.next = new_node

    def display(self):

        if not self.head:

            print("Circular Linked List is empty.")

            return

        current = self.head

        while True:

            print(current.data, end=" ")

            current = current.next

            if current == self.head:

                break

# Example usage:

circular_list = CircularLinkedList()

circular_list.append(1)

circular_list.append(2)

circular_list.append(3)

circular_list.append(4)

circular_list.display()