Table of Contents
In the given doubly linked list, delete a node
We can delete head node, middle node or last node.
Example
Algorithm
Time complexity : O(1)
Step 1 : create a function which takes a linked list and node that had to be deleted as arguments and delete the node.
Step 2 : If you want to delete a head node.
a)ย ย ย Change the head pointer to next of current node (head here).
b)ย ย ย Change the previous pointer of next node to current node previous.
Step 3 : If you want to delete middle node.
a)ย ย ย Change the previous pointer of next node to current node previous
b)ย ย ย Change the previous node next pointer to next of current node.
c)ย ย ย Delete the node. (current node)
d)ย ย ย If previous or next is NULL you need not delete them. (for deleting last node)
Step 4 : On the given linked list, call the function and give which node you want to delete.
Algorithm working Example
C++ Program
#include <bits/stdc++.h>
using namespace std;
struct DLL{
int data;
DLL *next;
DLL *prev;
};
void insertAtBeginning(struct DLL **head, int X)
{
struct DLL * curr = new DLL;
curr->data = X;
curr->prev = NULL;
curr->next = *head;
if(*head != NULL)
(*head)->prev = curr;
*head = curr;
}
void deleteNode(struct DLL **head, struct DLL *ptr)
{
if(*head == NULL || ptr == NULL)
return;
//if the node is head
if(*head == ptr)
*head = ptr->next;
//change the next and prev only if they are not null
if(ptr->next != NULL)
ptr->next->prev = ptr->prev;
if(ptr->prev != NULL)
ptr->prev->next = ptr->next;
delete(ptr); //delete the node
}
void display(struct DLL**head)
{
struct DLL*temp=*head;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
int main()
{
struct DLL *head = NULL;
insertAtBeginning(&head,6);
insertAtBeginning(&head,16);
insertAtBeginning(&head,15);
insertAtBeginning(&head,50);
insertAtBeginning(&head,1);
insertAtBeginning(&head,23);
cout<<"Current list is :- \n";
display(&head);
deleteNode(&head,head->next->next->next);
cout<<"\nAfter deleting the node doubly linked list it became :- \n";
display(&head);
}