Deletion after a given node in Doubly Linked List: A Comprehensive Guide

Doubly Linked Lists are fundamental data structures that form the backbone of many algorithms and software systems. Unlike their simpler counterpart, the Singly Linked List, a Doubly Linked List (DLL) is characterized by each node storing references to both its previous and next nodes. This two-way connection enables traversing the list in either direction, making it versatile for various operations such as insertion, deletion, and traversal.

One crucial operation in DLLs is deleting a node after a given node. This post delves deeply into the theory and practical implementation of this operation, elaborating on every step and providing a robust C-language, C++, C#, Java, JavaScript, and Python Program to execute the task efficiently.

What is a Doubly Linked List?

A Doubly Linked List is a type of linked list where each node consists of three components:

• Data: The value stored in the node.
• Next Pointer: A reference to the next node in the sequence.
• Previous Pointer: A reference to the previous node in the sequence.

This dual-pointer system allows efficient traversal in both directions. However, it also makes DLLs slightly more complex than Singly Linked Lists due to the additional pointer management required during operations like insertion and deletion.

Why Focus on Node Deletion?

Deletion is a common and essential operation in all linked list types. In a Doubly Linked List, deleting a node is particularly interesting because it requires carefully adjusting both the next and prev pointers to maintain the list’s structural integrity. Specifically, deleting a node after a given node is a scenario that frequently arises in applications where sequential node relationships are manipulated dynamically.

Steps to Delete a Node After a Specific Node

The process involves identifying the node after the target node and removing it while updating the appropriate references. Here’s a detailed explanation of the steps:

• Identify the Target Node: Begin by iterating through the list to find the node containing the given key value. This node is referred to as the current node or curr.
• Check for Deletion Feasibility:
  • If the curr node is NULL, it implies the key does not exist in the list.
  • If curr->next is NULL, the current node is the last node, and there is no node to delete.
• Locate the Node to be Deleted: If curr and curr->next are valid, the node to be deleted is stored in a temporary pointer, say nodeDelete.
• Update Pointers:
  • Update curr->next to point to nodeDelete->next.
  • If nodeDelete->next is not NULL, adjust its prev pointer to reference curr.
• Free Memory: Finally, free the memory occupied by nodeDelete to avoid memory leaks.
• Return the Updated List: Return the head of the modified list to reflect the changes.

Code Implementation C Programming Language

Below is a C program that demonstrates how to delete a node after a specific node in a Doubly Linked List. The program is comprehensive and handles all edge cases:

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
};

// Function to delete a node after a given node in doubly linked list
struct Node *deleteAfter(struct Node *head, int key) {
    struct Node *curr = head;

    // Iterate over Linked List to find the key
    while (curr != NULL) {
        if (curr->data == key)
            break;
        curr = curr->next;
    }

    // If curr is NULL or curr->next is NULL, there is no node to delete
    if (curr == NULL || curr->next == NULL)
        return head;

    // Node to be deleted
    struct Node *nodeDelete = curr->next;

    // Update the next of the current node to the next of the node to be deleted
    curr->next = nodeDelete->next;

    // If the node to be deleted is not the last node, update the previous pointer of the next node
    if (nodeDelete->next != NULL) {
        nodeDelete->next->prev = curr;
    }

    // Free the memory of the node to be deleted
    free(nodeDelete);

    return head;
}

void printList(struct Node *head) {
    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

struct Node *createNode(int new_data) {
    struct Node *new_node = 
      (struct Node *)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = NULL;
    new_node->prev = NULL;
    return new_node;
}

int main() {
    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3 <-> 4
    struct Node *head = createNode(1);
    head->next = createNode(2);
    head->next->prev = head;
    head->next->next = createNode(3);
    head->next->next->prev = head->next;
    head->next->next->next = createNode(4);
    head->next->next->next->prev = head->next->next;

    head = deleteAfter(head, 2);
    printList(head);

    return 0;
}

Output:

1 2 4

Explanation of the Code

• Struct Definition: The Node structure defines the basic unit of the doubly linked list, containing data, next, and prev pointers.
• deleteAfter Function: This function carries out the deletion logic, updating pointers and freeing memory as necessary.
• Helper Functions:
  • createNode: Allocates and initializes new nodes.
  • printList: Traverses the list and prints node data.
• Main Function: Demonstrates the program with a hardcoded doubly linked list and applies the deletion operation on a specific node.

Code Implementation In Multiple Programming Languages

Here is the code written in C, C++, C#, Java, JavaScript, and Python, along with a detailed step-by-step explanation for each language.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
};

