Problem Statement: Given a node’s reference within a doubly linked list (it is guaranteed not to be the head), the task is to remove that node while preserving the list’s integrity.
Examples
Example 1:
Input Format:
DLL: 3 <-> 2 <-> 5 <-> 1 <-> 3 Given Node: 5
Result: DLL: 3 <-> 2 <-> 1 <-> 3
Explanation: The given node of value 5 has been deleted from the list.
Example 2:
Input Format:
DLL: 7 <-> 5 Given Node: 5
Result: DLL: 7
Explanation: The given node was the tail node of the doubly linked list and it will be deleted.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach:
Given a node` temp` in a doubly linked list, our goal is to remove it while maintaining list integrity. The intuition is to make sure that
– the last node before the ‘temp’ node should have its next pointer pointing to the node after the ‘temp’ node. – the node after ‘temp’ should have its back pointer pointing to the node before ‘temp’.
Algorithm
Step 1: Given the node temp, identify its previous node prev and next node front. This can be easily done using the back and next pointer of the given node ‘temp’
Step 2: Update the next of the prev to point to the front. Update the back of the front to point to prev.
Step 3: Set temp’s next and back to null to fully disconnect it.
Step 4: Delete temp (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;
}
}
void deleteNode(Node* temp){
Node* prev = temp->back;
Node* front = temp->next;
// edge case if temp is the tail node
if(front==NULL){
prev->next = nullptr;
temp->back = nullptr;
free (temp);
return;
}
//Disconnect temp from the doubly linked list
prev->next = front;
front->back = prev;
// Set temp's pointers to NULL
temp->next = nullptr;
temp->back = nullptr;
// Free memory of the deleted node
free(temp);
return;
}
int main() {
vector<int> arr = {12, 5, 8, 7, 4};
Node* head = convertArr2DLL(arr);
print(head);
cout << endl << "Doubly Linked List after node with data '5' is removed: " << endl;
deleteNode(head->next);
print(head);
return 0;
}
Output:
12 5 8 7 4 Doubly Linked List after node with data ‘5’ is removed: 12 8 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;
}
}
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 deleteNode(Node temp){
Node prev = temp.back;
Node front = temp.next;
// edge case if temp is the tail node
if(front==null){
prev.next = null;
temp.back = null;
return;
}
//Disconnect temp from the doubly linked list
prev.next = front;
front.back = prev;
// Set temp's pointers to null
temp.next = null;
temp.back = null;
// Free memory of the deleted node
return;
}
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();
}
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 node with value '5': ");
deleteNode(head.next);
print(head);
}
}
Output:
12 5 8 7 4 Doubly Linked List after node with data ‘5’ is removed: 12 8 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
class Node:
def __init__(self, data, next_node=None, back_node=None):
self.data = data
self.next = next_node
self.back = back_node
def convert_arr_to_dll(arr):
head = Node(arr[0])
prev = head
for i in range(1, len(arr)):
temp = Node(arr[i], None, prev)
prev.next = temp
prev = temp
return head
def print_dll(head):
while head is not None:
print(head.data, end=" ")
head = head.next
print()
def delete_node(temp):
prev = temp.back
front = temp.next
if front is None:
prev.next = None
temp.back = None
del temp
return
prev.next = front
front.back = prev
temp.next = None
temp.back = None
del temp
if __name__ == "__main__":
arr = [12, 5, 8, 7, 4]
head = convert_arr_to_dll(arr)
print_dll(head)
print("\nDoubly Linked List after node with data '5' is removed:")
delete_node(head.next)
print_dll(head)
Output:
12 5 8 7 4 Doubly Linked List after node with data ‘5’ is removed: 12 8 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 a node with the specified data
function deleteNode(temp) {
const prev = temp.back;
const front = temp.next;
// Edge case if temp is the tail node
if (front === null) {
prev.next = null;
temp.back = null;
// Delete the node
delete temp;
return;
}
// Disconnect temp from the doubly linked list
prev.next = front;
front.back = prev;
// Set temp's pointers to null
temp.next = null;
temp.back = null;
// Delete the node
delete temp;
}
const arr = [12, 5, 8, 7, 4];
const head = convertArrToDLL(arr);
printDLL(head);
console.log("\nDoubly Linked List after node with data '5' is removed:");
deleteNode(head.next);
printDLL(head);
Output:
12 5 8 7 4 Doubly Linked List after node with data ‘5’ is removed: 12 8 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
