Delete a node in Doubly Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

We will be given a Doubly Linked List and a node from the doubly linked list in this problem. Our task will be to delete the given node from the doubly linked list.

Problem Statement Understanding

Let’s learn programming languages online and try to understand the problem statement with the help of an example.

If the given doubly linked list is head ↔ 4 ↔ 5 ↔ 7 ↔ 6 ↔ 2 ↔ 1 ↔ 9 and the node to be deleted is head→next→next.

  • According to the problem statement, we will have to delete the node head→next→next from the doubly linked list.
  • In the above given linked list, the head→next→next is the node with value 7. So we will have to delete this node.
  • So after deleting this node from the doubly linked list, our doubly linked list will be head ↔ 4 ↔ 5 ↔ 6 ↔ 2 ↔ 1 ↔ 9.

While deleting a node temp in a doubly linked list, we must take care of the links of the following nodes, the node temp which we want to delete, the immediate previous node to temp and the immediate next node of the temp by changing the next of the previous node of temp as the next of temp and the previous of the next node of temp as the previous of temp.

  • temp→next→prev = temp→prev
  • temp→prev→next = temp→next
  • delete(temp)

In the above example, the node we intended to delete was somewhere in the middle of the linked list. But if we wish to detete a node that is either the head or the tail of the doubly linked list, we will delete it a little differently, which we will see in the next section.

Now I think from the above example, the problem statement is clear, so let’s see in the next section how we can approach this problem.

Approach

While deleting a node from a doubly linked list, there can be 3 cases:
Case1: If the node to be deleted is the head node.

Case2: If the node to be deleted is somewhere in the middle of the linked list.

Case3: If the node to be deleted is the tail of the linked list.

Algorithm

  • If the node temp which we want to delete is NULL or the head is NULL, we will simply return.
  • Then we will check if temp is a head node or not.
    • If temp is the head node, then we will move head to head→next.
  • If the prev of temp is not NULL, we will change the prev of the next of temp to the prev of temp.
  • If the next of temp is not NULL, we will change the next of the prev of temp to the next of temp.
  • Finally, we will free the space allocated to the temp.
  • After all the above steps, the node temp will be deleted from the Doubly Linked List.

Dry Run

Code Implementation

#include 
using namespace std;

class DLLNode
{
	public:
	int data;
	DLLNode* next;
	DLLNode* prev;
};

void deleteNodefromList(DLLNode** head, DLLNode* temp)
{
	if (*head == NULL || temp == NULL)
		return;

	if (*head == temp)
		*head = temp->next;

	if (temp->next != NULL)
		temp->next->prev = temp->prev;

	if (temp->prev != NULL)
		temp->prev->next = temp->next;

	free(temp);
	return;
}

void push(DLLNode** head, int new_data)
{
	DLLNode* new_node = new DLLNode();

	new_node->data = new_data;

	new_node->prev = NULL;

	new_node->next = (*head);

	if ((*head) != NULL)
		(*head)->prev = new_node;

	(*head) = new_node;
}

void printList(DLLNode* node)
{
	while (node != NULL)
	{
		cout << node->data << " ";
		node = node->next;
	}
}

int main()
{
	DLLNode* head = NULL;
	push(&head, 3);
	push(&head, 8);
	push(&head, 10);
	push(&head, 7);
    push(&head, 2);
	push(&head, 6);
	push(&head, 1);
	push(&head, 5);
	deleteNodefromList(&head, head->next); 
	printList(head);

	return 0;
}
public class Prepbytes {

    public static class DLL {
        Node head;

        class Node {
            int data;
            Node prev;
            Node next;

            Node(int d) {
                data = d;
            }
        }

        public void push(int new_data) {
            Node new_Node = new Node(new_data);
            new_Node.next = head;
            new_Node.prev = null;

            if (head != null)
                head.prev = new_Node;

            head = new_Node;
        }

        public void printlist(Node node) {
            Node last = null;

            while (node.next != null) {
                System.out.print(node.data + " ");
                last = node;
                node = node.next;
            }

            System.out.println(node.data);
        }

        void deleteNode(Node temp) {

            if (head == null || temp == null) {
            return;
            }
            if (head == temp) {
                head = head.next;
            }

            if (temp.next != null) {
                temp.next.prev = temp.prev;
            }

            if (temp.prev != null) {
                temp.prev.next = temp.next;
            }

            return;
        }
    }

    public static void main(String[] args) {
        DLL dll = new DLL();
        dll.push(3);
        dll.push(8);
        dll.push(10);
        dll.push(7);
        dll.push(2);
        dll.push(6);
        dll.push(1);
        dll.push(5);
        dll.deleteNode(dll.head.next);

        dll.printlist(dll.head);
    }
}

Output

5 6 2 7 10 8 3

Time Complexity: O(1), as we do not need to do the traversal of the linked list.

So, in this blog, we have tried to explain how you can delete a node from a Doubly Linked List. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post A Brief Introduction to Linked Lists
Next post C program for performing Bubble sort on Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *