Doubly linked list khác singly linked list như thế nào?

Question

IT Interview Practice · Accepted Answer

**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). ## Cấu trúc ```text null <- [10] <-> [20] <-> [30] -> null liên kết prev/next theo CẢ HAI hướng ``` ## Xóa O(1) một node đã biết ```python 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)**. ## So sánh | 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 | ## Khi nào dùng - **Doubly:** LRU cache, lịch sử trình duyệt, undo/redo, và bất kỳ cấu trúc nào cần xóa O(1) ở giữa. - **Singly:** khi bộ nhớ eo hẹp và bạn chỉ di chuyển về phía trước. ## Tại sao điều này quan trọng 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ố.

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

Cấu trúc

Xóa O(1) một node đã biết

So sánh

Khi nào dùng

Tại sao điều này quan trọng

Câu hỏi liên quan