ద్విముఖ సంధానిత జాబితా ప్రతి నోడ్కు రెండు పాయింటర్లను ఇస్తుంది — 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 కేష్ లో హ్యాష్ మ్యాప్ల భాగస్వామిగా చేసే ముఖ్య సంపత్తి.
కూడిన prev పాయింటర్ ద్విముఖ చలనం మరియు స్థిర-సమయ తొలగింపు యొక్క నమ్యతకు జ్ఞాపకశక్తిని కారణం చేస్తుంది.