// Function to delete a node after a given node in doubly linked list
struct Node *deleteAfter(struct Node *head, int key) {
    struct Node *curr = head;

    // Iterate over Linked List to find the key
    while (curr != NULL) {
        if (curr->data == key)
            break;
        curr = curr->next;
    }

    // If curr is NULL or curr->next is NULL, there is no node to delete
    if (curr == NULL || curr->next == NULL)
        return head;

    // Node to be deleted
    struct Node *nodeDelete = curr->next;

    // Update the next of the current node to the next of the node to be deleted
    curr->next = nodeDelete->next;

    // If the node to be deleted is not the last node, update the previous pointer of the next node
    if (nodeDelete->next != NULL) {
        nodeDelete->next->prev = curr;
    }

    // Free the memory of the node to be deleted
    free(nodeDelete);

    return head;
}

void printList(struct Node *head) {
    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

struct Node *createNode(int new_data) {
    struct Node *new_node = 
      (struct Node *)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = NULL;
    new_node->prev = NULL;
    return new_node;
}

int main() {
    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3 <-> 4
    struct Node *head = createNode(1);
    head->next = createNode(2);
    head->next->prev = head;
    head->next->next = createNode(3);
    head->next->next->prev = head->next;
    head->next->next->next = createNode(4);
    head->next->next->next->prev = head->next->next;

    printf("Original Linked List:\n");
    printList(head);

    printf("\nDeleting Node with data 3 after Node with data 2:\n");
    head = deleteAfter(head, 2);
    printList(head);

    return 0;
}

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node* prev;
};

// Function to delete a node after a given node in doubly linked list
Node* deleteAfter(Node* head, int key) {
    Node* curr = head;

    // Iterate over Linked List to find the key
    while (curr != nullptr) {
        if (curr->data == key)
            break;
        curr = curr->next;
    }

    // If curr is NULL or curr->next is NULL, there is no node to delete
    if (curr == nullptr || curr->next == nullptr)
        return head;

    // Node to be deleted
    Node* nodeDelete = curr->next;

    // Update the next of the current node to the next of the node to be deleted
    curr->next = nodeDelete->next;

    // If the node to be deleted is not the last node, update the previous pointer of the next node
    if (nodeDelete->next != nullptr) {
        nodeDelete->next->prev = curr;
    }

    // Free the memory of the node to be deleted
    delete nodeDelete;

    return head;
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

Node* createNode(int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = nullptr;
    new_node->prev = nullptr;
    return new_node;
}

int main() {
    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3 <-> 4
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->prev = head;
    head->next->next = createNode(3);
    head->next->next->prev = head->next;
    head->next->next->next = createNode(4);
    head->next->next->next->prev = head->next->next;

    cout << "Original Linked List:" << endl;
    printList(head);

    cout << "\nDeleting Node with data 3 after Node with data 2:" << endl;
    head = deleteAfter(head, 2);
    printList(head);

    return 0;
}

using System;

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

class DoublyLinkedList {
    public static Node DeleteAfter(Node head, int key) {
        Node curr = head;

        // Iterate over Linked List to find the key
        while (curr != null) {
            if (curr.data == key)
                break;
            curr = curr.next;
        }

        // If curr is NULL or curr->next is NULL, there is no node to delete
        if (curr == null || curr.next == null)
            return head;

        // Node to be deleted
        Node nodeDelete = curr.next;

        // Update the next of the current node to the next of the node to be deleted
        curr.next = nodeDelete.next;

        // If the node to be deleted is not the last node, update the previous pointer of the next node
        if (nodeDelete.next != null) {
            nodeDelete.next.prev = curr;
        }

        return head;
    }

    public static void PrintList(Node head) {
        Node curr = head;
        while (curr != null) {
            Console.Write(curr.data + " ");
            curr = curr.next;
        }
        Console.WriteLine();
    }

    public static Node CreateNode(int newData) {
        Node newNode = new Node();
        newNode.data = newData;
        newNode.next = null;
        newNode.prev = null;
        return newNode;
    }

    public static void Main() {
        // Create a hardcoded doubly linked list:
        // 1 <-> 2 <-> 3 <-> 4
        Node head = CreateNode(1);
        head.next = CreateNode(2);
        head.next.prev = head;
        head.next.next = CreateNode(3);
        head.next.next.prev = head.next;
        head.next.next.next = CreateNode(4);
        head.next.next.next.prev = head.next.next;

        Console.WriteLine("Original Linked List:");
        PrintList(head);

        Console.WriteLine("\nDeleting Node with data 3 after Node with data 2:");
        head = DeleteAfter(head, 2);
        PrintList(head);
    }
}

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

    Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

public class DoublyLinkedList {
    public static Node deleteAfter(Node head, int key) {
        Node curr = head;

        // Iterate over Linked List to find the key
        while (curr != null) {
            if (curr.data == key)
                break;
            curr = curr.next;
        }

        // If curr is null or curr.next is null, there is no node to delete
        if (curr == null || curr.next == null)
            return head;

        // Node to be deleted
        Node nodeDelete = curr.next;

        // Update the next of the current node to the next of the node to be deleted
        curr.next = nodeDelete.next;

        // If the node to be deleted is not the last node, update the previous pointer of the next node
        if (nodeDelete.next != null) {
            nodeDelete.next.prev = curr;
        }

        return head;
    }

    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a hardcoded doubly linked list:
        // 1 <-> 2 <-> 3 <-> 4
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.prev = head;
        head.next.next = new Node(3);
        head.next.next.prev = head.next;
        head.next.next.next = new Node(4);
        head.next.next.next.prev = head.next.next;

        System.out.println("Original Linked List:");
        printList(head);

        System.out.println("\nDeleting Node with data 3 after Node with data 2:");
        head = deleteAfter(head, 2);
        printList(head);
    }
}

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

