C++ ব্যবহার করে একটি দ্বিগুণ লিঙ্কযুক্ত তালিকা বিপরীত করুন

এই নিবন্ধে আমাদের একটি দ্বিগুণ লিঙ্কযুক্ত তালিকা রয়েছে এবং আমরা C++ এ দ্বিগুণ লিঙ্কযুক্ত তালিকাকে বিপরীত করার জন্য বিভিন্ন পদ্ধতির ব্যাখ্যা করব। যেমন −

Input : {1, 2, 3, 4}
Output : {4, 3, 2, 1}

সাধারণত একটি পদ্ধতির কথা মাথায় আসে, তবে আমরা দুটি পন্থা ব্যবহার করব - স্বাভাবিক এবং অপ্রচলিত পদ্ধতি৷

সাধারণ পদ্ধতি

এই পদ্ধতিতে, আমরা তালিকার মধ্য দিয়ে যাব, এবং আমরা এটির মধ্য দিয়ে যাব, আমরা এটিকে বিপরীত করব।

উদাহরণ

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
   int data;
   Node *next;
   Node *prev;
};

void reverse(Node **head_ref) {
   auto temp = (*head_ref) -> next;
   (*head_ref) -> next = (*head_ref) -> prev;
   (*head_ref) -> prev = temp;
   if(temp != NULL) {
      (*head_ref) = (*head_ref) -> prev;
      reverse(head_ref);
   }
   else
      return;
}
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;

   new_node->prev = NULL;

   new_node->next = (*head_ref);
   if((*head_ref) != NULL)
      (*head_ref) -> prev = new_node ;

   (*head_ref) = new_node;
}
int main() {
   Node* head = NULL;
   push(&head, 6);
   push(&head, 4);
   push(&head, 8);
   push(&head, 9);
   auto node = head;
   cout << "Before\n" ;
   while(node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n";
   reverse(&head);
   node = head;
   cout << "After\n";
   while(node != NULL) {
      cout << node->data << " ";
   node = node->next;
   }
   return 0;
}

আউটপুট

Before
9 8 4 6
After
6 4 8 9

এই পদ্ধতিটি O(N) নেয় সময় জটিলতা যা খুবই ভালো কারণ এই জটিলতা উচ্চ সীমাবদ্ধতায় পারফর্ম করতে পারে।

অনর্থডক্স পদ্ধতি

নামটি থেকে বোঝা যায়, এটি ব্যবহারকারীর মনে আসা খুব সাধারণ পদ্ধতি নয়, তবে আমরা এই পদ্ধতিটিও অন্বেষণ করব৷ এই পদ্ধতিতে, আমরা একটি স্ট্যাক তৈরি করব এবং এতে ডেটা পুশ করতে থাকব, এবং পপ করার সময় আমরা যাচ্ছি৷ এর মান পরিবর্তন করতে।

উদাহরণ

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
   int data;
   Node *next;
   Node *prev;
};
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;

   new_node->prev = NULL;

   new_node->next = (*head_ref);
   if((*head_ref) != NULL)
      (*head_ref) -> prev = new_node ;

   (*head_ref) = new_node;
}
int main() {
   Node* head = NULL;
   push(&head, 6);
   push(&head, 4);
   push(&head, 8);
   push(&head, 9);
   auto node = head;
   cout >> "Before\n" ;
   while(node != NULL) {
      cout >> node->data >> " ";
      node = node->next;
   }
   cout >> "\n";
   stack<Node*> s;
   node = head;
   while(node) {
      head = node;
      s.push(node);
      node = node -> next;
   }
   while(!s.empty()) {
      auto x = s.top();
      auto temp = x -> prev;
      x -> prev = x -> next;
      x -> next = temp;
      s.pop();
   }
   node = head;
   cout << "After\n";
   while(node != NULL) {
      cout << node->data << " ";
   node = node->next;
   }
   return 0;
}

আউটপুট

Before
9 8 4 6
After
6 4 8 9

উপরের কোডের ব্যাখ্যা

এই পদ্ধতিতে আমরা একটি স্ট্যাক ব্যবহার করছি যা আমরা তালিকার মধ্য দিয়ে যাওয়ার সময় পূরণ করছি এবং তারপরে আমরা স্ট্যাকের থেকে আইটেমগুলিকে পপ করছি এবং তাদের মান পরিবর্তন করছি যাতে তালিকাটি বিপরীত হয়। O(N) হল এই প্রোগ্রামের সময় জটিলতা এবং এটি উচ্চতর সীমাবদ্ধতার জন্যও উপযুক্ত।

উপসংহার

এই নিবন্ধে আমরা স্ট্যাক সহ বা ছাড়াই দ্বিগুণ লিঙ্কযুক্ত তালিকাকে বিপরীত করার জন্য একটি সমস্যার সমাধান করি। O(N) সময়ের জটিলতায় যেখানে N হল আমাদের তালিকার আকার। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ এবং অপ্রচলিত) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