# Insert before a given Node of a DLL

Problem Statement: Given the pointer to a node belonging to a doubly linked list, and a value val, your task is to insert a new node with the given val before the referenced node. It is guaranteed that the node will not be the head of the doubly linked list.

Examples
```Example 1:
Input Format:
DLL: 1 <-> 2 <-> 3 <-> 4Give Node: 3Value to be Inserted: 6

Result: DLL: 1 <-> 2 <-> 6 <-> 3 <-> 4

Explanation: We have to insert a new node with value 6 before a node with value 3.
Example 2:
Input Format:
DLL: 10 <-> 20 <-> 30
Given Node: 30
Value to be Inserted: 5

Result: DLL: 10 <-> 20 <-> 5 <->30
Explanation: In this case, a new node of value 5 has to be inserted before the 1st node ie. head of the doubly linked list. 5 will be the new head of the doubly linked list.
```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Approach:

To insert before a given node, begin by identifying its previous node. This step is assured since the provided node is never the head. Create a new node with the specified value and set its back and next pointers to the previous node and the given node, respectively. To seamlessly integrate the new node into the doubly linked list, set the previous node’s next pointer and the given node’s back pointer to the new node.

### Algorithm:

Step 1: Track the node to which the back pointer of the referenced node is pointing and the name is `prev`.

Step 2: Create a new node with its data as val and back pointer as prev and next pointer as the given node.

Step 3: Update the next pointer of the prev node to point to the newly created node, and also, update the back pointer of the referenced node to point to the new node.

Code:

## C++ Code

``````#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Define a Node class for doubly linked list
class Node {
public:
// Data stored in the node
int data;
// Pointer to the next node in the list (forward direction)
Node* next;
// Pointer to the previous node in the list (backward direction)
Node* back;

// Constructor for a Node with both data, a reference to the next node, and a reference to the previous node
Node(int data1, Node* next1, Node* back1) {
data = data1;
next = next1;
back = back1;
}

// Constructor for a Node with data, and no references to the next and previous nodes (end of the list)
Node(int data1) {
data = data1;
next = nullptr;
back = nullptr;
}
};

// Function to convert an array to a doubly linked list
Node* convertArr2DLL(vector<int> arr) {
// Create the head node with the first element of the array
Node* head = new Node(arr[0]);
// Initialize 'prev' to the head node
Node* prev = head;

for (int i = 1; i < arr.size(); i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
Node* temp = new Node(arr[i], nullptr, prev);
// Update the 'next' pointer of the previous node to point to the new node
prev->next = temp;
// Move 'prev' to the newly created node for the next iteration
prev = temp;
}
// Return the head of the doubly linked list
return head;
}

// Function to print the elements of the doubly linked list
void print(Node* head) {
while (head != nullptr) {
// Print the data in the current node
cout << head->data << " ";
// Move to the next node
head = head->next;
}
}

// Function to insert before the Kth element
Node* insertBeforeKthElement(Node* head, int k, int val){

if(k==1){
// K = 1 means node has to be insert before the head
return insertBeforeHead(head, val);
}

// temp will keep track of the node
Node* temp = head;

// count so that the Kth element can be reached
int count = 0;
while(temp!=NULL){
count ++;
// On reaching the Kth position, break out of the loop
if(count == k) break;
// keep moving temp forward till count != K
temp = temp->next;
}
// track the node before the Kth node
Node* prev = temp->back;

// create new node with data as val
Node* newNode = new Node(val, temp, prev);

//join the new node in between prev and temp
prev->next = newNode;
temp->back = newNode;

// Set newNode's pointers to prev and temp
newNode->next = temp;
newNode->back = prev;

// Return the head of the updated doubly linked list
return head;
}

// Function to insert a new node before a given node
void insertBeforeNode(Node*node, int val){
// Get the node before the given node
Node* prev = node->back;

// Create a new node with the given val
Node* newNode = new Node(val, node, prev);

// Connect the newNode to the doubly linked List
prev->next = newNode;
node->back = newNode;

// void function to just update
return;
}

int main() {
vector<int> arr = {12, 5, 8, 7, 4};
Node* head = convertArr2DLL(arr);

print(head);
cout << endl << "Doubly Linked List After Inserting before the node with value 8: " << endl;
insertBeforeNode(head->next->next, 100);
print(head);

return 0;
}
``````

Output:

12 5 8 7 4
Doubly Linked List After Inserting before the node with value 8:
12 5 100 8 7 4

Time Complexity: O(1):  The time complexity of this insertion operation is O(1) because only a constant number of pointer updates are being performed regardless of the size of the Doubly Linked List.

Space Complexity: O(1):  The space complexity is also O(1) because a constant amount of extra space is used to create the new node

## Java Code

