700232. Doubly linked list Insertion at given position
Basic
Insert a Node in Doubly Linked List
Summary
This problem is about inserting a new node at a given position in a doubly linked list. The key concepts involved are doubly linked lists and basic algorithmic operations.
Detailed Explanation
The task is to insert a new node with the given data after the kth node from the start of the doubly linked list. We need to first find the kth node, then create a new node with the given data and link it after the found node. If the position is beyond the last node in the list, we simply append the new node at the end.
Here's the step-by-step breakdown:
- Initialize three pointers:
prev,curr, andnext. - Start traversing from the beginning of the doubly linked list using
currpointer. - For each iteration:
- Move
currone step forward until it reaches the kth node. - Update
prevto point to the current node (prev = curr).
- Move
- If
kis equal to the size of the list, then we need to append the new node at the end. - Create a new node with the given data and link it after the found node by updating
nextpointer (curr->next = new_node;) and previous pointer (new_node->prev = prev; new_node->next = curr->next;). - Update
nextto point to the new node (next = new_node;).
Time Complexity: O(n), where n is the size of the list. Space Complexity: O(1), as we are not using any extra space that scales with the input size.
Optimized Solutions
Java
class Node {
int data;
Node prev, next;
public Node(int d) {
data = d;
}
}
public class DoublyLinkedList {
Node head;
void insertNodeAtPosition(Node newNode, int position) {
Node temp = head;
for (int i = 1; i < position; i++) {
temp = temp.next;
}
newNode.prev = temp;
newNode.next = temp.next;
if (temp.next != null)
temp.next.prev = newNode;
temp.next = newNode;
if (position == 1) head = newNode;
}
}