Deletion in Doubly Linked List

Introduction:

A doubly linked list is a type of linked list in which each node contains a data part and two pointers, one pointing to the next node and the other pointing to the previous node. Deleting a node in a doubly linked list involves adjusting these pointers to remove the node from the sequence.

Steps for Deletion:

The deletion process can be broken down into several steps:

1. Identify the node to be deleted.
2. Adjust the pointers of the previous and next nodes to bypass the node to be deleted.
3. Free the memory of the node to be deleted.

Diagrammatic Representation:

      Step 1: Identify node to delete
      [Prev] <-> [Data | Next] <-> [Data | Next] <-> [Data | Next] <-> [Next]
      
      Step 2: Adjust pointers
      [Prev] <-> [Data | Next]       [Data | Next] <-> [Next]
      
      Step 3: Free memory
      [Prev] <-> [Data | Next] <-> [Next]
    

Java Code Example:

        class Node {
          int data;
          Node prev;
          Node next;
          
          Node(int data) {
            this.data = data;
          }
        }
        
        class DoublyLinkedList {
          Node head;
          
          public void deleteNode(Node del) {
            if (head == null || del == null) {
              return;
            }
            
            if (head == del) {
              head = del.next;
            }
            
            if (del.next != null) {
              del.next.prev = del.prev;
            }
            
            if (del.prev != null) {
              del.prev.next = del.next;
            }
            
            del = null;
          }
        }
      

Explanation of Code:

The above code defines a simple structure for a doubly linked list and demonstrates how to delete a node. It checks if the node to be deleted is the head, and if so, it updates the head pointer. It then adjusts the previous and next pointers of the neighboring nodes to exclude the node being deleted.

Use Cases:

Doubly linked lists are useful in scenarios where bidirectional traversal is required, such as in navigation systems or undo-redo functionality in software applications.