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

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.

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

def __init__(self):

def insert_at_end_naive(self, data):
new_node = Node(data)

else:
while current.next != self.head:
current = current.next
current.next = new_node

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

# Example usage:
clist.insert_at_end_naive(1)
clist.insert_at_end_naive(2)
clist.insert_at_end_naive(3)

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

def __init__(self):
self.last = None

def insert_at_end_optimized(self, data):
new_node = Node(data)

else:
self.last.next = new_node
self.last = new_node

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

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

clist.display()

```

Time and Space Complexity

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.

Related Banners

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

Question 1.

What is a circular linked list?

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?

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?

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