সি++-এ ডাবলি লিংকড সার্কুলার লিস্ট

ডাবলি লিংকড সার্কুলার লিস্টে লাস্ট নোডের `next` ফার্স্ট নোডকে পয়েন্ট করে এবং ফার্স্ট নোডের `prev` লাস্ট নোডকে পয়েন্ট করে। এটি উভয় দিকে সার্কুলার।

এলগরিদম (মূল অপারেশন)

displayForward(): head থেকে next ফলো করে প্রিন্ট
displayBackward(): last থেকে prev ফলো করে প্রিন্ট
insertFirst(key, data): হেডে নোড যোগ
insertLast(key, data): লাস্টে নোড যোগ
insertAfter(key, newKey, data): নির্দিষ্ট কীর পরে ইনসার্ট
deleteFirst(): হেড ডিলিট
deleteLast(): লাস্ট ডিলিট
deleteNode(key): নির্দিষ্ট কী ওয়ালা নোড ডিলিট

উদাহরণ কোড

#include <iostream> 
using namespace std; 

class node {
public:
    int data, key;
    node *next, *prev;
};

node *head = NULL, *last = NULL;

bool isEmpty(){ return head == NULL; }

void displayForward(){
    node *ptr = head;
    cout << "\n[ ";
    while(ptr != NULL){
        cout << "(" << ptr->key << "," << ptr->data << ") ";
        ptr = ptr->next;
    }
    cout << "]";
}

void displayBackward(){
    node *ptr = last;
    cout << "\n[ ";
    while(ptr != NULL){
        cout << "(" << ptr->key << "," << ptr->data << ") ";
        ptr = ptr->prev;
    }
    cout << "]";
}

void insertFirst(int key, int data){
    node *link = new node();
    link->key = key; link->data = data;
    if(isEmpty()) last = link;
    else head->prev = link;
    link->next = head;
    head = link;
}

void insertLast(int key, int data){
    node *link = new node();
    link->key = key; link->data = data;
    if(isEmpty()) last = link;
    else { last->next = link; link->prev = last; }
    last = link;
}

node* deleteFirst(){
    node *temp = head;
    if(head->next == NULL) last = NULL;
    else head->next->prev = NULL;
    head = head->next;
    return temp;
}

node* deleteLast(){
    node *temp = last;
    if(head->next == NULL) head = NULL;
    else last->prev->next = NULL;
    last = last->prev;
    return temp;
}

node* del(int key){
    node *curr = head, *prev = NULL;
    if(head == NULL) return NULL;
    while(curr->key != key){
        if(curr->next == NULL) return NULL;
        prev = curr; curr = curr->next;
    }
    if(curr == head) head = head->next;
    else prev->next = curr->next;
    if(curr == last) last = curr->prev;
    else curr->next->prev = curr->prev;
    return curr;
}

bool insertAfter(int key, int newKey, int data){
    node *curr = head;
    if(head == NULL) return false;
    while(curr->key != key){
        if(curr->next == NULL) return false;
        curr = curr->next;
    }
    node *newLink = new node();
    newLink->key = newKey; newLink->data = data;
    if(curr == last){ newLink->next = NULL; last = newLink; }
    else { newLink->next = curr->next; curr->next->prev = newLink; }
    newLink->prev = curr; curr->next = newLink;
    return true;
}

int main(){
    insertFirst(1,10); insertFirst(2,20); insertFirst(3,30);
    insertFirst(4,1); insertFirst(5,40); insertFirst(6,56);
    displayForward(); displayBackward();
    deleteFirst(); displayForward();
    deleteLast(); displayForward();
    insertAfter(4,7,13); displayForward();
    del(4); displayForward();
    return 0;
}

আউটপুট

List (First to Last): [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Last to first): [ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
After deleting first: [ (5,40) (4,1) (3,30) (2,20) (1,10) ]
After deleting last: [ (5,40) (4,1) (3,30) (2,20) ]
Insert after key(4): [ (5,40) (4,1) (7,13) (3,30) (2,20) ]
After delete key(4): [ (5,40) (7,13) (3,30) (2,20) ]