function deleteAfter(head, key) {
    let curr = head;

    // Iterate over Linked List to find the key
    while (curr !== null) {
        if (curr.data === key) break;
        curr = curr.next;
    }

    // If curr is null or curr.next is null, there is no node to delete
    if (curr === null || curr.next === null) return head;

    // Node to be deleted
    const nodeDelete = curr.next;

    // Update the next of the current node to the next of the node to be deleted
    curr.next = nodeDelete.next;

    // If the node to be deleted is not the last node, update the previous pointer of the next node
    if (nodeDelete.next !== null) {
        nodeDelete.next.prev = curr;
    }

    return head;
}

function printList(head) {
    let curr = head;
    while (curr !== null) {
        process.stdout.write(curr.data + " ");
        curr = curr.next;
    }
    console.log();
}

function main() {
    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3 <-> 4
    const head = new Node(1);
    head.next = new Node(2);
    head.next.prev = head;
    head.next.next = new Node(3);
    head.next.next.prev = head.next;
    head.next.next.next = new Node(4);
    head.next.next.next.prev = head.next.next;

    console.log("Original Linked List:");
    printList(head);

    console.log("\nDeleting Node with data 3 after Node with data 2:");
    const newHead = deleteAfter(head, 2);
    printList(newHead);
}

main();

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

def delete_after(head, key):
    curr = head

    # Iterate over Linked List to find the key
    while curr is not None:
        if curr.data == key:
            break
        curr = curr.next

    # If curr is None or curr.next is None, there is no node to delete
    if curr is None or curr.next is None:
        return head

    # Node to be deleted
    node_delete = curr.next

    # Update the next of the current node to the next of the node to be deleted
    curr.next = node_delete.next

    # If the node to be deleted is not the last node, update the previous pointer of the next node
    if node_delete.next is not None:
        node_delete.next.prev = curr

    return head

def print_list(head):
    curr = head
    while curr is not None:
        print(curr.data, end=" ")
        curr = curr.next
    print()

