Linked List Variations (প্রকারভেদ)
লিংকড লিস্টের মূলত তিনটি ফ্লেভার/প্রকার রয়েছে, যেগুলোর কার্যকারিতা ও ব্যবহার ভিন্ন।
১. Simple (Singly) Linked List
- নেভিগেশন: কেবল ফরওয়ার্ড (Next পয়েন্টার)।
- নোড স্ট্রাকচার:
{ data, next } - উপযোগিতা: সিম্পল ইমপ্লিমেন্টেশন, কম মেমরি, স্ট্যাক/কিউ বেস।
- সীমাবদ্ধতা: ব্যাকওয়ার্ড ট্রাভার্সাল নেই, টেইল অ্যাক্সেস O(n)۔
২. Doubly Linked List (ডাবলি লিংকড লিস্ট)
- নেভিগেশন: ফরওয়ার্ড (
next) + ব্যাকওয়ার্ড (prev)। - নোড স্ট্রাকচার:
{ data, next, prev } - এক্স্ট্রা: ক্লাসে
tailপয়েন্টার রাখা হয়। - উপযোগিতা: দ্বিমুখী ট্রাভার্সাল, O(1) ডিলিশন (দেওয়া নোড থেকে), ব্রাউজার হিস্টরি (Back/Forward)۔
- ট্রেড-অফ: প্রতি নোডে এক্স্ট্রা পয়েন্টার (মেমরি ওভারহেড)۔
৩. Circular Linked List (সার্কুলার লিংকড লিস্ট)
- চারিত্রিক: শেষ নোডের
nextপ্রথম নোডকে (হেড) পয়েন্ট করে। - প্রকারভেদ:
- Singly Circular: শুধু
nextসার্কুলার। - Doubly Circular:
next(হেডে) +prev(টেইলে) — উভয় দিকেই সার্কুলার।
- Singly Circular: শুধু
- উপযোগিতা: রাউন্ড-রবিন শিডিউলিং, মিউজিক প্লেলিস্ট (লুপ), গেম টার্ন সিস্টেম।
- সতর্কতা: ইনফিনিট লুপ এড়াতে
curr !== headচেক দরকার।
তুলনামূলক সারসংক্ষেপ
| Feature | Singly | Doubly | Circular (Singly) | Circular (Doubly) |
|---|---|---|---|---|
| Forward Traversal | ✅ | ✅ | ✅ (Loop) | ✅ (Loop) |
| Backward Traversal | ❌ | ✅ | ❌ | ✅ (Loop) |
| Tail Access | O(n) | O(1) | O(1) via Head.prev* | O(1) |
| Memory/Node | 2 Fields | 3 Fields | 2 Fields | 3 Fields |
| Delete Known Node | O(n) | O(1) | O(n) | O(1) |
| Complexity | Simple | Medium | Medium | Complex |
কোনটি বেছে নেবেন?
- Singly: স্ট্যাক, কিউ, সিম্পল লিস্ট, মেমরি সেনসিটিভ।
- Doubly: ব্রাউজার হিস্টরি, টেক্সট এডিটর (অনডু/রিডো), ডিক (Deque), LRU Cache।
- Circular: রাউন্ড-রবিন, ক্যারusele, রিয়েল-টাইম বাফার, গেম লুপ।
