How to Delete a Node in Doubly Linked List

As we already know that Linked list has various types, for a change we will see how a doubly linked list can be changed. Let’s just see a quick approach on deletion in doubly linked list. Basically we will be given a doubly linked list in which we will see deletion in doubly linked list or on how to delete a node in doubly linked list.

Problem Statement Understanding how to delete a node in doubly linked list.

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 delete 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 on how to delete a node in doubly linked list. is clear, so let’s see in the next section how we can approach this problem.

Approach on deletion in doubly linked list.

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 on deletion in doubly linked list.

  • 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 on deletion in doubly linked list.

Code Implementation on how to delete a node in doubly linked list.

#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.

Conclusion

So, in this blog, we have tried to explain how to delete a node in a doubly linked list. We have seen a complete approach, code implementation and Time complexity.If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this Link.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Student management system using linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. Why is a doubly linked list called a two way list?
  2. A doubly linked list has a pointer which points to the next node and the previous node as well. Which makes the linked list traverse in both directions, that’s why it is called a two way list.

  3. What are the operations which can be performed on doubly linked list?
  4. The operations performed on doubly linked list are:

    • Insertion of a node at the beginning.
    • Insertion of node in the middle.
    • Insertion of node at the end.
    • Deleting a node at the beginning.
    • Deleting a node in the middle.
    • Deleting a node at the end.
  5. How do you delete the node at a specific position in doubly linked list?
  6. To delete a node in doubly linked list:

    • We have to find the previous node which has to be deleted.
    • The next of the previous node has to be changed.
    • The memory of the node which has to be deleted has to be freed.

Leave a Reply

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