Danh sách liên kết đôi
Cập nhật lần cuối
Danh sách liên kết đôi (doubly linked list) là danh sách liên kết trong đó mỗi nút giữ hai con trỏ: next (trỏ đến nút phía sau) và prev (trỏ đến nút phía trước). Liên kết ngược bổ sung này cho phép bạn duyệt theo cả hai chiều và xóa một nút trong O(1) khi đã có tham chiếu đến nó, vì bạn đến thẳng được nút liền trước thay vì phải đi từ đầu danh sách. Nhấn Phát ở trên để xem các nút được nối và nối lại theo cả hai chiều.
Cái giá là thêm một con trỏ cho mỗi nút và nhiều việc cập nhật hơn: mỗi lần chèn và xóa đều phải cập nhật cả next lẫn prev ở các nút lân cận. Đây là cấu trúc đứng sau nhiều deque và LRU cache, nơi việc gỡ bỏ nhanh ở cả hai đầu là quan trọng.
Độ phức tạp thời gian
| Thao tác | Độ phức tạp | Ghi chú |
|---|---|---|
| Chèn vào đầu/cuối | O(1) | Khi có con trỏ head và tail |
| Xóa một nút đã biết | O(1) | Đến thẳng prev, không cần duyệt |
| Tìm kiếm | O(n) | Vẫn là duyệt tuần tự |
| Truy cập theo chỉ số | O(n) | Không có truy cập ngẫu nhiên |
Danh sách liên kết đơn và đôi
| Khía cạnh | Liên kết đơn | Liên kết đôi |
|---|---|---|
| Số con trỏ mỗi nút | 1 (next) | 2 (next + prev) |
| Duyệt ngược | Không | Có |
| Xóa một nút đã biết | O(n) (tìm prev) | O(1) |
| Bộ nhớ phụ | Thấp hơn | Cao hơn |
Ví dụ minh họa
Tạo [10, 20, 30] bằng cách thêm vào cuối, rồi xóa nút 20:
| Bước | Cấu trúc | Thao tác |
|---|---|---|
| Bắt đầu | null | Danh sách rỗng: head và tail đều là null |
| Thêm 10 | 10 | Nút đầu tiên; head và tail đều trỏ đến nó, prev = next = null |
| Thêm 20 | 10 <-> 20 | Đặt 10.next = 20 và 20.prev = 10; tail = 20 |
| Thêm 30 | 10 <-> 20 <-> 30 | Đặt 20.next = 30 và 30.prev = 20; tail = 30 |
| Xóa 20 | 10 <-> 30 | Dùng 20.prev và 20.next: đặt 10.next = 30 và 30.prev = 10 trong O(1) |
Khi nào nên dùng danh sách liên kết đôi
| Nên dùng khi | Tránh dùng khi |
|---|---|
| Bạn cần duyệt hoặc ghép nối theo cả hai chiều | Bạn chỉ luôn đi về phía trước: danh sách liên kết đơn nhẹ hơn |
Bạn xóa các nút bất kỳ mà bạn đã có tham chiếu (O(1)) | Bạn chủ yếu truy cập theo vị trí: hãy dùng mảng để truy cập O(1) |
| Bạn cài đặt deque, LRU cache hoặc lịch sử hoàn tác trên màn hình | Bộ nhớ eo hẹp: con trỏ prev bổ sung làm chi phí liên kết tăng gấp đôi |
| Việc chèn và gỡ bỏ diễn ra thường xuyên ở cả hai đầu | Dữ liệu nhỏ và hiếm khi thay đổi: sao chép mảng rẻ hơn |
Code Doubly Linked List
Một cách cài đặt Doubly Linked List gọn gàng, chạy được ngay bằng Python, JavaScript, Java, C++, C. Chọn một ngôn ngữ, sao chép code hoặc mở sẵn trong Coddy Playground.
Code Doubly Linked List bằng Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.prev = None5 self.next = None6
7
8class DoublyLinkedList:9 def __init__(self):10 self.head = None11 self.tail = None12
13 def append(self, value):14 node = Node(value)15 if self.tail is None:16 self.head = self.tail = node17 return18 # Wire both directions: old tail <-> new node19 node.prev = self.tail20 self.tail.next = node21 self.tail = node22
23 def prepend(self, value):24 node = Node(value)25 if self.head is None:26 self.head = self.tail = node27 return28 node.next = self.head29 self.head.prev = node30 self.head = node31
32 def forward(self):33 values, current = [], self.head34 while current:35 values.append(current.value)36 current = current.next37 return values38
39 def backward(self):40 values, current = [], self.tail41 while current:42 values.append(current.value)43 current = current.prev44 return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49 lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())Code Doubly Linked List bằng JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.prev = null;5 this.next = null;6 }7}8
9class DoublyLinkedList {10 constructor() {11 this.head = null;12 this.tail = null;13 }14
15 // Tail pointer makes append O(1)16 append(value) {17 const node = new Node(value);18 if (!this.tail) {19 this.head = node;20 this.tail = node;21 return;22 }23 node.prev = this.tail;24 this.tail.next = node;25 this.tail = node;26 }27
28 forward() {29 const out = [];30 for (let n = this.head; n; n = n.next) out.push(n.value);31 return out;32 }33
34 backward() {35 const out = [];36 for (let n = this.tail; n; n = n.prev) out.push(n.value);37 return out;38 }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));Code Doubly Linked List bằng Java
Java
1public class Main {2 static class Node {3 int value;4 Node prev, next;5 Node(int value) { this.value = value; }6 }7
8 static Node head, tail;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = tail = node; return; }13 node.prev = tail;14 tail.next = node;15 tail = node;16 }17
18 // Unlink in O(1) once found: fix both neighbor pointers19 static void delete(int value) {20 for (Node cur = head; cur != null; cur = cur.next) {21 if (cur.value != value) continue;22 if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23 if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24 return;25 }26 }27
28 public static void main(String[] args) {29 append(1);30 append(2);31 append(3);32 append(4);33
34 StringBuilder forward = new StringBuilder("Forward:");35 for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36 System.out.println(forward);37
38 StringBuilder backward = new StringBuilder("Backward:");39 for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40 System.out.println(backward);41
42 delete(3);43 StringBuilder after = new StringBuilder("After delete 3:");44 for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45 System.out.println(after);46 }47}Code Doubly Linked List bằng C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* prev = nullptr;6 Node* next = nullptr;7 explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11 Node* head = nullptr;12 Node* tail = nullptr;13
14 void append(int value) {15 Node* node = new Node(value);16 if (tail == nullptr) {17 head = tail = node;18 return;19 }20 node->prev = tail; // link both directions21 tail->next = node;22 tail = node;23 }24
25 void prepend(int value) {26 Node* node = new Node(value);27 if (head == nullptr) {28 head = tail = node;29 return;30 }31 node->next = head;32 head->prev = node;33 head = node;34 }35
36 void printForward() const {37 for (Node* cur = head; cur != nullptr; cur = cur->next) {38 std::cout << cur->value << " <-> ";39 }40 std::cout << "null\n";41 }42
43 void printBackward() const {44 for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45 std::cout << cur->value << " <-> ";46 }47 std::cout << "null\n";48 }49};50
51int main() {52 DoublyLinkedList list;53 for (int value : {10, 20, 30}) list.append(value);54 list.prepend(5);55 std::cout << "Forward: ";56 list.printForward();57 std::cout << "Backward: ";58 list.printBackward();59 return 0;60}Code Doubly Linked List bằng C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* prev;7 struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14 Node* n = calloc(1, sizeof(Node));15 n->value = value;16 return n;17}18
19void append(int value) {20 Node* node = newNode(value);21 if (tail == NULL) {22 head = tail = node;23 return;24 }25 node->prev = tail; // link both directions26 tail->next = node;27 tail = node;28}29
30void prepend(int value) {31 Node* node = newNode(value);32 if (head == NULL) {33 head = tail = node;34 return;35 }36 node->next = head;37 head->prev = node;38 head = node;39}40
41void printForward(void) {42 for (Node* cur = head; cur != NULL; cur = cur->next) {43 printf("%d <-> ", cur->value);44 }45 printf("NULL\n");46}47
48void printBackward(void) {49 for (Node* cur = tail; cur != NULL; cur = cur->prev) {50 printf("%d <-> ", cur->value);51 }52 printf("NULL\n");53}54
55int main(void) {56 int values[] = {10, 20, 30};57 for (int i = 0; i < 3; i++) append(values[i]);58 prepend(5);59 printf("Forward: ");60 printForward();61 printf("Backward: ");62 printBackward();63 return 0;64}Câu hỏi thường gặp về danh sách liên kết đôi
Danh sách liên kết đơn và danh sách liên kết đôi khác nhau như thế nào?
Danh sách liên kết đơn có một con trỏ mỗi nút (
next), nên bạn chỉ có thể đi về phía trước. Danh sách liên kết đôi thêm con trỏ prev, cho phép duyệt ngược và xóa một nút bạn đang giữ tham chiếu trong O(1), với cái giá là thêm một con trỏ mỗi nút và phải cập nhật hai liên kết mỗi khi thay đổi.Khi nào danh sách liên kết đôi đáng với phần bộ nhớ bổ sung?
Khi bạn cần duyệt ngược hoặc xóa trong
O(1) các nút bất kỳ mà bạn đã tham chiếu tới. Các trường hợp kinh điển là deque (hàng đợi hai đầu) và LRU cache, nơi các mục thường xuyên được di chuyển và loại bỏ ở cả hai đầu.Vì sao danh sách liên kết đôi có thể xóa một nút trong O(1)?
Để gỡ một nút, bạn phải nối nút liền trước với nút liền sau của nó. Trong danh sách liên kết đơn, bạn phải đi từ đầu danh sách để tìm nút liền trước (
O(n)); trong danh sách liên kết đôi, con trỏ prev của nút cho bạn nút liền trước ngay lập tức, nên việc nối lại là O(1).Danh sách liên kết đôi hay mảng: nên dùng cái nào?
Dùng mảng khi bạn cần truy cập theo chỉ số
O(1) và duyệt thân thiện với bộ nhớ đệm, và khi việc chèn chủ yếu diễn ra ở cuối. Dùng danh sách liên kết đôi khi bạn thường xuyên chèn hoặc gỡ ở giữa hoặc ở cả hai đầu khi đã có tham chiếu đến nút, vì thao tác đó là O(1) so với O(n) dịch chuyển của mảng. Mảng thắng về bộ nhớ và tính cục bộ; danh sách thắng ở các thao tác thay đổi cấu trúc.Nút lính canh trong danh sách liên kết đôi là gì?
Nút lính canh (sentinel, hay nút giả) là một nút giữ chỗ nằm trước head và/hoặc sau tail để danh sách không bao giờ thực sự rỗng. Nó loại bỏ các bước kiểm tra
null cho head, tail và các thao tác chèn/xóa ở biên, giúp mọi thao tác đi theo cùng một đoạn code nối lại. Nhiều bản cài đặt LRU cache trong môi trường production dùng hai nút lính canh để không phải xử lý riêng hai đầu.Bug phổ biến nhất khi xóa khỏi danh sách liên kết đôi là gì?
Quên cập nhật
head hoặc tail khi xóa nút đầu hoặc nút cuối, để lại một con trỏ treo trỏ đến nút đã bị giải phóng. Luôn kiểm tra xem node.prev có là null không (cập nhật head) hoặc node.next có là null không (cập nhật tail) trước khi nối lại các nút lân cận.Tài nguyên liên quan
Thêm mô phỏng trực quan
