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.

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.

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.

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.

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.

1. Create a new node with the given data.
3. If the linked list is not empty:
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.
4. The new node has been successfully inserted at the end of the linked list.

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

def __init__(self):

def insert_at_end(self, data):
new_node = Node(data)
else:
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

def __init__(self):

def insert_at_beginning(self, data):
new_node = Node(data)
```

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)
else:
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.

Related Banners

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

Question 1.

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