এই আর্টিকেলে আমাদের একটি ডাবলি লিংকড লিস্ট আছে, এবং আমরা C++-এ ডাবলি লিংকড লিস্ট রিভার্স করার বিভিন্ন পদ্ধতি ব্যাখ্যা করব। উদাহরণস্বরূপ −
ইনপুট : {1, 2, 3, 4}
আউটপুট : {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++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (নরমাল এবং অনঅর্থডক্স) শিখেছি যেগুলো দিয়ে আমরা এই সমস্যা সমাধান করেছি। আমরা একই প্রোগ্রাম অন্যান্য ল্যাঙ্গুয়েজে লিখতে পারি যেমন C, Java, Python এবং অন্যান্য ল্যাঙ্গুয়েজ। আশা করি আপনি এই আর্টিকেলটিকে সহায়ক খুঁজে পাবেন।
