Problem Link - Insertion in Doubly Linked List
Problem Statement:
Let’s suppose you need to insert a node newNode between node A and node B, the pointers we need to update are:
- next pointer of
A - prev pointer of
B - next and prev pointer of
newNode
Complete the function insertAtIndex(int index, int value) where index denotes that you need to insert a new node after the index-1 th element, i.e., at the index th position.
Approach:
The key idea of this solution is to insert a new node at a specific index in a doubly linked list. Depending on the position, the new node will either:
Here’s how the approach works:
-
Inserting at Index 0 (Head):
-
If the index is
0, the new node will become the new head. -
The existing head node will shift, and the new node will be linked to it by updating the pointers.
-
-
Inserting at Other Positions:
-
First, we traverse the list to find the node after which we need to insert (the node at
index - 1). -
Once located, we update the next and prev pointers of the surrounding nodes to insert the new node.
-
This ensures that the new node is properly linked between its neighbors.
-
-
printValues():
- This function prints all the values in the linked list, starting from the head and moving to the tail.
Time Complexity:
-
insertAtIndex: O(n) because, in the worst case, we might need to traverse the entire list to reach the position before inserting.
-
printValues: O(n) where
nis the number of nodes, as it requires traversing the list to print all elements.
Space Complexity:
- O(1) for insertion, as the operation modifies pointers but does not use extra space beyond the new node.