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 <-> 3 K: 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 <-> 5 K: 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:
If the input doubly linked list is empty, we return null, as there is nothing to delete.
If K equals 1 (meaning we need to delete the first node), we follow the steps to delete the head of the list.
If K equals the length of the doubly linked list, we need to delete the tail of the doubly linked list.
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 isautomatic, 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
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 delete the head of the doubly linked list
Node* deleteHead(Node* head) {
if (head == nullptr || head->next == nullptr) {
// Return NULL if the list is empty or contains only one element
return nullptr;
}
// Store the current head as 'prev'
Node* prev = head;
// Move 'head' to the next node
head = head->next;
// Set 'back' pointer of the new head to nullptr
head->back = nullptr;
// Set 'next' pointer of 'prev' to nullptr
prev->next = nullptr;
// Return the new head
return head;
}
// Function to delete the tail of the doubly linked list
Node* deleteTail(Node* head) {
if (head == nullptr || head->next == nullptr) {
// If the list is empty or has only one node, return null
return nullptr;
}
Node* tail = head;
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;
return head;
}
// Function to remove the Kth element from the doubly linked list
Node* removeKthElement(Node* head, int k){
if(head==NULL){
return NULL;
}
int count = 0;
Node* kNode = head;
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){
return deleteHead(head);
}
else if(front == NULL){
return deleteTail(head);
}
prev->next = front;
front->back = prev;
kNode->next = NULL;
kNode->back = NULL;
delete kNode;
return head;
}
int main() {
vector<int> arr = {12, 5, 8, 7, 4};
Node* head = convertArr2DLL(arr);
print(head);
cout << endl << "Doubly Linked List after its 3rd element is removed: " << endl;
head = removeKthElement(head, 3);
print(head);
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
Node prev = head; // Initialize 'prev' to the head node
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
}
return head; // Return the head of the doubly linked list
}
// Function to delete the tail of the doubly linked list
private static Node deleteTail(Node head) {
if (head == null || head.next == null) {
return null; // Return null if the list is empty or contains only one element
}
Node tail = head;
while (tail.next != null) {
tail = tail.next;
}
Node newtail = tail.back;
newtail.next = null;
tail.back = null;
return head;
}
// Function to delete the head of the doubly linked list
private static Node deleteHead(Node head) {
if (head == null || head.next == null) {
return null; // Return null if the list is empty or contains only one element
}
Node prev = head;
head = head.next;
head.back = null; // Set 'back' pointer of the new head to null
prev.next = null; // Set 'next' pointer of 'prev' to null
return head;
}
// Function to print the elements of the doubly linked list
private static void print(Node head) {
while (head != null) {
System.out.print(head.data + " "); // Print the data in the current node
head = head.next; // Move to the next node
}
System.out.println();
}
// Function to remove the Kth element from the doubly linked list
private static Node removeKthElement(Node head, int k) {
if (head == null) {
return null;
}
int count = 0;
Node kNode = head;
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) {
return deleteHead(head);
} else if (front == null) {
return deleteTail(head);
}
prev.next = front;
front.back = prev;
kNode.next = null;
kNode.back = null;
return head;
}
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
print(head); // Print the doubly linked list
System.out.println("Doubly Linked List after deleting tail node: ");
head = deleteTail(head);
print(head);
}
}
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
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
# Function to print the elements of the doubly linked list
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()
# Function to delete the head of the doubly linked list
def delete_head(head):
if head is None or head.next is None:
# Return None if the list is empty or contains only one element
return None
# Store the current head as 'prev'
prev = head
# Move 'head' to the next node
head = head.next
# Set 'back' pointer of the new head to None
head.back = None
# Set 'next' pointer of 'prev' to None
prev.next = None
# Return the new head
return head
# Function to delete the tail of the doubly linked list
def delete_tail(head):
if head is None or head.next is None:
# If the list is empty or has only one node, return None
return None
tail = head
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
return head
# Function to remove the Kth element from the doubly linked list
def remove_kth_element(head, k):
if head is None:
return None
count = 0
k_node = head
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:
return delete_head(head)
elif front is None:
return delete_tail(head)
prev.next = front
front.back = prev
k_node.next = None
k_node.back = None
del k_node
return head
if __name__ == "__main__":
arr = [12, 5, 8, 7, 4]
head = convert_arr_to_dll(arr)
print_dll(head)
print("\nDoubly Linked List after its 3rd element is removed: ")
head = remove_kth_element(head, 3)
print_dll(head)
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
const 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
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;
}
// Return the head of the doubly linked list
return head;
}
// Function to print the elements of the doubly linked list
function printDLL(head) {
while (head !== null) {
// Print the data in the current node
console.log(head.data + " ");
// Move to the next node
head = head.next;
}
}
// Function to delete the head of the doubly linked list
function deleteHead(head) {
if (head === null || head.next === null) {
// Return null if the list is empty or contains only one element
return null;
}
// Store the current head as 'prev'
const prev = head;
// Move 'head' to the next node
head = head.next;
// Set 'back' pointer of the new head to null
head.back = null;
// Set 'next' pointer of 'prev' to null
prev.next = null;
// Return the new head
return head;
}
// Function to delete the tail of the doubly linked list
function deleteTail(head) {
if (head === null || head.next === null) {
// If the list is empty or has only one node, return null
return null;
}
let tail = head;
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;
return head;
}
// Function to remove the Kth element from the doubly linked list
function removeKthElement(head, k) {
if (head === null) {
return null;
}
let count = 0;
let kNode = head;
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) {
return deleteHead(head);
} else if (front === null) {
return deleteTail(head);
}
prev.next = front;
front.back = prev;
kNode.next = null;
kNode.back = null;
delete kNode;
return head;
}
const arr = [12, 5, 8, 7, 4];
let head = convertArrToDLL(arr);
printDLL(head);
console.log("\nDoubly Linked List after its 3rd element is removed: ");
head = removeKthElement(head, 3);
printDLL(head);
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.
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
