Insertion in Linked List using Python
Insertion in Linked List using Python
In the world of data structures, linked lists are a fundamental concept. They provide a dynamic way to store and manage data, making them a crucial tool for any programmer. Among the many operations you can perform on a linked list, one of the most common is insertion.
In this page, we will dive deep into the process of insertion in linked list using Python.
Understanding Python Linked List Insertion
Insertion is a fundamental operation when working with linked lists. It allows us to add new elements at various positions within the list. Whether you want to add data to the beginning, end, or a specific location, knowing how to insert elements is crucial for manipulating linked lists effectively.
Types of Linked Lists
- Singly Linked List :
In a singly linked list, each node points to the next node in the sequence. It is the simplest form of a linked list and is often used when we need to traverse the list in one direction.
- Doubly Linked List :
A doubly linked list extends the concept of a singly linked list by adding an additional reference to the previous node. This bidirectional connection allows for more versatile operations but consumes additional memory.
- Circular Linked List :
In a circular linked list, the last node points back to the first node, forming a closed loop. This structure is advantageous in scenarios where we need continuous access to elements.
Insertion in Linked List Algorithm
- Create a new node with the given data.
- If the linked list is empty (head is None):
Set the new node as the head of the linked list. - If the linked list is not empty:
Initialize a pointer ‘current’ to the head of the linked list.
Traverse the linked list until you reach the last node (where the next pointer is None).
Set the ‘next’ pointer of the last node to point to the new node. - The new node has been successfully inserted at the end of the linked list.
Linked List Implementation in Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
Explanation :
- We create a new node with the provided data.
- If the linked list is empty (head is None), we set the new node as the head, making it the only node in the list.
- If the linked list is not empty, we traverse it by starting from the head and moving to the next node until we find the last node (the one with a next pointer set to None).
- Once we reach the last node, we update its next pointer to point to the new node, effectively inserting the new node at the end.
Mastering Insertion in Linked List in Python
- Insertion at Beginning
- Insertion at Ending
Insertion at Beginning in Linked List in Python
- Inserting an element at the beginning of a linked list involves creating a new node, setting its reference to the current head node, and updating the head to point to the new node.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
Insertion at End in Linked List in Python
To insert an element at the end of a linked list, you traverse the list until you reach the last node and then add the new node there. Here’s the Python implementation:
class LinkedList:
# ... (previous code)
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
Time and Space Complexity
The time complexity for insertion in a linked list varies based on the position of insertion:
- Insertion at the beginning or end takes O(1) time.
- Insertion at a specific position takes O(n) time in the worst case, where n is the list’s length.
- The space complexity for insertion is O(1) since it only involves creating a new node.
Conclusion
In this page, insertion in linked list using Python. We discussed the different types of linked lists, the importance of insertion operations, and how to handle various scenarios.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
What distinguishes a singly linked list from a doubly linked list?
A singly linked list is a linear data structure where each node has a data part and a reference (or link) to the next node in the sequence. It allows for forward traversal only, meaning you can move from the head to the tail of the list. In contrast, a doubly linked list extends the concept by having each node contain references to both the next and previous nodes.
Question 2.
Is it possible to insert multiple elements at once in a linked list?
Yes, it’s possible to insert multiple elements into a linked list, but they must be inserted one at a time. To insert multiple elements sequentially, you can loop through the elements you want to insert and call the insertion operation (e.g., insert_at_end) for each element.
Question 3.
What is the time complexity of inserting a node in a linked list?
The time complexity depends on the position of insertion. In the worst case, it’s O(n) for singly linked lists and O(1) for doubly linked lists when inserting at the beginning.
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
