Deletion in Doubly Linked List

Nodes can be removed from the double link list from any location such as front, end, or any other specific location or specific data.

When you remove a node from the list of double links, first relocate the pointer to that particular node so that the previous and next nodes do not connect to the node you want to remove. Then you can easily remove the node.

Consider the following list of double-linked lists with three nodes A, B, and C. Suppose you need to remove node B.

deletion

We have shown that node B will be removed from the specified linked list, as shown in the series of figures above. The order of operations remains the same whether the node is first or last. The only thing to note is that if the first node is removed, the pointer before the second node will be set to null.

Similarly, when the last node is removed, the next pointer to the previous node is set to null. If you remove the nodes between the nodes, the sequence will look like the one above.

For example:

deletion

deletion

Here Code:

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node *prev, *next;
};
void deleteNode(Node** head_ref, Node* del) {
   if (*head_ref == NULL || del == NULL) {
      return;
   }
   if (*head_ref == del) {
      *head_ref = del->next;
   }
   if (del->next != NULL) {
      del->next->prev = del->prev;
   }
   if (del->prev != NULL) {
      del->prev->next = del->next;
   }
   free(del);
   return;
}
void insertNode(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->prev = NULL;
   new_node->next = (*head_ref);
   if ((*head_ref) != NULL) {
      (*head_ref)->prev = new_node;
   }
   (*head_ref) = new_node;}
void printLinkedList(Node* node) {
   while (node != NULL) {
      cout << node->data << " -> ";
      node = node->next;}}
int main() {
   Node* head = NULL;
   insertNode(&head, 1);
   insertNode(&head, 2);
   insertNode(&head, 3);
   insertNode(&head, 4);
   cout << "Linked List before deletion:" << endl;
   printLinkedList(head);
   deleteNode(&head, head->next);
   cout << "\nLinked List after deletion:" << endl;
   printLinkedList(head);
   return 0;
}

Deletion operation:

The delete operation removes the node from a specific location in the double-link list.

  • Deletion of the first node: Deletes the first node in the list.
  • Deletion of the last node: Deletes the last node in the list.
  • Deletion of a node given the data: When data is specified, the operation matches the data with the data of the node in the linked list and deletes the node.
The following C ++ program shows all delete operations in a double-linked list.

For example:

deletion

deletion

deletion

Here Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
          public:
          int data;
          Node* next;
          Node* prev;
};
void deleteNode(Node** head_ref, Node* del)
{
          if (*head_ref == NULL || del == NULL)
                   return;
          if (*head_ref == del)
                   *head_ref = del->next;
          if (del->next != NULL)
                   del->next->prev = del->prev;
          if (del->prev != NULL)
                   del->prev->next = del->next;
          free(del);
          return;
}
void push(Node** head_ref, int new_data)
{
          Node* new_node = new Node();
          new_node->data = new_data;
          new_node->prev = NULL;
          new_node->next = (*head_ref);
          if ((*head_ref) != NULL)
                   (*head_ref)->prev = new_node;
          (*head_ref) = new_node;
}
void printList(Node* node)
{
          while (node != NULL)
          {
                   cout << node->data << " ";
                   node = node->next;
          }
}
int main()
{
          Node* head = NULL;
          push(&head, 2);
          push(&head, 4);
          push(&head, 8);
          push(&head, 10);
          cout << "Original Linked list ";
          printList(head);
          /*delete first node*/
          deleteNode(&head, head);
          /*delete middle node*/
          deleteNode(&head, head->next);
          /*delete last node*/
          deleteNode(&head, head->next);
          cout << "\nModified Linked list ";
          printList(head);
          return 0;
}

Complexity Analysis:

  • Time Complexity: O(1): Time complexity is constant because the linked list is not required to be scanned.
  • Space Complexity: O(1): Spatial complexity is constant because no additional space is needed.

Recommended Articles:

  1. Insertion in Doubly Linked List
  2. How to reverse a doubly linked list?
  3. QuickSort on Doubly Linked List
  4. Merge Sort for Doubly Linked List
  5. Deletion in Linked List

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 113 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] Deletion in Doubly Linked List […]

You cannot copy content of this page
Scroll Up
1
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.