Deletion in Linked List | DSA in C++ - Software Development PDF Download

Introduction

Linked lists are popular data structures in computer science and are used to store and manipulate collections of data. One common operation performed on linked lists is deletion, which involves removing a specific node from the list. In this article, we will explore the concepts of deletion in linked lists using C++ and provide simple code examples with explanations to help beginners understand the process.

Overview of Linked Lists

A linked list is a linear data structure that consists of nodes linked together via pointers. Each node contains two components: a data element and a pointer that points to the next node in the list. The last node in the list points to NULL, indicating the end of the list. Linked lists are dynamic in nature, allowing for efficient insertion and deletion of elements.

Deletion in Linked Lists

To delete a node from a linked list, we need to adjust the pointers of the surrounding nodes to bypass the node to be deleted. There are three common cases to consider when deleting a node:

• Deleting the first node
• Deleting a middle node
• Deleting the last node

Code Examples

Deleting the First Node:

To delete the first node of a linked list, we need to update the head pointer to point to the next node.

void deleteFirstNode(Node*& head) {

    if (head == NULL) {

        return;  // Nothing to delete, list is empty

    }

    Node* temp = head;

    head = head->next;

    delete temp;

}

Output:

Before deletion: 1 -> 2 -> 3 -> NULL

After deletion: 2 -> 3 -> NULL

Explanation: In this example, the function 'deleteFirstNode' takes the head pointer of the linked list as a parameter. It checks if the list is empty by verifying if the head pointer is NULL. If the list is not empty, it creates a temporary pointer 'temp' to store the address of the first node. Then, it updates the head pointer to point to the second node and deletes the temporary pointer, effectively removing the first node from the list.

Deleting a Middle Node

To delete a middle node from a linked list, we need to update the pointers of the previous node and the next node to bypass the node to be deleted.

void deleteMiddleNode(Node*& head, int key) {

    Node* current = head;

    Node* previous = NULL;

    while (current != NULL && current->data != key) {

        previous = current;

        current = current->next;

    }

    if (current == NULL) {

        return;  // Node not found

    }

    previous->next = current->next;

    delete current;

}

Output:

Before deletion: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

After deletion of key=3: 1 -> 2 -> 4 -> 5 -> NULL

Explanation: The 'deleteMiddleNode' function takes the head pointer and a key value as parameters. It uses two pointers, 'current' and 'previous', to traverse the linked list until it finds the node with the specified key or reaches the end of the list. If the key is not found, the function returns. Otherwise, it updates the 'next' pointer of the previous node to skip the current node and deletes the current node, effectively removing it from the list.

Deleting the Last Node:

To delete the last node of a linked list, we need to update the 'next' pointer of the second-to-last node to NULL.

void deleteLastNode(Node*& head) {

    if (head == NULL) {

        return;  // Nothing to delete, list is empty

    }

    if (head->next == NULL) {

        delete head;

        head = NULL;

        return;  // List contained only one node

    }

    Node* current = head;

    while (current->next->next != NULL) {

        current = current->next;

    }

    delete current->next;

    current->next = NULL;

}

Output:

Before deletion: 1 -> 2 -> 3 -> 4 -> NULL

After deletion: 1 -> 2 -> 3 -> NULL

Explanation: The 'deleteLastNode' function first checks if the list is empty or contains only one node. If so, it deletes the single node and updates the head pointer accordingly. Otherwise, it uses a loop to traverse the list until it reaches the second-to-last node. It then deletes the last node and updates the 'next' pointer of the second-to-last node to NULL.

Sample Problems

Here are some sample problems related to deletion in linked lists:

Problem 1: Write a function to delete all occurrences of a given key in a linked list.

void deleteAllOccurrences(Node*& head, int key) {

    Node* current = head;

    Node* previous = NULL;

    while (current != NULL) {

        if (current->data == key) {

            if (previous == NULL) {

                head = current->next;

            } else {

                previous->next = current->next;

            }

            Node* temp = current;

            current = current->next;

            delete temp;

        } else {

            previous = current;

            current = current->next;

        }

    }

}

Problem 2: Write a function to delete the nth node from the end of a linked list.

void deleteNthNodeFromEnd(Node*& head, int n) {

    Node* slow = head;

    Node* fast = head;

    // Move the fast pointer n positions ahead

    for (int i = 0; i < n; i++) {

        if (fast == NULL) {

            return;  // List size is less than n

        }

        fast = fast->next;

    }

    // If the list contained exactly n nodes

    if (fast == NULL) {

        head = head->next;

        delete slow;

        return;

    }

    // Move both pointers until the fast pointer reaches the end

    while (fast->next != NULL) {

        slow = slow->next;

        fast = fast->next;

    }

    Node* temp = slow->next;

    slow->next = slow->next->next;

    delete temp;

}

Conclusion

In this article, we explored the concept of deletion in linked lists using C++. We discussed the process of deleting the first, middle, and last nodes of a linked list, along with code examples and explanations. We also provided sample problems with solutions to further reinforce the understanding of deletion operations. With this knowledge, you can now manipulate linked lists by deleting nodes efficiently.