Doubly linked list (danh sách liên kết đôi) cho mỗi node hai pointer — next và prev — nên bạn có thể duyệt theo cả hai hướng và xóa một node trong O(1) khi bạn đã giữ tham chiếu tới nó (không cần đi từ head để tìm phần tử liền trước).
null <- [10] <-> [20] <-> [30] -> null
liên kết prev/next theo CẢ HAI hướng
class Node:
def __init__(self, val):
self.val, self.prev, self.next = val, None, None
def remove(node): # O(1) — không cần duyệt
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
Trong một singly linked list, xóa một node đòi hỏi tìm phần tử liền trước của nó trước → O(n).
| Khía cạnh | Singly | Doubly |
|---|---|---|
| Pointer mỗi node | 1 (next) | 2 (next, prev) |
| Duyệt ngược | không | có |
| Xóa node đã biết | O(n) | O(1) |
| Chi phí bộ nhớ | thấp hơn | cao hơn |
Việc nối-bỏ (splice-out) O(1) một node đã biết là thuộc tính then chốt khiến doubly linked list trở thành đối tác của hash map trong một LRU cache.
Pointer prev thêm vào đánh đổi bộ nhớ để lấy sự linh hoạt của di chuyển hai chiều và xóa trong thời gian hằng số.