ডাবলি লিংকড লিস্ট (Doubly Linked List)

সিঙ্গলি লিংকড লিস্ট হলো এমন একটা গুপ্তধন খোঁজার খেলার মতো, যেখানে প্রতিটা চিরকুট আপনাকে শুধু বলে দেয় সামনে কোথায় যেতে হবে। কিন্তু একটা ডাবলি লিংকড লিস্ট (Doubly Linked List) হলো এমন একটা খেলা, যেখানে চিঠিতে এটাও লেখা থাকে যে আপনি পেছনে বা আগের জায়গায় কীভাবে ফিরে যাবেন!

এখানে প্রতিটা নোড তিনটা জিনিস বহন করে: একটা ভ্যালু বা ডেটা, সামনের নোডকে চেনার জন্য একটা next পয়েন্টার, এবং পেছনের নোডকে চেনার জন্য একটা prev (previous) পয়েন্টার। এই লিস্টে একটা হেড (Head) বা মাথা যেমন থাকে, তেমনি একটা টেইল (Tail) বা লেজও থাকে। যার কারণে আপনি শেকল ধরে সামনে থেকে পেছনে বা পেছন থেকে সামনে—দুই দিকেই যাতায়াত করতে পারবেন।

সিঙ্গলি লিংকড লিস্টের চেয়ে এখানে কী সুবিধা?

এই এক্সট্রা prev পয়েন্টারটা দুটো বিরাট সুবিধা এনে দেয়:

• টেইল বা একদম শেষে নতুন কিছু যোগ করা O(1) — যেহেতু আপনি সবসময় জানেন টেইলটা কোথায়, তাই একদম শেষে কিছু যোগ করতে শুধু পয়েন্টারগুলো একটু ঘুরালেই হয়, নতুন করে হেড থেকে হেঁটে হেঁটে আসতে হয় না।
• নোড চেনা থাকলে ডিলিট করা O(1) — ধরুন আপনার কাছে একটা নির্দিষ্ট নোডের ঠিকানা সরাসরি আছে। আপনি চোখের পলকে সেটা ডিলিট করে দিতে পারবেন। সিঙ্গলি লিংকড লিস্টে হলে আপনাকে হেড থেকে খুঁজে দেখতে হতো ওই নোডের আগের নোডটা কোনটা (যার জন্য O(n) সময় লাগতো), কারণ সেখানে পেছনে যানয়ার কোনো রাস্তা ছিল না।

এই দুই জাদুকরী সুবিধার মূলে একটাই কারণ: আপনি এখন শেকল ধরে উল্টো দিকেও হাঁটতে পারেন। তাই কোনো নোডের আগের নোড কে, তা জানার জন্য আপনাকে আর কষ্ট করে হেড থেকে যাত্রা শুরু করতে হয় না।

হেডে কিছু যোগ করা (O(1))

একদম সামনে নতুন কোনো নোড বসাতে চাইলে আপনার কাজ হলো:

1. নতুন নোডের next পয়েন্টারকে বর্তমান হেডের দিকে ঘুরিয়ে দিন।
2. বর্তমান হেডের prev পয়েন্টারকে নতুন নোডের দিকে ঘুরিয়ে দিন।
3. সবশেষে head ট্যাগটাকে নতুন নোডের গায়ে লাগিয়ে দিন।

ব্যস! মাত্র তিনটে পয়েন্টার বদল। কাজ শেষ।

টেইলে বা একদম পেছনে কিছু যোগ করা (O(1))

যেহেতু আমরা টেইল বা লেজকেও আলাদা করে চিনি, তাই পেছনে কিছু যোগ করাটাও একদম মামুলি কাজ:

1. বর্তমান টেইলের next পয়েন্টারকে নতুন নোডের দিকে ঘুরিয়ে দিন।
2. নতুন নোডের prev পয়েন্টারকে বর্তমান টেইলের দিকে ঘুরিয়ে দিন।
3. সবশেষে tail ট্যাগটাকে নতুন নোডের গায়ে লাগিয়ে দিন।

একটা সিঙ্গলি লিংকড লিস্ট টেইল পয়েন্টার ছাড়া এটা কখনোই O(1) সময়ে করতে পারবে না। আর টেইল পয়েন্টার থাকলেও, পেছনের নোড মুছে ফেলতে গেলে তার O(n) সময় লাগবে (কারণ আগের নোড খোঁজার উপায় নেই)। ডাবলি লিংকড লিস্টের ক্ষেত্রে নতুন টেইল পাওয়া যায় জাস্ট old_tail.prev দিয়ে!

রেফারেন্স জানা থাকলে ডিলিট করা (O(1))

যদি আপনার কাছে এমন একটা পয়েন্টার থাকে যেটা সরাসরি ডিলিট করার নোডটাকে চেনে:

1. আগের নোডের সাথে পরের নোড জুড়ে দিন: node.prev.next = node.next
2. পরের নোডের সাথে আগের নোড জুড়ে দিন: node.next.prev = node.prev

নোডটা এখন দুই দিক থেকেই শেকল-ছাড়া হয়ে গেলো। কোনো খোঁজাখুঁজির প্যারা ছাড়াই!

বাস্তব দুনিয়ায় এর ব্যবহার

ডাবলি লিংকড লিস্ট হলো প্রোগ্রামিং জগতের অনেক গুরুত্বপূর্ণ জিনিসের পেছনের কারিগর:

• LRU Cache — যে জিনিসগুলো বেশি ব্যবহার হচ্ছে সেগুলোকে চোখের পলকে বা O(1) সময়ে সামনে নিয়ে আসা।
• Deque (ডাবল-এন্ডেড কিউ) — লাইনের একদম সামনে এবং পেছনে, দুই জায়গা থেকেই পুশ বা পপ করা।
• ব্রাউজার হিস্ট্রি — ইন্টারনেটে সামনে (Forward) এবং পেছনে (Back) যানয়া।
• Undo/Redo — আমরা যখন কোনো কাজে ভুল করে আনডু বা রিডু করি, তখন এই কাজের হিস্ট্রি দুই দিকে যাতায়াতের জন্য ডাবলি লিংকড লিস্ট ব্যবহার করে।