รายการที่เชื่อมโยงแบบสองทิศทาง ให้แต่ละโหนด สอง ตัวชี้ — 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 เพิ่มเติมจะแลกเปลี่ยนหน่วยความจำเพื่อความยืดหยุ่นของการเคลื่อนที่ในสองทิศทางและการลบในเวลาคงที่