Doubly Linked List: ধারণা ও কাঠামো
Doubly Linked List (ডাবলি লিংকড লিস্ট) সিংলি লিংকড লিস্টের মতোই কিন্তু প্রতিটি নোডে দুইটি লিংক থাকে: next (পরবর্তী) এবং prev (পূর্ববর্তী)। এটি দ্বিমুখী ট্রাভার্সাল সক্ষম করে।
নোড স্ট্রাকচার
┌─────────────────────────────────────┐ │ NODE │ ├──────────┬──────────┬──────────────┤ │ prev │ data │ next │ │ (ref) │ (value) │ (ref) │ └──────────┴──────────┴──────────────┘
লিস্ট রিপ্রেজেন্টেশন
HEAD TAIL
↓ ↓
null ← [Node 1] ⇄ [Node 2] ⇄ [Node 3] ⇄ ... ⇄ [Node N] → null
↑ ↑ ↑ ↑
prev prev prev prev
(null) (Node 1) (Node 2) (Node N-1)
- Head: প্রথম নোড, এর
prev = null। - Tail: শেষ নোড, এর
next = null। - Internal Nodes:
prevএবংnextউভয়েই ভ্যালিড রেফারেন্স।
সিংলি লিংকড লিস্ট থেকে পার্থক্য
| অপারেশন | Singly Linked List | Doubly Linked List |
|---|---|---|
| Forward Traversal | O(n) | O(n) |
| Backward Traversal | অসম্ভব (বिना এক্স্ট্রা স্ট্রাকচার) | O(n) — tail থেকে prev ফলো করে |
| Delete Known Node | O(n) — Prev খুঁজতে হেড থেকে ট্রাভার্স | O(1) — node.prev.next = node.next |
| Insert Before Known Node | O(n) | O(1) |
| Memory per Node | Data + 1 Ref | Data + 2 Refs |
ক্লাসে Tail ট্র্যাক করার কারণ
append()/insertAtEnd()O(1)-এ করা যায় (ট্রাভার্সাল লাগে না)।- Backward Traversal শুরু করার জন্য
tailদরকার। removeLast()O(1)-এ সম্ভব।
JavaScript Implementation Skeleton
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
DoublyLinkedList.prototype.Node = class {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
};
এই বেস স্ট্রাকচার এর ওপর insert, remove, find, reverse ইত্যাদি বিল্ড করা হয়।
