Danh sách liên kết¶
Bộ nhớ là tài nguyên dùng chung cho tất cả các chương trình. Trong một môi trường chạy phức tạp, bộ nhớ trống có thể bị phân tán khắp không gian địa chỉ. Chúng ta biết rằng mảng yêu cầu vùng nhớ liên tục, và khi một mảng rất lớn, hệ thống có thể không cung cấp được một khối bộ nhớ liên tục lớn như vậy. Đây chính là lúc tính linh hoạt của danh sách liên kết được phát huy.
Một danh sách liên kết (linked list) là một cấu trúc dữ liệu tuyến tính trong đó mỗi phần tử là một đối tượng nút (node), và các nút được kết nối thông qua các "tham chiếu". Một tham chiếu ghi lại địa chỉ bộ nhớ của nút tiếp theo, qua đó có thể truy cập nút tiếp theo từ nút hiện tại.
Thiết kế này cho phép các nút của danh sách liên kết được lưu trữ ở các vị trí khác nhau trong bộ nhớ và địa chỉ của chúng không cần phải liên tục.
Quan sát hình trên, đơn vị cơ bản của danh sách liên kết là đối tượng nút (node). Mỗi nút chứa hai phần dữ liệu: "giá trị" của nút và một "tham chiếu" đến nút tiếp theo.
- Nút đầu tiên của danh sách liên kết được gọi là nút đầu (head node), và nút cuối cùng được gọi là nút cuối (tail node).
- Nút cuối trỏ đến rỗng, được biểu diễn lần lượt là
null,nullptrvàNonetrong Java, C++ và Python. - Trong các ngôn ngữ hỗ trợ con trỏ như C, C++, Go và Rust, "tham chiếu" nói trên sẽ được thay thế bằng con trỏ (pointer).
Như hiển thị trong mã nguồn sau, một nút danh sách liên kết ListNode không chỉ chứa một giá trị mà còn có thêm một tham chiếu (con trỏ). Do đó, danh sách liên kết chiếm dụng nhiều không gian bộ nhớ hơn mảng khi lưu trữ cùng một lượng dữ liệu.
/* Cấu trúc nút của danh sách liên kết */
typedef struct ListNode {
int val; // Giá trị của nút
struct ListNode *next; // Con trỏ đến nút tiếp theo
} ListNode;
/* Hàm khởi tạo */
ListNode *newListNode(int val) {
ListNode *node;
node = (ListNode *) malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
return node;
}
Các thao tác danh sách liên kết thông thường¶
Khởi tạo danh sách liên kết¶
Xây dựng danh sách liên kết gồm hai bước: thứ nhất, khởi tạo từng đối tượng nút; thứ hai, thiết lập các mối quan hệ tham chiếu giữa các nút. Sau khi hoàn thành việc khởi tạo, chúng ta có thể duyệt qua tất cả các nút bắt đầu từ nút đầu của danh sách liên kết thông qua tham chiếu next.
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
ListNode n0 = new(1);
ListNode n1 = new(3);
ListNode n2 = new(2);
ListNode n3 = new(5);
ListNode n4 = new(4);
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
let n0 = ListNode(x: 1)
let n1 = ListNode(x: 3)
let n2 = ListNode(x: 2)
let n3 = ListNode(x: 5)
let n4 = ListNode(x: 4)
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
ListNode n0 = ListNode(1);
ListNode n1 = ListNode(3);
ListNode n2 = ListNode(2);
ListNode n3 = ListNode(5);
ListNode n4 = ListNode(4);
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
let n0 = Rc::new(RefCell::new(ListNode { val: 1, next: None }));
let n1 = Rc::new(RefCell::new(ListNode { val: 3, next: None }));
let n2 = Rc::new(RefCell::new(ListNode { val: 2, next: None }));
let n3 = Rc::new(RefCell::new(ListNode { val: 5, next: None }));
let n4 = Rc::new(RefCell::new(ListNode { val: 4, next: None }));
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0.borrow_mut().next = Some(n1.clone());
n1.borrow_mut().next = Some(n2.clone());
n2.borrow_mut().next = Some(n3.clone());
n3.borrow_mut().next = Some(n4.clone());
/* Khởi tạo danh sách liên kết 1 -> 3 -> 2 -> 5 -> 4 */
// Khởi tạo từng nút
ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);
// Xây dựng mối quan hệ tham chiếu giữa các nút
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
Trực quan hóa mã nguồn
https://pythontutor.com/render.html#code=class%20ListNode%3A%0A%20%20%20%20%22%22%22%E9%93%BE%E8%A1%A8%E8%8A%82%E7%82%B9%E7%B1%BB%22%22%22%0A%20%20%20%20def%20__init__%28self,%20val%3A%20int%29%3A%0A%20%20%20%20%20%20%20%20self.val%3A%20int%20%3D%20val%20%20%23%20%E8%8A%82%E7%82%B9%E5%80%BC%0A%20%20%20%20%20%20%20%20self.next%3A%20ListNode%20%7C%20None%20%3D%20None%20%20%23%20%E5%90%8E%E7%BB%A7%E8%8A%82%E7%82%B9%E5%BC%95%E7%94%A8%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E9%93%BE%E8%A1%A8%201%20-%3E%203%20-%3E%202%20-%3E%205%20-%3E%204%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%90%84%E4%B8%AA%E8%8A%82%E7%82%B9%0A%20%20%20%20n0%20%3D%20ListNode%281%29%0A%20%20%20%20n1%20%3D%20ListNode%283%29%0A%20%20%20%20n2%20%3D%20ListNode%282%29%0A%20%20%20%20n3%20%3D%20ListNode%285%29%0A%20%20%20%20n4%20%3D%20ListNode%284%29%0A%20%20%20%20%23%20%E6%9E%84%E5%BB%BA%E8%8A%82%E7%82%B9%E4%B9%8B%E9%97%B4%E7%9A%84%E5%BC%95%E7%94%A8%0A%20%20%20%20n0.next%20%3D%20n1%0A%20%20%20%20n1.next%20%3D%20n2%0A%20%20%20%20n2.next%20%3D%20n3%0A%20%20%20%20n3.next%20%3D%20n4&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
Một mảng là một biến duy nhất; ví dụ, một mảng nums chứa các phần tử nums[0], nums[1], v.v. Ngược lại, một danh sách liên kết được cấu thành từ nhiều đối tượng nút độc lập. Chúng ta thường lấy nút đầu để đại diện cho toàn bộ danh sách liên kết; ví dụ, danh sách liên kết trong mã nguồn trên có thể được gọi là danh sách liên kết n0.
Chèn nút¶
Chèn một nút trong danh sách liên kết rất dễ dàng. Như hình bên dưới, giả sử chúng ta muốn chèn một nút mới P vào giữa hai nút liền kề n0 và n1. Chúng ta chỉ cần thay đổi hai tham chiếu (con trỏ) của nút, với độ phức tạp thời gian là \(O(1)\).
Ngược lại, độ phức tạp thời gian của việc chèn một phần tử trong mảng là \(O(n)\), hiệu năng kém khi xử lý lượng dữ liệu lớn.
Xóa nút¶
Như hình bên dưới, việc xóa một nút trong danh sách liên kết cũng rất thuận tiện. Chúng ta chỉ cần thay đổi tham chiếu (con trỏ) của một nút.
Lưu ý rằng mặc dù nút P vẫn trỏ đến n1 sau khi hoàn thành thao tác xóa, danh sách liên kết không còn khả năng truy cập P khi duyệt qua nữa, nghĩa là P không còn thuộc về danh sách liên kết này nữa.
Truy cập nút¶
Truy cập nút trong danh sách liên kết kém hiệu quả hơn. Như đã đề cập ở phần trước, chúng ta có thể truy cập bất kỳ phần tử nào trong mảng với thời gian \(O(1)\). Điều này không đúng với danh sách liên kết. Chương trình cần bắt đầu từ nút đầu và duyệt tuần tự về sau cho đến khi tìm thấy nút mục tiêu. Nghĩa là, việc truy cập nút thứ \(i\) trong danh sách liên kết yêu cầu \(i - 1\) lần lặp, với độ phức tạp thời gian là \(O(n)\).
Tìm kiếm nút¶
Duyệt qua danh sách liên kết để tìm nút có giá trị target và xuất ra chỉ số của nút đó trong danh sách liên kết. Quá trình này cũng là một tìm kiếm tuyến tính. Mã nguồn được hiển thị bên dưới:
So sánh mảng và danh sách liên kết¶
Bảng bên dưới tóm tắt các đặc điểm của mảng và danh sách liên kết, đồng thời so sánh hiệu quả hoạt động của chúng. Vì chúng sử dụng hai chiến lược lưu trữ hoàn toàn trái ngược nhau, nên các đặc tính và hiệu quả hoạt động khác nhau của chúng cũng thể hiện những đặc điểm tương phản.
Bảng
| Mảng | Danh sách liên kết | |
|---|---|---|
| Phương thức lưu trữ | Vùng nhớ liên tục | Vùng nhớ phân tán |
| Mở rộng dung lượng | Độ dài bất biến | Mở rộng linh hoạt |
| Hiệu quả bộ nhớ | Các phần tử chiếm ít bộ nhớ hơn, nhưng không gian có thể bị lãng phí | Các phần tử chiếm nhiều bộ nhớ hơn |
| Truy cập phần tử | \(O(1)\) | \(O(n)\) |
| Thêm phần tử | \(O(n)\) | \(O(1)\) |
| Xóa phần tử | \(O(n)\) | \(O(1)\) |
Các loại danh sách liên kết phổ biến¶
Như hình bên dưới, có ba loại danh sách liên kết phổ biến:
- Danh sách liên kết đơn (singly linked list): Đây là loại danh sách liên kết thông thường được giới thiệu ở trên. Các nút của danh sách liên kết đơn chứa một giá trị và một tham chiếu đến nút tiếp theo. Chúng ta gọi nút đầu tiên là nút đầu và nút cuối cùng là nút cuối; nút cuối trỏ đến
None. - Danh sách liên kết vòng (circular linked list): Nếu chúng ta để nút cuối của danh sách liên kết đơn trỏ ngược về nút đầu (nối đuôi vào đầu), ta sẽ được một danh sách liên kết vòng. Trong danh sách liên kết vòng, bất kỳ nút nào cũng có thể được xem là nút đầu.
- Danh sách liên kết đôi (doubly linked list): So với danh sách liên kết đơn, danh sách liên kết đôi ghi lại tham chiếu ở cả hai hướng. Định nghĩa nút của danh sách liên kết đôi bao gồm cả tham chiếu đến nút kế tiếp (successor node) và nút trước đó (predecessor node). So với danh sách liên kết đơn, danh sách liên kết đôi linh hoạt hơn và có thể duyệt qua danh sách liên kết theo cả hai hướng, nhưng nó cũng đòi hỏi nhiều không gian bộ nhớ hơn.
/* Cấu trúc nút của danh sách liên kết đôi */
type DoublyListNode struct {
Val int // Giá trị của nút
Next *DoublyListNode // Con trỏ đến nút kế tiếp
Prev *DoublyListNode // Con trỏ đến nút trước đó
}
// NewDoublyListNode Khởi tạo
func NewDoublyListNode(val int) *DoublyListNode {
return &DoublyListNode{
Val: val,
Next: nil,
Prev: nil,
}
}
/* Lớp biểu diễn nút của danh sách liên kết đôi */
class ListNode {
constructor(val, next, prev) {
this.val = val === undefined ? 0 : val; // Giá trị của nút
this.next = next === undefined ? null : next; // Tham chiếu đến nút kế tiếp
this.prev = prev === undefined ? null : prev; // Tham chiếu đến nút trước đó
}
}
/* Lớp biểu diễn nút của danh sách liên kết đôi */
class ListNode {
val: number;
next: ListNode | null;
prev: ListNode | null;
constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {
this.val = val === undefined ? 0 : val; // Giá trị của nút
this.next = next === undefined ? null : next; // Tham chiếu đến nút kế tiếp
this.prev = prev === undefined ? null : prev; // Tham chiếu đến nút trước đó
}
}
use std::rc::Rc;
use std::cell::RefCell;
/* Cấu trúc nút của danh sách liên kết đôi */
#[derive(Debug)]
struct ListNode {
val: i32, // Giá trị của nút
next: Option<Rc<RefCell<ListNode>>>, // Con trỏ đến nút kế tiếp
prev: Option<Rc<RefCell<ListNode>>>, // Con trỏ đến nút trước đó
}
/* Hàm khởi tạo (constructor) */
impl ListNode {
fn new(val: i32) -> Self {
ListNode {
val,
next: None,
prev: None,
}
}
}
/* Cấu trúc nút của danh sách liên kết đôi */
typedef struct ListNode {
int val; // Giá trị của nút
struct ListNode *next; // Con trỏ đến nút kế tiếp
struct ListNode *prev; // Con trỏ đến nút trước đó
} ListNode;
/* Hàm khởi tạo (constructor) */
ListNode *newListNode(int val) {
ListNode *node;
node = (ListNode *) malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
node->prev = NULL;
return node;
}
# Lớp biểu diễn nút của danh sách liên kết đôi
class ListNode
attr_accessor :val # Giá trị của nút
attr_accessor :next # Tham chiếu đến nút kế tiếp
attr_accessor :prev # Tham chiếu đến nút trước đó
def initialize(val=0, next_node=nil, prev_node=nil)
@val = val
@next = next_node
@prev = prev_node
end
end
Ứng dụng điển hình của danh sách liên kết¶
Danh sách liên kết đơn thường được sử dụng để triển khai ngăn xếp, hàng đợi, bảng băm và đồ thị.
- Ngăn xếp và hàng đợi: Khi thao tác chèn và xóa đều xảy ra ở một đầu của danh sách liên kết, nó thể hiện đặc tính vào-sau-ra-trước (LIFO), tương ứng với ngăn xếp. Khi thao tác chèn xảy ra ở một đầu của danh sách liên kết và thao tác xóa xảy ra ở đầu còn lại, nó thể hiện đặc tính vào-trước-ra-trước (FIFO), tương ứng với hàng đợi.
- Bảng băm: Phương pháp xích trực tiếp (separate chaining) là một trong những giải pháp phổ biến để giải quyết xung đột băm. Trong phương pháp này, tất cả phần tử bị trùng mã băm được xếp chung vào một danh sách liên kết.
- Đồ thị: Danh sách kề (adjacency list) là một phương pháp phổ biến để biểu diễn đồ thị, trong đó mỗi đỉnh của đồ thị liên kết với một danh sách liên kết, và mỗi phần tử trong danh sách liên kết biểu diễn cho một đỉnh khác được nối với đỉnh đó.
Danh sách liên kết đôi thường được sử dụng trong các kịch bản đòi hỏi truy cập nhanh vào phần tử trước và kế tiếp.
- Cấu trúc dữ liệu nâng cao: Ví dụ, trong cây đỏ-đen và cây B, chúng ta cần truy cập nút cha của một nút, điều này có thể thực hiện bằng cách lưu trữ một tham chiếu đến nút cha ngay tại nút đó, tương tự như danh sách liên kết đôi.
- Lịch sử trình duyệt: Trong các trình duyệt web, khi người dùng nhấp vào nút tiến hoặc lùi, trình duyệt cần biết các trang web trước đó và tiếp theo mà người dùng đã truy cập. Đặc điểm của danh sách liên kết đôi giúp thao tác này trở nên đơn giản.
- Thuật toán LRU: Trong các thuật toán loại bỏ bộ đệm (LRU), chúng ta cần tìm nhanh dữ liệu ít được sử dụng gần đây nhất và hỗ trợ việc thêm và xóa nhanh các nút. Việc sử dụng danh sách liên kết đôi là rất phù hợp cho mục đích này.
Danh sách liên kết vòng thường được sử dụng trong các kịch bản yêu cầu hoạt động tuần hoàn, chẳng hạn như lập lịch tài nguyên của hệ điều hành.
- Thuật toán lập lịch luân phiên (round-robin scheduling algorithm): Trong hệ điều hành, lập lịch luân phiên (Round-robin) là một thuật toán điều phối CPU phổ biến cần xoay vòng qua một tập hợp các tiến trình. Mỗi tiến trình được gán một lát cắt thời gian, và khi hết thời gian, CPU sẽ chuyển sang tiến trình tiếp theo. Hoạt động tuần hoàn này có thể được triển khai bằng danh sách liên kết vòng.
- Bộ đệm dữ liệu (data buffer): Trong một số triển khai bộ đệm dữ liệu, danh sách liên kết vòng cũng có thể được sử dụng. Ví dụ, trong các trình phát âm thanh và video, luồng dữ liệu có thể được chia thành nhiều khối bộ đệm và đưa vào danh sách liên kết vòng để phát liên tục.