KEYWORD: adding node, specific position, linked list, node value
Want to Insert a Node at a Specific Position in a Linked List? We’ve Got You Covered!
Introduction
Inserting a new node at a specific position in a linked list is a common task in programming. In this article, we will guide you through the process with a detailed problem statement, examples, and a code snippet for reference. Let’s get started!
Problem Description
The task is to insert a new node with a given value at a specified position in a given linked list.
Example 1
Input:
LinkedList: 0->1->2
Value to insert: 5
Position: 2
Output:
LinkedList: 0->5->1->2
Explanation: The value 5 should be inserted at the 2nd position in the existing linked list.
Example 2
Input:
LinkedList: 12->5->8->7
Value to insert: 100
Position: 3
Output:
LinkedList: 12->5->100->8->7
Explanation: The value 100 should be inserted at the 3rd position in the existing linked list.
Approach
The key to solving this problem is to traverse the linked list until we reach the desired position. For example, if we need to insert a node at the 3rd position, we would traverse up to the 2nd position and then insert the new node after this position.
To insert the new node, we create a new node with the given value. Then, we ensure that the new node is placed after the 2nd position by adjusting the links accordingly.
Implementation
Here is a sample implementation of inserting a node at a specific position in a linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertNode(self, value, position):
new_node = Node(value)
if position == 0:
new_node.next = self.head
self.head = new_node
return
current = self.head
previous = None
count = 0
while current and count < position:
previous = current
current = current.next
count += 1
previous.next = new_node
new_node.next = current
def printList(self):
current = self.head
while current:
print(current.data, end=" ")
current = current.next
# Example usage
linked_list = LinkedList()
linked_list.insertNode(0, 0)
linked_list.insertNode(1, 1)
linked_list.insertNode(2, 2)
linked_list.printList()
Complexity Analysis
The time complexity of inserting a node at a specific position in a linked list is O(N) in the worst-case scenario, which occurs when the insertion is at the tail. However, in the best-case scenario where the insertion is at the head, the time complexity is O(1).
The space complexity is O(1) as no additional space is required.
Conclusion
You have now learned how to insert a node at a specific position in a linked list. We have provided a clear problem statement, examples, a step-by-step solution approach, and a code implementation.
If you are interested in expanding your knowledge of data structures and algorithms, we recommend exploring our comprehensive A2Z DSA Course, which includes videos and blogs.
We would like to express our gratitude to Neerav Sethi for contributing to this article on takeUforward. If you would like to share your expertise with the takeUforward community, please refer to this article.
