ایک دوگنا منسلک فہرست ہر نوڈ کو دو pointers دیتی ہے — next اور prev — تاکہ آپ دونوں سمتوں میں traversal کر سکیں اور جب آپ کے پاس اس کا reference ہو تو ایک نوڈ کو O(1) میں حذف کر سکیں (head سے predecessor تک جانے کی ضرورت نہیں)۔
ایک دوگنا منسلک فہرست ہر نوڈ کو دو pointers دیتی ہے — next اور prev — تاکہ آپ دونوں سمتوں میں traversal کر سکیں اور جب آپ کے پاس اس کا reference ہو تو ایک نوڈ کو O(1) میں حذف کر سکیں (head سے predecessor تک جانے کی ضرورت نہیں)۔
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
ایک سادہ منسلک فہرست میں، کسی نوڈ کو حذف کرنے کے لیے پہلے اس کا predecessor تلاش کرنا پڑتا ہے → O(n)۔
| پہلو | سادہ | دوگنا |
|---|---|---|
| ہر نوڈ میں pointers | 1 (next) | 2 (next, prev) |
| پیچھے کی طرف traversal | نہیں | ہاں |
| معلوم نوڈ حذف کریں | O(n) | O(1) |
| میموری overhead | کم | زیادہ |
معلوم نوڈ کا O(1) splice-out یہ اہم خصوصیت ہے جو دوگنا منسلک فہرستوں کو LRU cache میں hash maps کا ساتھی بناتی ہے۔
اضافی prev pointer میموری کے بدلے bidirectional movement اور constant-time deletion کی لچک فراہم کرتا ہے۔
تفصیلی جوابات کے ساتھ IT انٹرویو سوالات کی ایک لائبریری — جونیئر سے سینئر تک۔
عطیہ دیں