**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__