# Delete the kth node of a Doubly Linked List

Problem Statement: Given the head of a doubly linked list and a value K, delete the node that is located at the Kth position from the head of the list.
1 <= K <= Length of DLL

Examples
```Example 1:
Input Format:
DLL: 3 <-> 2 <-> 5 <-> 1 <-> 3K: 3

Output: DLL: 3 <-> 2 <-> 1 <-> 4

Explanation: The node with the value 5 is at position K hence it will be deleted and the nodes before and after it will be connected.
Input Format:
DLL: 7 <-> 5K: 2

Result: DLL: 7

Explanation: After deleting the node as position 2, which will be like deleting the tail, only the head will be left and returned.
```

### Solution

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

### Approach:

To delete the Kth node from a doubly linked list, we follow a similar logic as when deleting the tail node. First, we locate the Kth node by traversing the list and maintaining a count of nodes visited.

Once we reach the Kth node, we update the linkage between the Kth node’s previous node and its next node. Since a doubly linked list is bidirectional, we set the previous node’s ‘next’ pointer to the Kth node’s ‘next’ node and the Kth node’s ‘back’ pointer to its ‘previous’ node. This effectively removes the Kth node from the list.

Edge cases to consider:

1. If the input doubly linked list is empty, we return null, as there is nothing to delete.
2. If K equals 1 (meaning we need to delete the first node), we follow the steps to delete the head of the list.
3. If K equals the length of the doubly linked list, we need to delete the tail of the doubly linked list.
4. If the doubly linked list has a single element, K can only take value 1 hence we delete this node and return null.

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 the temp’s back pointer is pointing to and track the temp’s next node with the front pointer.

Step 3: Set the ‘next’ pointer of the prev node to the front node.

Step 4: Set the ‘back’ pointer of the front node to the back node.

Step 5: Set temp’s next and back pointers to null so it also does not point to anything. Now that we have updated the doubly linked list, the list is now one node shorter than before.

Step 6: Delete prev (C++ Only)Note that in C++, it’s essential to explicitly delete the previous head to free memory. In Java, memory management is automatic, handled by the garbage collector, which cleans up unreferenced objects.

Code:

## C++ Code

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

using namespace std;

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

// 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
// Initialize 'prev' to the head node

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;
}

}

// Function to print the elements of the doubly linked list
// Print the data in the current node
cout << head->data << " ";
// Move to the next node
}
}

// Return NULL if the list is empty or contains only one element
return nullptr;
}

// Store the current head as 'prev'
// Move 'head' to the next node

// Set 'back' pointer of the new head to nullptr

// Set 'next' pointer of 'prev' to nullptr
prev->next = nullptr;

}

// Function to delete the tail of the doubly linked list
// If the list is empty or has only one node, return null
return nullptr;
}

while (tail->next != nullptr) {
// Traverse to the last node (tail)
tail = tail->next;
}

Node* newTail = tail->back;
newTail->next = nullptr;
tail->back = nullptr;

// Free memory of the deleted node
delete tail;

}

// Function to remove the Kth element from the doubly linked list
return NULL;
}
int count = 0;
while(kNode!=NULL){
count++;
if(count==k){
break;
}
kNode = kNode->next;
}
Node* prev = kNode->back;
Node* front = kNode->next;

if(prev==NULL && front == NULL){
delete kNode;
return NULL;
}
else if (prev==NULL){
}
else if(front == NULL){
}

prev->next = front;
front->back = prev;

kNode->next = NULL;
kNode->back = NULL;

delete kNode;

}

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

cout << endl << "Doubly Linked List after its 3rd element is removed: " << endl;

return 0;
}
``````

Output:

12 5 8 7 4
Doubly Linked List after it’s 3 element is removed:
12 5 7 4

Time Complexity: O(1) Removing a node of a doubly linked list is a quick operation, taking constant time because it only involves updating references and is independent of the list’s length.

Space Complexity: O(1) Deleting a node also has minimal memory usage, using a few extra pointers without regard to the list’s size hence constant space complexity.

## Java Code

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

// 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;
}
}

// Function to convert an array to a doubly linked list
private static Node convertArr2DLL(int[] arr) {
Node head = new Node(arr[0]); // Create the head node with the first element of the array

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);
prev.next = temp; // Update the 'next' pointer of the previous node to point to the new node
prev = temp; // Move 'prev' to the newly created node for the next iteration
}
}

// Function to delete the tail of the doubly linked list
private static Node deleteTail(Node head) {
return null; // Return null if the list is empty or contains only one element
}

while (tail.next != null) {
tail = tail.next;
}

Node newtail = tail.back;

newtail.next = null;
tail.back = null;

}

return null; // Return null if the list is empty or contains only one element
}

head.back = null; // Set 'back' pointer of the new head to null
prev.next = null; // Set 'next' pointer of 'prev' to null

}

