**Problem Statement:** Given a doubly linked list, an integer **K**, and a value **val**, your task is to insert a new node with the given value val before the **Kth** node in the list. Ensure that the doubly linked structure is maintained after the insertion.

**Note:** In this question, the Kth node is indexed starting from 1.

##
**
Examples
**

Example 1:

Input Format:DLL: 2 <-> 3 <-> 4 <-> 1

Position K: 3

Value to be Inserted: 10

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

Explanation: The node at the 3rd position is 4. We have inserted a new node of value 10 before 4 ie. in between 3 and 4.

Example 2:

Input Format:DLL: 10 <-> 20 <-> 30

Position K: 1

Value to be Inserted: 5

Result: DLL: 5 <-> 10 <-> 20 <-> 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**:

If K is 1 then it points to the head and we have to perform Insert Node before head as discussed in the earlier **article** and if K = length of the linked list then we have to insert the nodes before the tail of the list which has been covered in previous **article.** In every other case, we have to **traverse to the Kth node **and** track its previous node**. Then **create a new node** and set its **back** and **next** pointers to the **Kth’s previous node** and **Kth node **respectively. Then to fully integrate the new nodes into the doubly linked list we join the **previous nodes’ next pointer** and** Kth’s node back pointer** to the new node.

**Algorithm:**

**Step 1: Traverse the doubly linked list **to the** Kth node **while keeping** count.** Maintain a while loop to keep a counter variable and as the counter becomes K we break out of the loop, else we keep moving next. Use a **temp pointer** to point to the Kth node that has to be deleted.

**Step 2: **Set the **prev node** to the one that** temp’s back pointer** is pointing to and **create a new node** with its **data as val **and back **pointer as prev** and **next pointer as temp**.

**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 **temp** **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;
}
}
// This function was explain in prevoius articles
// Please refer there
// Function to insert new node before head
Node* insertBeforeHead(Node* head, int val){
// Create new node with data as val
Node* newHead = new Node(val , head, nullptr);
head->back = newHead;
return newHead;
}
// This function was explain in prevoius articles
// Please refer there
Node* insertBeforeTail(Node* head, int val){
// Edge case, if dll has only one elements
if(head->next==NULL){
// If only one element
return insertBeforeHead(head, val);
}
// Create pointer tail to traverse to the end of list
Node* tail = head;
while(tail->next!=NULL){
tail = tail->next;
}
// Keep track of node before tail using prev
Node* prev = tail->back;
// Create new node with value val
Node* newNode = new Node(val, tail, prev);
// Join the new node into the doubly linked list
prev->next = newNode;
tail->back = newNode;
// Return the updated linked list
return head;
}
// 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;
}
int main() {
vector<int> arr = {12, 5, 8, 7, 4};
Node* head = convertArr2DLL(arr);
print(head);
cout << endl << "Doubly Linked List After Inserting val on the kth position: " << endl;
head = insertBeforeKthElement(head, 2, 10);
print(head);
return 0;
}
```

**Output:**

12 5 8 7 4

Doubly Linked List After Inserting 6 before tail:

12 10 5 8 7 4

**Time Complexity: O(K) **The time complexity of this operation is O(K) in the worst case because it may involve traversing K nodes in the Doubly Linked List to reach the Kth element. In the best case, when K is 0 (insertion at the head), the time complexity is O(1) as it involves a constant number of operations. In the average case, it’s O(K).

**Space Complexity: O(1) **The space complexity is also O(1) because we are using a constant amount of extra space 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();
}
private static Node insertBeforeHead(Node head, int val){
// Create new node with data as val
Node newHead = new Node(val, head, null);
// Set old head's back pointer to the new Head
head.back = newHead;
// Return the new head
return newHead;
}
private static Node insertBeforeTail(Node head, int val){
// Edge case, if dll has only one elements
if(head.next==null){
// If only one element
return insertBeforeHead(head, val);
}
// Create pointer tail to traverse to the end of list
Node tail = head;
while(tail.next!=null){
tail = tail.next;
}
// Keep track of node before tail using prev
Node prev = tail.back;
// Create new node with value val
Node newNode = new Node(val, tail, prev);
// Join the new node into the doubly linked list
prev.next = newNode;
tail.back = newNode;
// Return the updated linked list
return head;
}
// Function to insert before the Kth node
private static 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;
}
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 val on the kth position: ");
head = insertBeforeKthElement(head, 2, 10);
print(head);
}
}
```

**Output:**

12 5 8 7 4

Doubly Linked List After Inserting 6 before tail:

12 10 5 8 7 4

**Time Complexity: O(K) **The time complexity of this operation is O(K) in the worst case because it may involve traversing K nodes in the Doubly Linked List to reach the Kth element. In the best case, when K is 0 (insertion at the head), the time complexity is O(1) as it involves a constant number of operations. In the average case, it’s O(K).

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

