Delete a node in doubly linked list

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

Reference

Translate ยป