``````public class DLinkedList {
public static class Node {
// Data stored in the node
public int data;
// Reference to the next node in the list (forward direction)
public Node next;
// Reference to the previous node in the list (backward direction)
public Node back;

// Constructor for a Node with both data, a reference to the next node, and a reference to the previous node
public Node(int data1, Node next1, Node back1) {
data = data1;
next = next1;
back = back1;
}

// Constructor for a Node with data, and no references to the next and previous nodes (end of the list)
public Node(int data1) {
data = data1;
next = null;
back = null;
}
}

private static Node convertArr2DLL(int[] arr) {
// Create the head node with the first element of the array
Node head = new Node(arr[0]);
// Initialize 'prev' to the head node
Node prev = head;

for (int i = 1; i < arr.length; i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
Node temp = new Node(arr[i], null, prev);
// Update the 'next' pointer of the previous node to point to the new node
prev.next = temp;
// Move 'prev' to the newly created node for the next iteration
prev = temp;
}
// Return the head of the doubly linked list
return head;
}

private static void print(Node head) {
while (head != null) {
// Print the data in the current node
System.out.print(head.data + " ");
// Move to the next node
head = head.next; // Move to the next node
}
System.out.println();
}

// Function to insert a new node before a given node
private static void insertBeforeNode(Node node, int val) {
// Get the node before the given node
Node prev = node.back;

// Create a new node with the given val
Node newNode = new Node(val, node, prev);

// Connect the newNode to the doubly linked list
prev.next = newNode;
node.back = newNode;

}

public static void main(String[] args) {
int[] arr = {12, 5, 6, 8, 4};
// Convert the array to a doubly linked list
Node head = convertArr2DLL(arr);
// Print the doubly linked list
print(head);

System.out.println("Doubly Linked List After Inserting before the node with value 8:");

insertBeforeNode(head.next.next, 100);
print(head);
}
}
``````

Output:

12 5 8 7 4
Doubly Linked List After Inserting before the node with value 8:
12 5 100 8 7 4

Time Complexity: O(1):  The time complexity of this insertion operation is O(1) because only a constant number of pointer updates are being performed regardless of the size of the Doubly Linked List.

Space Complexity: O(1):  The space complexity is also O(1) because a constant amount of extra space is used to create the new node.

## Python Code

``````class DLinkedList:
class Node:
def __init__(self, data, next_node=None, back_node=None):
# Data stored in the node
self.data = data
# Reference to the next node in the list (forward direction)
self.next = next_node
# Reference to the previous node in the list (backward direction)
self.back = back_node

@staticmethod
def convertArr2DLL(arr):
# Create the head node with the first element of the array
head = DLinkedList.Node(arr[0])
# Initialize 'prev' to the head node
prev = head

for i in range(1, len(arr)):
# Create a new node with data from the array and set its 'back' pointer to the previous node
temp = DLinkedList.Node(arr[i], None, prev)
# Update the 'next' pointer of the previous node to point to the new node
prev.next = temp
# Move 'prev' to the newly created node for the next iteration
prev = temp

# Return the head of the doubly linked list
return head

@staticmethod
def print_linked_list(head):
while head is not None:
# Print the data in the current node
print(head.data, end=" ")
# Move to the next node
head = head.next
print()

@staticmethod
def insert_before_node(node, val):
# Get the node before the given node
prev = node.back

# Create a new node with the given val
new_node = DLinkedList.Node(val, node, prev)

# Connect the new_node to the doubly linked list
prev.next = new_node
node.back = new_node

if __name__ == "__main__":
arr = [12, 5, 6, 8, 4]
# Convert the array to a doubly linked list
head = DLinkedList.convertArr2DLL(arr)
# Print the doubly linked list
DLinkedList.print_linked_list(head)

print("Doubly Linked List After Inserting before the node with value 8:")

# Insert a new node before the node with value 8
DLinkedList.insert_before_node(head.next.next, 100)
# Print the updated doubly linked list
DLinkedList.print_linked_list(head)
``````

Output:

12 5 8 7 4
Doubly Linked List After Inserting before the node with value 8:
12 5 100 8 7 4

Time Complexity: O(1):  The time complexity of this insertion operation is O(1) because only a constant number of pointer updates are being performed regardless of the size of the Doubly Linked List.

Space Complexity: O(1):  The space complexity is also O(1) because a constant amount of extra space is used to create the new node.

## JavaScript Code

``````class Node {
// Data stored in the node
constructor(data1, next1, back1) {
this.data = data1;
this.next = next1;
this.back = back1;
}

// Constructor for a Node with data, and no references to the next and previous nodes (end of the list)
constructor(data1) {
this.data = data1;
this.next = null;
this.back = null;
}
}

function convertArr2DLL(arr) {
// Create the head node with the first element of the array
let head = new Node(arr[0]);
// Initialize 'prev' to the head node
let prev = head;

for (let i = 1; i < arr.length; i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
let temp = new Node(arr[i], null, prev);
// Update the 'next' pointer of the previous node to point to the new node
prev.next = temp;
// Move 'prev' to the newly created node for the next iteration
prev = temp;
}
// Return the head of the doubly linked list
return head;
}

function print(head) {
while (head !== null) {
// Print the data in the current node
console.log(head.data + " ");
// Move to the next node
head = head.next; // Move to the next node
}
console.log();
}

// Function to insert a new node before a given node
function insertBeforeNode(node, val) {
// Get the node before the given node
let prev = node.back;

// Create a new node with the given val
let newNode = new Node(val, node, prev);

// Connect the newNode to the doubly linked list
prev.next = newNode;
node.back = newNode;
}

// Main function
let arr = [12, 5, 6, 8, 4];
// Convert the array to a doubly linked list
let head = convertArr2DLL(arr);
// Print the doubly linked list
print(head);

console.log("Doubly Linked List After Inserting before the node with value 8:");

insertBeforeNode(head.next.next, 100);
print(head);
``````

Output:

12 5 8 7 4
Doubly Linked List After Inserting before the node with value 8:
12 5 100 8 7 4

Time Complexity: O(1):  The time complexity of this insertion operation is O(1) because only a constant number of pointer updates are being performed regardless of the size of the Doubly Linked List.

Space Complexity: O(1):  The space complexity is also O(1) because a constant amount of extra space is used to create the new node

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Gauri Tomar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article