Senarai terpaut dua arah memberikan setiap nod dua penunjuk — next dan prev — sehingga anda boleh melintasi dalam kedua-dua arah dan memadam nod dalam O(1) apabila anda sudah memegang rujukan kepadanya (tidak perlu berjalan dari kepala untuk mencari pendahulu).
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
Dalam senarai terpaut satu arah, memadamkan nod memerlukan mencari pendahulunya terlebih dahulu → O(n).
| Aspek | Satu arah | Dua arah |
|---|---|---|
| Penunjuk per nod | 1 (next) | 2 (next, prev) |
| Lintas ke belakang | tidak | ya |
| Padamkan nod yang diketahui | O(n) | O(1) |
| Overhed memori | lebih rendah | lebih tinggi |
Splice-out O(1) bagi nod yang diketahui adalah sifat utama yang menjadikan senarai terpaut dua arah pasangan peta hash dalam cache LRU.
Penunjuk prev tambahan menukar memori untuk fleksibilitas pergerakan dua arah dan pemadaman masa yang tetap.
Pustaka soalan temu duga IT dengan jawapan terperinci — daripada Junior hingga Senior.
Derma