একটি দ্বিমুখী সংযুক্ত তালিকা প্রতিটি নোডকে দুটি পয়েন্টার দেয় — next এবং prev — যাতে আপনি উভয় দিকে ট্রাভার্স করতে পারেন এবং O(1)-এ একটি নোড মুছে ফেলতে পারেন যখন আপনার কাছে ইতিমধ্যে এটির একটি রেফারেন্স আছে (হেড থেকে পূর্ববর্তী খুঁজে পেতে হাঁটার প্রয়োজন নেই)।
null <- [10] <-> [20] <-> [30] -> null
prev/next links in BOTH directions
class Node:
def __init__(self, val):
self.val, self.prev, self.next = val, None, None
def remove(node): # O(1) — no traversal needed
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
একটি একক সংযুক্ত তালিকায়, একটি নোড মুছে ফেলা প্রথমে এর পূর্ববর্তী খুঁজে পাওয়ার প্রয়োজন → O(n)।
| দিক | একক | দ্বিমুখী |
|---|---|---|
| প্রতি নোড পয়েন্টার | 1 (next) | 2 (next, prev) |
| পিছনের দিকে ট্রাভার্স | না | হাঁ |
| পরিচিত নোড মুছুন | O(n) | O(1) |
| মেমরি ওভারহেড | কম | বেশি |
পরিচিত নোডের O(1) স্প্লাইস-আউট হল মূল সম্পত্তি যা দ্বিমুখী সংযুক্ত তালিকাগুলিকে একটি LRU ক্যাশ-এ hash ম্যাপের অংশীদার করে তোলে।
অতিরিক্ত prev পয়েন্টার দ্বিমুখী আন্দোলনের নমনীয়তা এবং ধ্রুবক-সময় মুছে ফেলার জন্য মেমরি ব্যবসা করে।