Introduction
This blog will discuss the approach to deleting a node from a doubly linked list. Before jumping on the approach to the problem, let us first understand the problem.
Problem Statement
Given a node, write a function to delete it from a doubly linked list. That means you will be given the head of the Doubly Linked List and a node to be deleted.
Sample Example
Input : Node to be deleted - 3
Output :
Also see, Rabin Karp Algorithm
Approach
This problem can be segmented into three types.
- Deletion of head node.
- Deletion of mid node.
- Deletion of last node.
All the three types can be handled easily if we carefully move the next and prev pointers.
Steps of Algorithm
- If the node/element to be deleted is the head/beginning node, then make the next node as the head node.
- If the node/element to be deleted is not the last node, then adjust the prev of del->next.
- If the node to be deleted is not the first node, then adjust the next of del->prev.
- Finally, free the memory occupied by del.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node* next;
Node* prev;
};
//function to delete a given node from a doubly linked list
void deleteNodeinDLL(Node** head_ref, Node* del)
{
/* base case */
if (*head_ref == NULL || del == NULL)
return;
/* If node to be deleted is the head node */
if (*head_ref == del)
*head_ref = del->next;
/* If node to be
deleted is NOT the last node */
if (del->next != NULL)
del->next->prev = del->prev;
/* If node to be
deleted is NOT the first node */
if (del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
Delete del;
return;
}
//function to insert node at the beginning of the DLL
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
int main(){
Node* head = NULL;
push(&head, 4);
push(&head, 9);
push(&head, 3);
push(&head, 5);
//Calling the delete function
deleteNodeinDLL(&head,head->next);
//Printing the resultant DLL
Node* curr = head;
while(curr != NULL){
cout<<curr->data<<" ";
Curr = curr->next;
}
return 0;
}
Output :
5 9 4
Also read - Merge sort in linked list
Complexity Analysis
Time Complexity : O(1)
Since the traversal is not required here as in a singly linked list, therefore the time complexity is constant in order.
Space Complexity : O(1)
As not any extra space is required apart from a given DLL, therefore space complexity is constant in order.
Recommended Topic, Floyds Algorithm and Data Structure