تعطي القائمة المرتبطة الثنائية كل عقدة مؤشرين — 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) من قائمة انتظار عقدة معروفة هي الخاصية الرئيسية التي تجعل القوائم المرتبطة الثنائية شريكة خرائط Hash في ذاكرة تخزين مؤقت LRU.
المؤشر الإضافي prev يتاجر بالذاكرة مقابل مرونة الحركة ثنائية الاتجاه وحذف ثابت الوقت.