def main():
    # Create a hardcoded doubly linked list:
    # 1 <-> 2 <-> 3 <-> 4
    head = Node(1)
    head.next = Node(2)
    head.next.prev = head
    head.next.next = Node(3)
    head.next.next.prev = head.next
    head.next.next.next = Node(4)
    head.next.next.next.prev = head.next.next

    print("Original Linked List:")
    print_list(head)

    print("\nDeleting Node with data 3 after Node with data 2:")
    head = delete_after(head, 2)
    print_list(head)

main()

Output:

Original Linked List:
1 2 3 4 
Deleting Node with data 3 after Node with data 2:
1 2 4

Time Complexity and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the list. The linear traversal ensures that we visit each node once while searching for the key.
• Auxiliary Space: O(1). The operation does not use any additional space beyond a few pointers.

Key Takeaways

• Pointer Management: Properly updating the next and prev pointers is crucial to maintaining the list’s integrity after deletion.
• Edge Case Handling: Always check for scenarios like NULL pointers to avoid runtime errors.
• Memory Management: Freeing memory after deletion is necessary to prevent memory leaks.
• Versatility: The logic and implementation can be easily adapted for other linked list operations, demonstrating the flexibility of doubly linked lists.

Related Articles

• Deletion in a Doubly Linked List with Implementation: A Comprehensive Guide
• Deletion at the Beginning in a Doubly Linked List: A Detailed Exploration
• Deletion after a given node in Doubly Linked List: A Comprehensive Guide
• Deleting a Node Before a Given Node in a Doubly Linked List: A Detailed Exploration
• Deletion at a Specific Position in a Doubly Linked List: A Detailed Exploration
• Deletion at the End in Doubly Linked List: A Comprehensive Exploration

Read More Articles

• Data Structure (DS) Array:
  • Why the Analysis of Algorithms is Important?
  • Worst, Average, and Best Case Analysis of Algorithms: A Comprehensive Guide
  • Understanding Pointers in C Programming: A Comprehensive Guide
  • Understanding Arrays in Data Structures: A Comprehensive Exploration
  • Memory Allocation of an Array: An In-Depth Comprehensive Exploration
  • Understanding Basic Operations in Arrays: A Comprehensive Guide
  • Understanding 2D Arrays in Programming: A Comprehensive Guide
  • Mapping a 2D Array to a 1D Array: A Comprehensive Exploration
• Data Structure Linked List:
  • Understanding Linked Lists in Data Structures: A Comprehensive Exploration
  • Types of Linked List: Detailed Exploration, Representations, and Implementations
  • Understanding Singly Linked Lists: A Detailed Exploration
  • Understanding Doubly Linked List: A Comprehensive Guide
  • Operations of Doubly Linked List with Implementation: A Detailed Exploration
  • Insertion in Doubly Linked List with Implementation: A Detailed Exploration
  • Inserting a Node at the Beginning of a Doubly Linked List: A Detailed Exploration
  • Inserting a Node After a Given Node in a Doubly Linked List: A Detailed Exploration
  • Inserting a Node Before a Given Node in a Doubly Linked List: A Detailed Exploration
  • Inserting a Node at a Specific Position in a Doubly Linked List: A Detailed Exploration
  • Inserting a New Node at the End of a Doubly Linked List: A Detailed Exploration
  • Deletion in a Doubly Linked List with Implementation: A Comprehensive Guide
  • Deletion at the Beginning in a Doubly Linked List: A Detailed Exploration
  • Deletion after a given node in Doubly Linked List: A Comprehensive Guide
  • Deleting a Node Before a Given Node in a Doubly Linked List: A Detailed Exploration
  • Deletion at a Specific Position in a Doubly Linked List: A Detailed Exploration
  • Deletion at the End in Doubly Linked List: A Comprehensive Exploration

Frequently Asked Questions (FAQs)

What is a Doubly Linked List (DLL)?

A Doubly Linked List is a data structure consisting of a sequence of nodes, where each node contains three components:

• Data: The value stored in the node.
• Next Pointer: A reference to the next node in the sequence.
• Previous Pointer: A reference to the previous node in the sequence.

This structure allows traversal in both directions, making DLLs more versatile than Singly Linked Lists (SLLs). However, managing two pointers (next and previous) increases the complexity of operations such as insertion, deletion, and traversal.

Why are Doubly Linked Lists useful?

