Doubly linked list Insertion at given position in Java
Given a doubly-linked list, a data structure in which each node has references to both the next and previous nodes in the list. In addition, given an integer value x and a particular position named pos in the list. The task is to insert a new node into a doubly-linked list, placing it immediately after the node at the pth position. That means the node containing the value x should be inserted between the node at position p and its successor within the list.
Example 1:
Input: DLList: 1 <-> 3 <-> 7 <-> 9 <->
pos = 1, x = 5
Output: 1 3 5 7 9
Explanation: The node containing value 5 is inserted between the node at positions 1 and 3. So, 5 is inserted after position 1, i.e., at position 2.
Example 2:
Input: DLList: 22 <-> 53 <-> 72<-> 19 <-> 32
pos = 3, x = 26
Output: 22 53 72 19 26 32
Explanation: The node value 26 is inserted between the node at positions 3 and 5. So, 26 is inserted after position 3, i.e., at position 4.
Approach:
Follow the below steps to solve the problem:
Step 1: Define a class named DLLNode to represent a node in a double linked list. And declare a variable called data and references to the next node and previous node.
Step 2: Define a class named DubLinkedList for a double linked list.
Step 2.1: Create a new node. And add it to the list.
Step 2.2: Traverse the list to find the specified position.
Step 2.3: Insert the new node data at the specified position, then adjust the references accordingly.
Step 3: Display the elements after the insertion of new node data at the specified position.
FileName: DubLinkedList.java
// defining a class for a doubly linked list node
class DLLNode {
int data;
DLLNode nextNd;
DLLNode prevNd;
// constructor to initialize a node with given data
DLLNode(int data) {
this.data = data;
nextNd = prevNd = null;
}
}
// defining a class for a doubly linked list
public class DubLinkedList {
// method to create a new node and add it to the beginning of the list
DLLNode newNode( DLLNode head, int data) {
DLLNode n = new DLLNode(data); // creating a new node
if (head == null) {
head = n;
return head;
}
head.nextNd = n;
n.prevNd = head;
head = n;
return head;
}
// method to display the elements of the list
void printList( DLLNode node) {
if (node == null) {
System.out.println("The list is empty.");
return;
}
DLLNode temp = node;
while (temp.prevNd != null) {
temp = temp.prevNd;
}
while (temp != null) { // traverse and print the list
System.out.print(temp.data + " ");
temp = temp.nextNd;
}
System.out.println();
}
// main method
public static void main(String args[]) {
DubLinkedList DLL = new DubLinkedList();
DLLNode head = null;
DLLNode root = null;
// provide input values
int[] linkedListVals = {22, 53, 72, 19, 32};
int posn = 3;
int data = 26;
// creating the linked list with input values
for (int i = 0; i < linkedListVals.length; i++) {
head = DLL.newNode(head, linkedListVals[i]);
if (root == null)
root = head;
}
head = root;
NodeInsertionAtPos np = new NodeInsertionAtPos();
np.addNodeAtPosn(head, posn, data);
DLL.printList(head);
}
}
// defining a class for node insertion at a specified position in the list
class NodeInsertionAtPos {
// method to insert a new node at the specified position in the list
void addNodeAtPosn(DLLNode headRef, int posn, int data) {
DLLNode newNode = new DLLNode(data);
DLLNode temp = headRef;
int cnt = -1;
// traverse the list to find the position to insert the new node
while (temp != null) {
cnt++;
if (cnt == posn) {
break;
}
temp = temp.nextNd;
}
DLLNode front = temp.nextNd; // reference to the node after the specified position
if (front == null) {
temp.nextNd = newNode;
newNode.prevNd = temp;
} else {
newNode.nextNd = front;
newNode.prevNd = temp;
temp.nextNd = newNode;
front.prevNd = newNode;
}
}
}
Output:
22 53 72 19 26 32
Complexity analysis: The time complexity is O(n) for creating a doubly linked list. Inserting a node at a specified position takes O(posn) time, and printing the elements of the list takes O(n), where n is the number of elements. The overall time complexity of the program is O(n), where n is the length of the input array. The space complexity is O(1) because it uses constant extra space for a fixed number of variables and references, irrespective of the input size.