एक दोहोरो जोडिएको सूची प्रत्येक नोडलाई दुई सूचक दिन्छ — next र prev — त्यसोभेरे तपाईं दुवै दिशामा यात्रा गर्न सक्नुहुन्छ र जब तपाईंसँग पहिले नै यसको सन्दर्भ छ त्यस नोडलाई O(1) मा मेट गर्न सक्नुहुन्छ (टाउकोबाट पूर्ववर्तीलाई खोज्न जान आवश्यक छैन)।
एक दोहोरो जोडिएको सूची प्रत्येक नोडलाई दुई सूचक दिन्छ — 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)।
| पहलु | एकल | दोहोरो |
|---|---|---|
| प्रति नोड सूचक | १ (next) | २ (next, prev) |
| पछाडि तिरको यात्रा | छैन | हो |
| ज्ञात नोड मेट गर्नु | O(n) | O(1) |
| मेमोरी ओभरहेड | कम | बढी |
ज्ञात नोडको O(1) स्प्लिस-आउट मुख्य गुण हो जसले दोहोरो जोडिएको सूचीहरुलाई LRU क्याश मा hash maps को साथीदार बनाउँछ।
अतिरिक्त prev सूचकले मेमोरीलाई दुविध-दिशा आन्दोलन र स्थिर-समय मेटिङको लचकपनको लागी व्यापार गर्छ।