এই সমস্যাতে, আমাদের একটি ডাবলি লিংকড লিস্ট (Doubly Linked List) দেওয়া আছে। আমাদের কাজ হল C++-এ ডাবলি লিংকড লিস্টের আকার (size/length) বের করার প্রোগ্রাম লিখা।
ডাবলি লিংকড লিস্ট হল লিংকড লিস্টের একটি বিশেষ ধরন যেখানে আগে ও পিছে উভয় দিকে নেভিগেশন করা যায়, যা সিঙ্গলি লিংকড লিস্টের তুলনায় সহজ। ডাবলি লিংকড লিস্ট বোঝার জন্য কিছু গুরুত্বপূর্ণ টার্ম:
Link - লিংকড লিস্টের প্রতিটি লিংক একটি ডেটা সংরক্ষণ করতে পারে जिसे element বলা হয়।
Next - প্রতিটি লিংক পরবর্তী লিংকের সাথে সংযুক্ত থাকে जिसे Next বলা হয়।
Prev - প্রতিটি লিংক পূর্ববর্তী লিংকের সাথে সংযুক্ত থাকে जिसे Prev বলা হয়।
LinkedList - একটি লিংকড লিস্টে প্রথম লিংকের সাথে সংযোগ থাকে (First) এবং শেষ লিংকের সাথে সংযোগ থাকে (Last)।
ডাবলি লিংকড লিস্টের প্রতিনিধিত্ব:
সমস্যা বর্ণনা: আমাদের উপরের ধরনের একটি ডাবলি লিংকড লিস্ট দেওয়া থাকবে। আমাদের এর আকার (length) বের করতে হবে।
উদাহরণ:
ইনপুট
উপরোক্ত লিংকড লিস্ট A <-> B <-> C
আউটপুট
3
সমাধানের পদ্ধতি
ডাবলি লিংকড লিস্টের আকার বের করতে, আমাদের লিস্টটি ট্রাভার্স (traverse) করতে হবে এবং একটি লেন্থ ভেরিয়েবল দিয়ে গণনা রাখতে হবে।
অ্যালগরিদম
ইনিশিয়ালাইজ: length = 0, *temp = head
- স্টেপ ১: লিস্ট ট্রাভার্স করুন (temp != NULL পর্যন্ত)।
- স্টেপ ১.১: length++, length বাড়ান
- স্টেপ ১.২: পয়েন্টার আপডেট করুন, temp = temp->next
- স্টেপ ২: length প্রিন্ট করুন।
প্রোগ্রাম
#include <iostream>
using namespace std;
struct doublyLL {
char val;
struct doublyLL *next;
struct doublyLL *prev;
};
void insertNode(struct doublyLL** head_ref, int value) {
struct doublyLL* new_node = new doublyLL;
new_node->val = value;
new_node->next = (*head_ref);
new_node->prev = NULL;
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
int calcDLLSize(struct doublyLL *temp) {
int length = 0;
while (temp != NULL) {
temp = temp->next;
length++;
}
return length;
}
int main() {
struct doublyLL* head = NULL;
insertNode(&head, 'A');
insertNode(&head, 'H');
insertNode(&head, 'E');
insertNode(&head, 'K');
insertNode(&head, 'M');
insertNode(&head, 'S');
cout << "The size of Doubly Linked List is " << calcDLLSize(head);
return 0;
}
আউটপুট
The size of Doubly Linked List is 6
