Insertion at Beginning in Circular Linked List in Python
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 beginning 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 Start: To insert a new node at the beginning of the circular linked list:
- Create a new node with the desired data.
- If the list is empty (head is NULL), set the new node’s next pointer to itself and update head to point to the new node.
- If the list is not empty, set the new node’s next pointer to the current head.
- Update the last node’s next pointer to the new node (making it circular).
- Update head to point to the new node.
Circular Linked List Insertion at Beginning 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
Step 1: Create a New Node
To add a new node at the start, first create a new node with the desired data
Step 2: Link the New Node
- Set the next pointer of the new node to the current head of the circular linked list.
Step 3: Update the Head
- Now, update the head pointer to point to the new node.
Implementation of Circular Linked List in Python(Naïve Approach) :
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_at_start(head, data):
new_node = Node(data)
temp = head
new_node.next = head
# Traverse to the last node to update the next pointer
while(temp.next != head):
temp = temp.next
temp.next = new_node
head = new_node
return head
Optimized Approach for Insertion at Beginning in Circular Linked List
Step 1: Create a New Node
Similar to the naïve approach, start by creating a new node with the desired data.
Step 2: Link the New Node
- Set the next pointer of the new node to the current head.
Step 3: Update the Last Node
- Find the last node in the circular linked list and update its next pointer to the new node.
Step 4: Update the Head
- Finally, update the head pointer to point to the new node.
Implementation of Circular Linked List in Python(Optimized Approach) :
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_at_start(head, data):
new_node = Node(data)
new_node.next = head
temp = head
# Find the last node and update its next pointer
while(temp.next != head):
temp = temp.next
temp.next = new_node
head = new_node
return head
Time and Space Complexity
Conclusion
In this page, we have discussed about concept of “Insertion at Beginning 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