द्विमार्गीय जोडलेली यादी प्रत्येक नोडला दोन सूचक देते — 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).
| पैलू | एकमार्गीय | द्विमार्गीय |
|---|---|---|
| प्रति नोड सूचक | 1 (next) | 2 (next, prev) |
| मागे जाणा | नाही | होय |
| ज्ञात नोड हटवा | O(n) | O(1) |
| मेमोरी ओव्हरहेड | कमी | जास्त |
ज्ञात नोडचा O(1) splice-out हा मुख्य गुणधर्म आहे जो द्विमार्गीय जोडलेल्या यादीला LRU कॅश चे hash map सहकारी बनवते.
अतिरिक्त prev सूचक मेमोरीचा व्यापार द्विदिशात्मक हालचालीचे लवचिकता आणि स्थिर-काल हटवणे साठी करते.
सविस्तर उत्तरांसह IT मुलाखत प्रश्नांचे ग्रंथालय — Junior पासून Senior पर्यंत.
देणगी द्या