Lecture 218:- Circular Doubly Linked List

A circular doubly linked list is a linked list where each node has a pointer to both its previous and next nodes. In addition, the last node's "next" pointer points back to the head node, and the head node's "prev" pointer points to the last node, making it a circular structure.

Below is the C++ implementation of a CircularDoublyLinkedList class with methods to insert elements at the head and tail, delete elements, and display the circular doubly linked list in both forward and backward directions:

cppCopy code

#include <iostream> class Node { public:    int data;    Node* next;    Node* prev;    Node(int data) : data(data), next(nullptr), prev(nullptr) {} }; class CircularDoublyLinkedList { private:    Node* head;    Node* tail; public:    CircularDoublyLinkedList() : head(nullptr), tail(nullptr) {}    ~CircularDoublyLinkedList() {        if (!head)            return;        Node* current = head->next;        while (current != head) {            Node* temp = current;            current = current->next;            delete temp;        }        delete head;    }    void insertAtHead(int data) {        Node* newNode = new Node(data);        if (!head) {            head = newNode;            tail = newNode;            head->next = head;            head->prev = head;        } else {            newNode->next = head;            newNode->prev = tail;            head->prev = newNode;            tail->next = newNode;            head = newNode;        }    }    void insertAtTail(int data) {        Node* newNode = new Node(data);        if (!tail) {            head = newNode;            tail = newNode;            head->next = head;            head->prev = head;        } else {            newNode->next = head;            newNode->prev = tail;            head->prev = newNode;            tail->next = newNode;            tail = newNode;        }    }    void deleteHead() {        if (!head) {            std::cout << "List is empty. Nothing to delete." << std::endl;            return;        }        if (head == tail) {            delete head;            head = nullptr;            tail = nullptr;        } else {            Node* temp = head;            head = head->next;            head->prev = tail;            tail->next = head;            delete temp;        }    }    void deleteTail() {        if (!tail) {            std::cout << "List is empty. Nothing to delete." << std::endl;            return;        }        if (head == tail) {            delete head;            head = nullptr;            tail = nullptr;        } else {            Node* temp = tail;            tail = tail->prev;            tail->next = head;            head->prev = tail;            delete temp;        }    }    void displayForward() {        if (!head) {            std::cout << "List is empty." << std::endl;            return;        }        Node* current = head;        do {            std::cout << current->data << " -> ";            current = current->next;        } while (current != head);        std::cout << "HEAD" << std::endl;    }    void displayBackward() {        if (!tail) {            std::cout << "List is empty." << std::endl;            return;        }        Node* current = tail;        do {            std::cout << current->data << " -> ";            current = current->prev;        } while (current != tail);        std::cout << "TAIL" << std::endl;    } }; int main() {    CircularDoublyLinkedList list;    list.insertAtHead(1);    list.insertAtTail(2);    list.insertAtHead(3);    list.insertAtTail(4);    list.displayForward(); // Output: 3 -> 1 -> 2 -> 4 -> HEAD    list.displayBackward(); // Output: 4 -> 2 -> 1 -> 3 -> TAIL    list.deleteHead();    list.deleteTail();    list.displayForward(); // Output: 1 -> 2 -> HEAD    list.displayBackward(); // Output: 2 -> 1 -> TAIL    return 0; }

In this implementation, the CircularDoublyLinkedList class uses the Node class to represent each element of the circular doubly linked list. The insertAtHead and insertAtTail methods insert elements at the head and tail, respectively. The deleteHead and deleteTail methods delete elements from the head and tail, respectively.

The displayForward method displays the circular doubly linked list in the forward direction, starting from the head node and continuing until it reaches the head again. The displayBackward method displays the list in the backward direction, starting from the tail node and continuing until it reaches the tail again.

In the main function, we demonstrate how to use the CircularDoublyLinkedList class by creating a circular doubly linked list, inserting elements at the head and tail, and deleting elements from the head and tail. The output will show the circular doubly linked list in both forward and backward directions after each operation.