Doubly Linked Lists are especially useful in scenarios where bidirectional traversal or frequent updates are required. For example:

• Navigation Systems: Where you can move forward and backward between locations.
• Undo/Redo Functionality: Used in text editors or software applications.
• Deque Operations: Efficient implementation of double-ended queues.

Their additional pointer (previous) allows operations like deletion or insertion in O(1)O(1) time if the node reference is already available.

What does it mean to delete a node after a specific node?

In a DLL, “deleting a node after a specific node” means removing the node that comes immediately after a given node (identified by a key value). For example, if the list is 1 <-> 2 <-> 3 <-> 4 and the target node is 2, deleting the node after it will remove 3. The resulting list becomes 1 <-> 2 <-> 4.

What are the steps to delete a node after a specific node?

The process involves:

• Locating the target node using the given key value.
• Verifying that the target node exists and has a next node to delete.
• Storing a reference to the node to be deleted.
• Updating the next pointer of the target node and the prev pointer of the next node (if it exists).
• Freeing the memory occupied by the deleted node.

This ensures the structural integrity of the list while preventing memory leaks.

How do you handle edge cases during deletion?

Edge cases include:

• Key Not Found: If the node with the given key does not exist, no deletion occurs.
• Last Node: If the target node is the last node in the list (curr->next == NULL), there is no node to delete.
• Empty List: If the list is empty (head == NULL), the operation terminates without any action.

Proper checks in the program ensure these scenarios are handled gracefully.

Can the code handle the deletion of the last node?

No, the provided implementation cannot delete the last node because the deletion operation specifically targets the node after a given node. If the target node is the last node, curr->next will be NULL, and the function will terminate without any action.

To delete the last node, a different function targeting the tail of the list is required.

What is the time complexity of the deleteAfter function?

The time complexity of the deleteAfter function is:

• Best Case: O(1) if the target node is at the head of the list.
• Worst Case: O(n) if the target node is at the end of the list or does not exist.

Here, n is the total number of nodes in the list. The linear search for the target node contributes to the O(n) complexity.

How does the code ensure memory is not leaked?

After identifying the node to be deleted (nodeDelete), the program uses the free function to release the memory allocated for this node:

free(nodeDelete);

This prevents memory leaks by ensuring that no unused memory remains allocated after the operation.

Why is it important to update the previous pointer of the next node?

In a Doubly Linked List, the prev pointer of each node links it to its predecessor. When deleting a node, if the deleted node has a next node, its prev pointer must be updated to skip the deleted node and point to its new predecessor.

Failing to update this pointer results in a broken link, making the list traversal inaccurate or leading to runtime errors.

How is a node created in this program?

The createNode function dynamically allocates memory for a new node and initializes its components:

struct Node *createNode(int new_data) {
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = NULL;
    new_node->prev = NULL;
    return new_node;
}

This function ensures that each new node is properly set up before being added to the list.

What happens if the key value is repeated in the list?

If the key value appears multiple times in the list, the program deletes the node after the first occurrence of the key. To modify this behavior, the program would need to account for all occurrences by iterating through the entire list and applying the deletion logic at each match.

Can this code be adapted for other operations?

Yes, the structure and logic of this code can be modified to implement other operations like:

• Deleting the node before a specific node.
• Deleting a specific node by key.
• Inserting a node after or before a specific node.

The underlying principles of pointer manipulation remain consistent across these operations.

Why is the return value of the deleteAfter function the head of the list?

The deleteAfter function returns the updated head of the list to account for cases where the structure of the list might change (e.g., when the first node is deleted or modified). While the function does not alter the head in this specific implementation, returning it ensures the program is extensible and robust.

How is the list printed after deletion?

The printList function iterates through the list from the head node and prints the data of each node:

void printList(struct Node *head) {
    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

This ensures the updated list structure is correctly displayed after any operation.

How does the program handle multiple deletions?

The program can handle multiple deletions by repeatedly calling the deleteAfter function with different key values. Each call performs one deletion, and the updated list is passed as input for the subsequent operation.

For example:

head = deleteAfter(head, 2);
head = deleteAfter(head, 1);
printList(head);

This flexibility enables dynamic modifications to the list as required.