द्विमार्गीय जोडलेली यादी प्रत्येक नोडला दोन सूचक देते — next आणि prev — जेणेकरून आपण दोन्ही दिशांना जाऊ शकता आणि जर आपल्याकडे त्याचा संदर्भ असेल तर नोड O(1) मध्ये हटवू शकता (मागीळ शोधण्यासाठी डोक्यावरून चालण्याची गरज नाही).
null <- [10] <-> [20] <-> [30] -> null
prev/next links in BOTH directions
सविस्तर उत्तरांसह IT मुलाखत प्रश्नांचे ग्रंथालय — Junior पासून Senior पर्यंत.
देणगी द्या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) splice-out हा मुख्य गुणधर्म आहे जो द्विमार्गीय जोडलेल्या यादीला LRU कॅश चे hash map सहकारी बनवते.
अतिरिक्त prev सूचक मेमोरीचा व्यापार द्विदिशात्मक हालचालीचे लवचिकता आणि स्थिर-काल हटवणे साठी करते.