Sebuah doubly linked list memberikan setiap node dua pointer — next dan prev — sehingga Anda dapat melakukan traversal dalam kedua arah dan menghapus node dalam O(1) ketika Anda sudah memegang referensi ke node tersebut (tidak perlu berjalan dari head untuk mencari 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
Dalam singly linked list, menghapus node memerlukan pencarian predecessor terlebih dahulu → O(n).
| Aspek | Singly | Doubly |
|---|---|---|
| Pointer per node | 1 (next) | 2 (next, prev) |
| Traversal backward | tidak | ya |
| Hapus node yang diketahui | O(n) | O(1) |
| Overhead memori | lebih rendah | lebih tinggi |
Splice-out O(1) dari node yang diketahui adalah sifat kunci yang membuat doubly linked list menjadi mitra hash map dalam LRU cache.
Pointer prev tambahan menukar memori untuk fleksibilitas pergerakan bidirectional dan penghapusan dengan waktu konstan.