Lecture 212:- Insert In A Doubly Linked List

To insert an element into a doubly linked list, you can consider three scenarios:

1. Insert at the beginning (head) of the doubly linked list.
2. Insert at the end (tail) of the doubly linked list.
3. Insert at a specific position in the doubly linked list.

Here's a C++ implementation for inserting elements into a doubly linked list:

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 insertAtPosition(int data, int position) {        if (position <= 0) {            insertAtHead(data);        } else if (!head) {            std::cout << "List is empty. Cannot insert at position." << std::endl;        } else {            Node* newNode = new Node(data);            Node* current = head;            int count = 0;            while (count < position - 1 && current->next) {                current = current->next;                count++;            }            if (count == position - 1) {                newNode->prev = current;                newNode->next = current->next;                if (current->next) {                    current->next->prev = newNode;                } else {                    tail = newNode;                }                current->next = newNode;            } else {                std::cout << "Invalid position. Insertion failed." << std::endl;                delete newNode;            }        }    }    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.insertAtPosition(4, 1);    list.displayForward(); // Output: 2 -> 4 -> 1 -> 3 -> NULL    list.displayBackward(); // Output: 3 -> 1 -> 4 -> 2 -> NULL    return 0; }

In this implementation, we've added a new method insertAtPosition to the DoublyLinkedList class to insert an element at a specific position in the doubly linked list. The method covers all the scenarios for inserting an element in a doubly linked list.

The method starts by checking if the position is less than or equal to 0. If it is, we insert the node at the head using the insertAtHead method. If the list is empty, we cannot insert at a position other than the head, so we display an error message.

Next, we traverse the list to find the node at the position before the desired insertion position. We then create a new node and adjust the pointers to insert the new node after the found position node. If the position is invalid (greater than the number of elements), we display an error message and delete the new node.

In the main function, we demonstrate how to use the DoublyLinkedList class by creating a doubly linked list, inserting elements at the head, tail, and at a specific position, and displaying the doubly linked list in both forward and backward directions. The output will be 2 -> 4 -> 1 -> 3 -> NULL for forward direction and 3 -> 1 -> 4 -> 2 -> NULL for backward direction after the insertions.