ორმხრივი დაკავშირებული სია ყოველ კვანძს ადის ორი მაჩვენებელი — 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 მაჩვენებელი ცვლის მეხსიერებას ორმხრივი გადაადგილების და მუდმივი დროის წაშლის მოქნილობაზე.