গত পর্বের Circular Singly Linked List এর মতই এই পর্বের Circular Doubly Linked List. তুমি যদি লিংকড লিস্টের আগের পর্বগুলো বুঝে থাকো তাহলে এই পর্বটা বুঝতে খুব একটা কষ্ট হবে না। এই পর্বটি বুঝার জন্য তোমার singly linked list, doubly linked list ও circular singly linked list বুঝতে হবে। এই তিনটির সমন্বয়েই বলতে পারো এই ডেটা স্ট্রাকচারটি গঠিত। তাই ধরেই নিচ্ছি তুমি আগের টপিকগুলো আমার পূর্বের পোস্টগুলো থেকে বা অন্য কোনো রিসোর্স থেকে শিখে নিয়েছ। সে জন্য অনেক ব্যাখ্যাই খুব বেশি ডিটেইলসে দিব না।

Circular Doubly Linked List এমন একটা লিংকড লিস্ট যাতে দুটি বৈশিষ্ট্য আছে। প্রথমত এটা একটা circular (singly) linked list এবং দ্বিতীয়ত এটা একটা doubly linked list. এই circular আর doubly দুইটা লিস্টের বৈশিষ্ট্যকে এক সাথে করে বানানো হয়েছে circular doubly linked list.
Circular Linked List এর বৈশিষ্ট্য হচ্ছে এটা সার্কুলার। অর্থাৎ এর শেষ প্রান্ত বলে কিছু নাই। শেষ প্রান্তে গিয়ে পরের নোডে যেতে চাইলে সে তোমাকে head node এর কাছে পাঠিয়ে দিবে। তুমি চাইলে চড়কির মত এই লিস্টের মধ্যে ভনভন করে ঘুরতে পারো (multiplayer লুডু খেলার মত। চারজনই একের পর এক ছক্কা দিয়ে চালতে থাকে)। আর doubly linked list হচ্ছে এমন একটা লিস্ট যার একটা শুরু ও শেষ আছে (সার্কুলার নয়। শেষ নোডটি next pointer হিসাবে NULL-কে পয়েন্ট করে থাকে)। এর বিশেষ বৈশিষ্ট্য হচ্ছে এর head থেকে tail এর দিকে যেমন traverse করা যায়, একই ভাবে tail থেকে head এর দিকেও traverse করা যায়। অর্থাৎ ছোট বেলার ‘উভমুখী বিক্রিয়া’র মত একটা বিষয়।
Applications of Circular Doubly Linked List
- Repeated task নিয়ে কাজ করার ক্ষেত্রে যদি forward-backward দুই দিকেই traverse করার দরকার হয় একই সাথে যদি লিস্টটাকে সার্কুলারও করতে হয় সেক্ষেত্রে এই ডেটা স্ট্রাকচারটা দরকার হয়। যেমনঃ মিডিয়া প্লেয়ার অ্যাপ্লিকেশনে অডিও বা ভিডিওগুলো সামনে-পিছনে ইচ্ছা মত প্লে করা যায়। পুরো লিস্ট প্লে হলে আবার শুরু থেকে প্লে হয়। তার মানে আমরা যদি ডেস্কটপ, মোবাইল বা ওয়েবে যদি media player App বানাতে চাই তাহলে সেখানে circular doubly linked list ডেটা স্ট্রাকচার নিয়ে কাজ করতে হবে।
- অনলাইন শপিংয়ের ক্ষেত্রে shopping cart ম্যানেজ করার জন্য এই ডেটা স্ট্রাকচার ব্যবহৃত হয়।
Advantages of Circular Doubly Linked List
- লিস্টের যে কোনো নোডকে শুরুর নোড ধরে পুরো লিস্টে traverse করা যায়। শুধু খেয়াল রাখতে হবে যেই নোড থেকে শুরু করা হয়েছিল সেটায় দ্বিতীয় বার ভিজিট করলে যেন traverse operation terminated হয়।
- লিস্টের শুরু থেকে শেষের দিকে ও শেষ থেকে শুরুর দিকে traverse করা যায়।
- Constant time এ [ O(1) ] head থেকে tail এবং tail থেকে head এর মধ্যে সুইচ করা যায়।
- Advanced কিছু Data Structures এর মাধ্যমে implement করা যায়। যেমনঃ Fibonacci Heap.
Disadvantages of Circular Doubly Linked List
- প্রতিটা নোডের previous pointer স্টোর করার জন্য একটু বেশি খরচ হয়।
- বেশ কিছু পয়েন্টার হ্যান্ডেল করতে হয় যে কোনো অপারেশনেই। লিস্টে একটা নোড ঢুকলে বা ডিলেট হলে তার আগের ও পরের উভয় নোডের সাথেই পয়েন্টার কেন্দ্রীক কাজ করতে হয়। তাই খুব সাবধানতা অবলম্বন করতে হয়। নইলে লিস্টের ভিতরের জিনিসপত্রে ভজঘট লেগে যেতে পারে।
Operations of Circular Doubly Linked List
অন্যান্য ডেটা স্ট্রাকচারের মতই সার্কুলার ডাবলি লিংকড লিস্টের কমন কিছু অপারেশন রয়েছে। এই লেখায় নিচের অপারেশনগুলো নিয়ে আলোচনা করা হবে।
- Insert node at list (Position: head, tail and middle)
- Delete node from list (Position: head, tail and middle)
- Traverse the list in Forward order (Print the full list)
- Traverse the list in Backward/Reverse order (Print the full list)
Insert node at Circular Doubly Linked List
Insert node at head: নতুন একটা নোড লিস্টের front এ add করতে চাইলে নিচের কাজগুলো করতে হবেঃ
- নতুন একটা নোড বানিয়ে (newNode) এর next ও previous pointer এ তার নিজের মেমরি অ্যাড্রেসই অ্যাসাইন করে দেয়া
- newNode এর next pointer-টি পয়েন্ট করবে head-কে।
- newNode এর previous pointer-টি পয়েন্ট করবে tail-কে।
- head এর previous pointer এখন পর্যন্ত tail-কে পয়েন্ট করে আছে। কিন্তু head এর আগে এখন newNode বসেছে। তাই head এর previous pointer পয়েন্ট করবে newNode-কে।
- tail এর next pointer এখন পর্যন্ত head কে পয়েন্ট করে আছে। কিন্তু নতুন head হতে যাচ্ছে newNode. তাই tail এর next pointer পয়েন্ট করবে newNode-কে
- লিস্টের নতুন head এখন newNode. তাই head-কে আপডেট করতে হবে newNode দিয়ে।
void insert_at_head(int number){
node *newNode = (node *) malloc(sizeof(node));
newNode->number = number;
newNode->next = newNode;
newNode->previous = newNode;
if(head==NULL){
head = newNode;
tail = newNode;
} else{
newNode->next = head;
newNode->previous = tail;
head->previous = newNode;
tail->next = newNode;
head = newNode;
}
}
Insert node at tail: নতুন একটা নোড লিস্টের end এ add করতে চাইলে নিচের কাজগুলো করতে হবেঃ
- নতুন একটা নোড বানিয়ে (newNode) এর next ও previous pointer এ তার নিজের মেমরি অ্যাড্রেসই অ্যাসাইন করে দেয়া
- এখন tail->next পয়েন্ট করে আছে head কে। যেহেতু tail এ নতুন একটা নোড newNode যোগ হবে তাই এটিই হবে নতুন tail. তাই বর্তমান tail এর next pointer পয়েন্ট করবে newNode কে।
- newNode যেহেতু হতে যাচ্ছে নতুন tail, তাই এর next pointer পয়েন্ট করবে head কে।
- newNode এর previous pointer পয়েন্ট করবে বর্তমান tail কে।
- উপরের চারটি ধাপ অতিক্রম করলে newNode লিস্টের শেষে বসে যাবে। এখন এটা যেহেতু নতুন tail, তাই tail node কে আপডেট করে দিতে হবে newNode দিয়ে।
- এখন পর্যন্ত head এর previous pointer পয়েন্ট করে আছে পুরাতন tail-কে। যেহেতু tail আপডেট হয়েছে সেহেতু head এর previous pointer-ও আপডেট করতে হবে updated tail দিয়ে। তুমি চাইলে head->previous = newNode; এভাবেও লিখতে পার।
void insert_at_tail(int number){
node *newNode = (node *) malloc(sizeof(node));
newNode->number = number;
newNode->next = newNode;
newNode->previous = newNode;
if(head==NULL){
head = newNode;
tail = newNode;
} else{
tail->next = newNode;
newNode->next = head;
newNode->previous = tail;
tail = newNode;
head->previous = tail; //can also write `head->previous = newNode`
}
}
Insert node at middle: নতুন একটা নোড লিস্টের মাঝের যে কোনো পজিশনে add করতে চাইলে নিচের কাজগুলো করতে হবেঃ


Would anyone please send this data structure?cause i have no fb account.
[email protected]
You don’t need to use Facebook account to read this blog post. Can you explain a bit more about your requirement?
Thank you a lot for awesome writing.