Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a Doubly Linked List?
3.2.
Why is the time complexity of deletion of elements from the mid is O(1) in DLL?
3.3.
What is the time complexity of pushing an element in front of the DLL?
4.
Conclusion
Last Updated: Mar 27, 2024

Delete a Node in a Doubly Linked List

Author Ankit kumar
0 upvote

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.

  1. Deletion of head node.
  2. Deletion of mid node.
  3. Deletion of last node.

 

All the three types can be handled easily if we carefully move the next and prev pointers.

Steps of Algorithm

  1. If the node/element to be deleted is the head/beginning node, then make the next node as the head node.
  2. If the node/element to be deleted is not the last node, then adjust the prev of del->next.
  3. If the node to be deleted is not the first node, then adjust the next of del->prev.
  4. 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;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output : 

5 9 4
You can also try this code with Online C++ Compiler
Run Code

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

Frequently Asked Questions

What is a Doubly Linked List?

A Doubly Linked List is a variation in linked list in which traversal is possible in both the directions,i.e., forward and backward, which is not available in a singly linked list.

Why is the time complexity of deletion of elements from the mid is O(1) in DLL?

Deletion of elements from the mid is O(1) in DLL because, in this case, one does not have to traverse the whole array to adjust the previous and next links, which is not in the case of a singly linked list.

What is the time complexity of pushing an element in front of the DLL?

The time complexity of pushing an element in front of the DLL would cost O(1) time as it does not need any traversal.

Conclusion

This article discussed the approach to deleting any given element from a doubly linked list. We talked about the simple algorithm, which takes a constant amount of time as well as space to execute.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Live masterclass