Insertion at End in Circular Linked List in Python(Naïve and Optimized Approach)

November 2, 2023

Insertion at Beginning in Circular Linked List in Python

In the realm of data structures, linked lists are fundamental. Among them, circular linked lists present a unique twist. They not only have the standard features of a singly linked list but also form a closed loop.

In this page, we will explore how to perform insertion at end in circular linked list using Python. We will cover different scenarios and techniques for inserting elements in terms of Naïve Approach and Optimized Approach.

What is a Circular Linked List? A circular linked list is a type of data structure used in computer programming and data management. It is similar to a regular singly linked list, but with one key difference: in a circular linked list, the last node points back to the first node, forming a closed loop.

Understanding Circular Linked List Insertion

Linked lists are fundamental data structures, but circular linked lists add an extra layer of complexity and versatility. Inserting a node at the beginning of a circular linked list may seem straightforward at first glance, but there are multiple ways to achieve this, each with its own advantages and drawbacks.

In a circular linked list, the last node is connected to the first node, forming a closed loop. This unique structure allows for efficient traversal and certain operations, making it particularly useful in specific scenarios.

Circular Linked List Algorithm :

Initialize: Create a structure for the linked list node, including data and a pointer to the next node.
Create an Empty Circular Linked List: Initialize a pointer, say head, to NULL to represent an empty list.
Insertion at the End (Naïve Approach) :
- To insert a node at the end of the circular linked list (naïve approach):
  - Create a new ‘Node’ with the desired data.
  - Traverse the list from the head until you find the last node (the node whose ‘next’ pointer points back to the head).
  - Make the last node’s ‘next’ pointer point to the new node.
  - Update the new node’s ‘next’ pointer to point back to the head to complete the circular structure.
Insertion at the End (Optimized Approach) :
- To insert a node at the end of the circular linked list (optimized approach):
  - Create a new ‘Node’ with the desired data.
  - If the list is empty (head is ‘None’), set the head to the new node and make it point to itself. Also, set the ‘last’ pointer to the new node.
  - Otherwise, make the new node’s next pointer point to the head.
  - Update the ‘next’ pointer of the ‘last’ node to point to the new node.
  - Update the ‘last’ pointer to the newly inserted node.

Circular Linked List Insertion at End in Python

For each Insertion operation, we need to consider the two cases.

Naïve Approach
Optimized Approach

Naïve Approach for Insertion at Beginning in Circular Linked List

The Naïve Approach to insert a node at the end of a circular linked list. This method involves traversing the entire list to find the last node and then making it point to the new node.

Step 1: Traversal

Start at the head of the list.
Move through the list until you reach the last node. (You can determine this when the next node is the head itself.)
Once you’ve found the last node, proceed to the next step.

Step 2: Insertion

Create a new node with the data you want to insert.
Make the last node’s next pointer point to the new node.
Finally, update the new node’s next pointer to point back to the head, thus completing the circular structure.

Implementation of Circular Linked List in Python(Naïve Approach) :

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_end_naive(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:
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
            print(current.data)
            
# Example usage:
clist = CircularLinkedList()
clist.insert_at_end_naive(1)
clist.insert_at_end_naive(2)
clist.insert_at_end_naive(3)

print("Circular Linked List:")
clist.display()

Optimized Approach for Insertion at Beginning in Circular Linked List

In Optimized Approach, Instead of traversing the entire list to find the last node, we can maintain a pointer to the last node and directly insert the new node.

Step 1: Initialization

Initially, we set a pointer called last to the head of the list.

Step 2: Insertion

Create a new node with the data you want to insert.
Make the new node’s next pointer point to the head of the list.
Update the next pointer of the last node to point to the new node
Finally, move the last pointer to the newly inserted node.

Implementation of Circular Linked List in Python(Optimized Approach) :

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

class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.last = None

    def insert_at_end_optimized(self, data):
        new_node = Node(data)
        
        if not self.head:
            self.head = new_node
            self.head.next = self.head
            self.last = self.head
        else:
            new_node.next = self.head
            self.last.next = new_node
            self.last = new_node

    def display(self):
        if not self.head:
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
            print(current.data)

# Example usage:
clist = CircularLinkedList()
clist.insert_at_end_optimized(1)
clist.insert_at_end_optimized(2)
clist.insert_at_end_optimized(3)

print("Circular Linked List:")
clist.display()

Time and Space Complexity

Naïve Approach:

Time Complexity: O(n) (Due to traversal)

Space Complexity: O(1)

Optimized Approach:

Time Complexity: O(1)

Space Complexity: O(1)

Advantages of Circular Linked Lists :

Efficient traversal.

Suitable for applications involving a circular arrangement of data.

Simplifies certain problems like the "Josephus Problem."

Disadvantages of Circular Linked Lists :

Increased complexity in insertion and deletion operations.

More challenging to implement correctly than singly linked lists.

Not as commonly used as other data structures like arrays or singly linked lists.

Conclusion

In this page, we have discussed about concept of “Insertion at End in Circular Linked Lists in Python” using both naïve and optimized approaches. While the naïve approach is simple to understand, the optimized approach offers improved efficiency with constant time complexity. Understanding the nuances of circular linked lists and their insertion methods can be invaluable in solving various programming challenges.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Most Frequently Asked Questions and Answers

Question 1.

What is a circular linked list?

Explanation

A circular linked list is a type of linked list in which the last node points back to the first node, forming a closed loop.

Question 2.

What is the advantage of the optimized insertion approach in circular linked lists?

Explanation

The optimized approach reduces the time complexity of insertion at the start from O(n) to O(1), making it more efficient.

Question 3.

How can I get started with circular linked lists in programming?

Explanation

To get started, understand the basic structure of circular linked lists and practice implementing operations like insertion, deletion, and traversal.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Unlock this article for Free,
by logging in

Insertion at End in Circular Linked List in Python(Naïve and Optimized Approach)

Insertion at Beginning in Circular Linked List in Python