// Function to print the elements of the doubly linked list
private static void print(Node head) {
System.out.print(head.data + " "); // Print the data in the current node
}
System.out.println();
}

// Function to remove the Kth element from the doubly linked list
private static Node removeKthElement(Node head, int k) {
return null;
}
int count = 0;
while (kNode != null) {
count++;
if (count == k) {
break;
}
kNode = kNode.next;
}
Node prev = kNode.back;
Node front = kNode.next;

if (prev == null && front == null) {
return null;
} else if (prev == null) {
} else if (front == null) {
}

prev.next = front;
front.back = prev;

kNode.next = null;
kNode.back = null;

}

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

System.out.println("Doubly Linked List after deleting tail node: ");
}
}
``````

Output:

12 5 8 7 4
Doubly Linked List after it’s 3 element is removed:
12 5 7 4

Time Complexity: O(1) Removing a node of a doubly linked list is a quick operation, taking constant time because it only involves updating references and is independent of the list’s length.

Space Complexity: O(1) Deleting a node also has minimal memory usage, using a few extra pointers without regard to the list’s size hence constant space complexity.

## Python Code

``````# Define a Node class for doubly linked list
class Node:
def __init__(self, data, next_node=None, back_node=None):
self.data = data
self.next = next_node
self.back = back_node

# Function to convert an array to a doubly linked list
def convert_arr_to_dll(arr):
# Create the head node with the first element of the array
# Initialize 'prev' to the head node

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

# Function to print the elements of the doubly linked list
# Print the data in the current node
# Move to the next node
print()

# Return None if the list is empty or contains only one element
return None

# Store the current head as 'prev'
# Move 'head' to the next node
# Set 'back' pointer of the new head to None
# Set 'next' pointer of 'prev' to None
prev.next = None

# Function to delete the tail of the doubly linked list
# If the list is empty or has only one node, return None
return None

while tail.next is not None:
# Traverse to the last node (tail)
tail = tail.next

new_tail = tail.back
new_tail.next = None
tail.back = None

# Free memory of the deleted node
del tail

# Function to remove the Kth element from the doubly linked list
return None

count = 0
while k_node is not None:
count += 1
if count == k:
break
k_node = k_node.next

prev = k_node.back
front = k_node.next

if prev is None and front is None:
del k_node
return None
elif prev is None:
elif front is None:

prev.next = front
front.back = prev
k_node.next = None
k_node.back = None

del k_node

if __name__ == "__main__":
arr = [12, 5, 8, 7, 4]

print("\nDoubly Linked List after its 3rd element is removed: ")
``````

Output:

12 5 8 7 4
Doubly Linked List after it’s 3 element is removed:
12 5 7 4

Time Complexity: O(1) Removing a node of a doubly linked list is a quick operation, taking constant time because it only involves updating references and is independent of the list’s length.

Space Complexity: O(1) Deleting a node also has minimal memory usage, using a few extra pointers without regard to the list’s size hence constant space complexity.

## JavaScript Code

``````// Define a Node class for doubly linked list
class Node {
constructor(data, nextNode = null, backNode = null) {
this.data = data;
this.next = nextNode;
this.back = backNode;
}
}

// Function to convert an array to a doubly linked list
function convertArrToDLL(arr) {
// Create the head node with the first element of the array
// Initialize 'prev' to the head node

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
const 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;
}

}

// Function to print the elements of the doubly linked list
// Print the data in the current node
// Move to the next node
}
}

// Return null if the list is empty or contains only one element
return null;
}

// Store the current head as 'prev'
// Move 'head' to the next node
// Set 'back' pointer of the new head to null
// Set 'next' pointer of 'prev' to null
prev.next = null;

}

// Function to delete the tail of the doubly linked list
// If the list is empty or has only one node, return null
return null;
}

while (tail.next !== null) {
// Traverse to the last node (tail)
tail = tail.next;
}

const newTail = tail.back;
newTail.next = null;
tail.back = null;

// Free memory of the deleted node
delete tail;

}

// Function to remove the Kth element from the doubly linked list
return null;
}

let count = 0;
while (kNode !== null) {
count++;
if (count === k) {
break;
}
kNode = kNode.next;
}

const prev = kNode.back;
const front = kNode.next;

if (prev === null && front === null) {
delete kNode;
return null;
} else if (prev === null) {
} else if (front === null) {
}

prev.next = front;
front.back = prev;
kNode.next = null;
kNode.back = null;

delete kNode;

}

const arr = [12, 5, 8, 7, 4];

console.log("\nDoubly Linked List after its 3rd element is removed: ");
``````

Output:

12 5 8 7 4
Doubly Linked List after it’s 3 element is removed:
12 5 7 4

Time Complexity: O(1) Removing a node of a doubly linked list is a quick operation, taking constant time because it only involves updating references and is independent of the list’s length.

Space Complexity: O(1) Deleting a node also has minimal memory usage, using a few extra pointers without regard to the list’s size hence constant space complexity.

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