দ্বিগুণ লিঙ্কযুক্ত তালিকা বাস্তবায়নের জন্য সি++ প্রোগ্রাম

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

সম্পূর্ণ লিঙ্ক করা তালিকা অ্যাক্সেস করার জন্য শুধুমাত্র প্রথম তালিকা নোডের রেফারেন্স প্রয়োজন। এটি মাথা হিসাবে পরিচিত। তালিকার শেষ নোডটি কিছুই নির্দেশ করে না তাই এটি সেই অংশে 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

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

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

ফাংশন insert() ডাটা ঢোকানো হয় দ্বিগুণ লিঙ্ক করা তালিকার শুরুতে। এটি একটি নিউনোড তৈরি করে এবং নিউনোডের ডেটা ক্ষেত্রে নম্বর সন্নিবেশ করায়। তারপর নিউনোডের পূর্ববর্তী পয়েন্টারটি NULL এর দিকে নির্দেশ করে যেভাবে এটি শুরুতে প্রবেশ করা হয়েছে এবং পরবর্তী পয়েন্টারটি মাথার দিকে নির্দেশ করে। হেড 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;
}

ফাংশন প্রদর্শন() পুরো দ্বিগুণ লিঙ্কযুক্ত তালিকা প্রদর্শন করে। প্রথম ptr পয়েন্ট হেড. তারপর নোডের সমস্ত ডেটা মান প্রিন্ট না হওয়া পর্যন্ত এটি ক্রমাগত পরবর্তী নোডে ফরোয়ার্ড করা হয়। এটি নীচে দেওয়া হল৷

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;
}