ডাবলি লিঙ্কড লিস্ট বাস্তবায়নের C++ প্রোগ্রাম

ডাবলি লিঙ্কড লিস্ট একটি ডেটা স্ট্রাকচারের প্রকার যা নোড দ্বারা তৈরি হয় যা সেলফ-রেফারেনশিয়াল স্ট্রাকচার ব্যবহার করে তৈরি করা হয়। এই নোডগুলো তিনটি অংশ ধারণ করে: ডেটা, পরবর্তী লিস্ট নোডের রেফারেন্স এবং পূর্ববর্তী লিস্ট নোডের রেফারেন্স।

প্রথম লিস্ট নোডের রেফারেন্স মাত্রই পুরো লিঙ্কড লিস্ট অ্যাক্সেস করার জন্য পর্যাপ্ত। এটিকে হেড (head) বলা হয়। লিস্টের শেষ নোডটি কাকেই পয়েন্ট করে না তাই সেটি সেই অংশে NULL সংরক্ষণ করে। এছাড়া ডাবলি লিঙ্কড লিস্ট যেন দুই দিকে ট্রভার্স করা যায় কারণ প্রতিটি নোড তার আগের এবং পরের নোডকে পয়েন্ট করে।

ডাবলি লিঙ্কড লিস্ট বাস্তবায়ন করার একটি প্রোগ্রাম নিচে দেওয়া হলো:

উদাহরণ

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};

struct Node* head = NULL;

void insert(int newdata) {
    struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
    newnode->data = newdata;
    newnode->prev = NULL;
    newnode->next = head;
    if (head != NULL)
        head->prev = newnode;
    head = newnode;
}

void display() {
    struct Node* ptr;
    ptr = head;
    while (ptr != NULL) {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
}

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout << "The doubly linked list is: ";
    display();
    return 0;
}

আউটপুট

The doubly linked list is: 9 2 7 1 3

উপরোক্ত প্রোগ্রামে, Node স্ট্রাকচারটি ডাবলি লিঙ্কড লিস্টের নোড গঠন করে। এতে ডেটা এবং পরবর্তী ও পূর্ববর্তী লিঙ্কড লিস্ট নোডের পয়েন্টার থাকে। এটি নিচে দেওয়া হলো:

struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};

insert() ফাংশনটি ডাবলি লিঙ্কড লিস্টের শুরুতে ডেটা ইনসার্ট করে। এটি একটি newnode তৈরি করে এবং নম্বরটি newnode-এর ডেটা ফিল্ডে ইনসার্ট করে। তারপর newnode-এর prev পয়েন্টার NULL-কে পয়েন্ট করে কারণ এটি শুরুতে ইনসার্ট হয়েছে এবং next পয়েন্টার head-কে পয়েন্ট করে। যদি head NULL না হয় তবে head-এর prev পয়েন্টার newnode-কে পয়েন্ট করে। অবশেষে head হয় newnode অর্থাৎ লিঙ্কড লিস্ট সেখান থেকে শুরু হয়। এটি নিচে দেওয়া হলো:

void insert(int newdata) {
    struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
    newnode->data = newdata;
    newnode->prev = NULL;
    newnode->next = head;
    if (head != NULL)
        head->prev = newnode;
    head = newnode;
}

display() ফাংশনটি পুরো ডাবলি লিঙ্কড লিস্ট প্রদর্শন করে। প্রথমে ptr head-কে পয়েন্ট করে। তারপর এটি liên tục পরবর্তী নোডে ফরওয়ার্ড করা হয় যতক্ষণ না নোডগুলোর সমস্ত ডেটা ভ্যালু প্রিন্ট হয়। এটি নিচে দেওয়া হলো:

void display() {
    struct Node* ptr;
    ptr = head;
    while (ptr != NULL) {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
}

main() ফাংশনে, প্রথমে বিভিন্ন মান insert() কল করে ডাবলি লিঙ্কড লিস্টে ইনসার্ট করা হয়। তারপর ডাবলি লিঙ্কড লিস্টটি প্রদর্শন করা হয়। এটি নিচে দেওয়া হলো:

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout << "The doubly linked list is: ";
    display();
    return 0;
}