- Prepare
- All Platforms
- Programming
- Aptitude
- Syllabus
- Interview Preparation
- Interview Exp.
- Off Campus
- Prime Video
- Prime Mock

- Prime Video
- OffCampus Updates
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

No New notification

- Login
- Get Prime

# 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.

- Create a new

- To insert a node at the end of the circular linked list (naïve approach):
**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.

- Create a new

- To insert a node at the end of the circular linked list (optimized approach):

**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**

**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

**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

Login/Signup to comment