Lecture 214:- Deleting from Doubly Linked List

To delete elements from a doubly linked list, you can consider several scenarios:

1. Delete the head node.
2. Delete the tail node.
3. Delete a node at a specific position.
4. Delete the only node in the list.
5. Delete a node with a given key.

Below is the C++ implementation of the DoublyLinkedList class with methods to delete elements based on the scenarios mentioned above:

cppCopy code

#include <iostream> class Node { public:    int data;    Node* next;    Node* prev;    Node(int data) : data(data), next(nullptr), prev(nullptr) {} }; class DoublyLinkedList { private:    Node* head;    Node* tail; public:    DoublyLinkedList() : head(nullptr), tail(nullptr) {}    ~DoublyLinkedList() {        Node* current = head;        while (current) {            Node* temp = current;            current = current->next;            delete temp;        }    }    void insertAtHead(int data) {        Node* newNode = new Node(data);        if (!head) {            head = newNode;            tail = newNode;        } else {            newNode->next = head;            head->prev = newNode;            head = newNode;        }    }    void insertAtTail(int data) {        Node* newNode = new Node(data);        if (!tail) {            head = newNode;            tail = newNode;        } else {            newNode->prev = tail;            tail->next = newNode;            tail = newNode;        }    }    void deleteHead() {        if (!head) {            std::cout << "List is empty. Nothing to delete." << std::endl;            return;        }        Node* temp = head;        head = head->next;        if (head) {            head->prev = nullptr;        } else {            tail = nullptr;        }        delete temp;    }    void deleteTail() {        if (!tail) {            std::cout << "List is empty. Nothing to delete." << std::endl;            return;        }        Node* temp = tail;        tail = tail->prev;        if (tail) {            tail->next = nullptr;        } else {            head = nullptr;        }        delete temp;    }    void deleteAtPosition(int position) {        if (!head) {            std::cout << "List is empty. Nothing to delete." << std::endl;            return;        }        if (position <= 0) {            deleteHead();        } else {            Node* current = head;            int count = 0;            while (count < position && current) {                current = current->next;                count++;            }            if (count == position) {                if (current->prev) {                    current->prev->next = current->next;                } else {                    head = current->next;                }                if (current->next) {                    current->next->prev = current->prev;                } else {                    tail = current->prev;                }                delete current;            } else {                std::cout << "Invalid position. Deletion failed." << std::endl;            }        }    }    void deleteByKey(int key) {        if (!head) {            std::cout << "List is empty. Nothing to delete." << std::endl;            return;        }        Node* current = head;        while (current && current->data != key) {            current = current->next;        }        if (current && current->data == key) {            if (current->prev) {                current->prev->next = current->next;            } else {                head = current->next;            }            if (current->next) {                current->next->prev = current->prev;            } else {                tail = current->prev;            }            delete current;        } else {            std::cout << "Element with key " << key << " not found in the list." << std::endl;        }    }    void displayForward() {        if (!head) {            std::cout << "List is empty." << std::endl;            return;        }        Node* current = head;        while (current) {            std::cout << current->data << " -> ";            current = current->next;        }        std::cout << "NULL" << std::endl;    }    void displayBackward() {        if (!tail) {            std::cout << "List is empty." << std::endl;            return;        }        Node* current = tail;        while (current) {            std::cout << current->data << " -> ";            current = current->prev;        }        std::cout << "NULL" << std::endl;    } }; int main() {    DoublyLinkedList list;    list.insertAtHead(1);    list.insertAtHead(2);    list.insertAtTail(3);    list.insertAtTail(4);    list.displayForward(); // Output: 2 -> 1 -> 3 -> 4 -> NULL    list.deleteHead();    list.deleteTail();    list.deleteAtPosition(1);    list.deleteByKey(3);    list.displayForward(); // Output: 1 -> NULL    return 0; }

In this implementation, we've added two new methods to the DoublyLinkedList class: deleteAtPosition and deleteByKey. These methods allow us to delete elements from the doubly linked list based on the position or the key (value) of the node to be deleted.

The deleteAtPosition method deletes the node at the specified position (0-based) in the doubly linked list. If the position is less than or equal to 0, it deletes the head node. If the position is greater than or equal to the number of elements, it displays an error message.

The deleteByKey method searches for the first occurrence of the node with the given key (data) in the doubly linked list and deletes it. If the node with the given key is not found, it displays an error message.

In the main function, we demonstrate how to use the DoublyLinkedList class by creating a doubly linked list, inserting elements at the head and tail, and deleting elements using different methods. The output will be 2 -> 1 -> 3 -> 4 -> NULL for the initial list and 1 -> NULL after the deletions.