## Python Code

```
class Node:
def __init__(self, data1, next1=None, back1=None):
# Data stored in the node
self.data = data1
# Reference to the next node in the list (forward direction)
self.next = next1
# Reference to the previous node in the list (backward direction)
self.back = back1
def convert_arr_to_dll(arr):
# Create the head node with the first element of the array
head = 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 = 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
def print_dll(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()
def insert_before_head(head, val):
# Create new node with data as val
new_head = Node(val, head)
# Set old head's back pointer to the new Head
head.back = new_head
# Return the new head
return new_head
def insert_before_tail(head, val):
# Edge case, if dll has only one element
if head.next is None:
# If only one element
return insert_before_head(head, val)
# Create pointer tail to traverse to the end of list
tail = head
while tail.next is not None:
tail = tail.next
# Keep track of node before tail using prev
prev = tail.back
# Create new node with value val
new_node = Node(val, tail, prev)
# Join the new node into the doubly linked list
prev.next = new_node
tail.back = new_node
# Return the updated linked list
return head
def insert_before_kth_element(head, k, val):
if k == 1:
# K = 1 means node has to be inserted before the head
return insert_before_head(head, val)
# temp will keep track of the node
temp = head
# count so that the Kth element can be reached
count = 0
while temp is not None:
count += 1
# 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
prev = temp.back
# create new node with data as val
new_node = Node(val, temp, prev)
# join the new node in between prev and temp
prev.next = new_node
temp.back = new_node
# Set newNode's pointers to prev and temp
new_node.next = temp
new_node.back = prev
# Return the head of the updated doubly linked list
return head
if __name__ == "__main__":
arr = [12, 5, 6, 8, 4]
# Convert the array to a doubly linked list
head = convert_arr_to_dll(arr)
# Print the doubly linked list
print("Original Doubly Linked List:")
print_dll(head)
print("\nDoubly Linked List After Inserting 10 before the 2nd position:")
head = insert_before_kth_element(head, 2, 10)
print_dll(head)
```

**Output:**

12 5 8 7 4

Doubly Linked List After Inserting 6 before tail:

12 10 5 8 7 4

**Time Complexity: O(K) **The time complexity of this operation is O(K) in the worst case because it may involve traversing K nodes in the Doubly Linked List to reach the Kth element. In the best case, when K is 0 (insertion at the head), the time complexity is O(1) as it involves a constant number of operations. In the average case, it’s O(K).

**Space Complexity: O(1) **The space complexity is also O(1) because we are using a constant amount of extra space 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 to convert an array to a doubly linked list
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 to print the elements of the doubly linked list
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;
}
console.log();
}
// Function to insert before the Kth node
function insertBeforeKthElement(head, k, val) {
if (k === 1) {
// K = 1 means node has to be inserted before the head
return insertBeforeHead(head, val);
}
// temp will keep track of the node
let temp = head;
// count so that the Kth element can be reached
let 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
let prev = temp.back;
// create a new node with data as val
let 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 before the head of the doubly linked list
function insertBeforeHead(head, val) {
// Create a new node with data as val
let newHead = new Node(val, head, null);
// Set the old head's back pointer to the new Head
head.back = newHead;
// Return the new head
return newHead;
}
// Function to insert before the tail of the doubly linked list
function insertBeforeTail(head, val) {
// Edge case, if dll has only one element
if (head.next === null) {
// If only one element
return insertBeforeHead(head, val);
}
// Create a pointer tail to traverse to the end of the list
let tail = head;
while (tail.next !== null) {
tail = tail.next;
}
// Keep track of the node before tail using prev
let prev = tail.back;
// Create a new node with value val
let newNode = new Node(val, tail, prev);
// Join the new node into the doubly linked list
prev.next = newNode;
tail.back = newNode;
// Return the updated linked list
return head;
}
// Convert the array to a doubly linked list
let arr = [12, 5, 6, 8, 4];
let head = convertArr2DLL(arr);
// Print the doubly linked list
console.log("Original Doubly Linked List:");
print(head);
console.log("Doubly Linked List After Inserting 10 before the 2nd position:");
head = insertBeforeKthElement(head, 2, 10);
print(head);
```

**Output:**

12 5 8 7 4

Doubly Linked List After Inserting 6 before tail:

12 10 5 8 7 4

**Time Complexity: O(K) **The time complexity of this operation is O(K) in the worst case because it may involve traversing K nodes in the Doubly Linked List to reach the Kth element. In the best case, when K is 0 (insertion at the head), the time complexity is O(1) as it involves a constant number of operations. In the average case, it’s O(K).

**Space Complexity: O(1) **The space complexity is also O(1) because we are using a constant amount of extra space 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 toGauri Tomarfor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,please check out this article