Danh sách liên kết

Wiki › Cấu trúc dữ liệu

huunguyen · Last updated 28, Tháng 3, 2026, 22:44

Danh sách liên kết (Linked List) là cấu trúc dữ liệu mà mỗi phần tử (node) chứa giá trị và con trỏ đến node tiếp theo. Khác với mảng, các node không cần nằm liền nhau trong bộ nhớ.

So sánh với mảng

Thao tác	Mảng	Danh sách liên kết
Truy cập `a[i]`	$O (1)$	$O (N)$
Chèn/xóa đầu	$O (N)$	$O (1)$
Chèn/xóa cuối	$O (1)$	$O (1)$ (nếu có tail pointer)
Chèn/xóa giữa	$O (N)$	$O (1)$ (nếu đã có con trỏ)
Bộ nhớ	Liên tiếp	Phân tán (overhead con trỏ)

Trong thực tế thi đấu

Trong lập trình thi đấu, bạn hiếm khi cần tự cài danh sách liên kết. Thay vào đó dùng:

std::list hoặc std::deque trong C++
collections.deque trong Python

Cài đặt danh sách liên kết đơn trong C++

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

struct LinkedList {
    Node* head = nullptr;

    void push_front(int v) {
        Node* node = new Node(v);
        node->next = head;
        head = node;
    }

    void print() {
        for (Node* cur = head; cur; cur = cur->next)
            cout << cur->val << " ";
        cout << "\n";
    }
};

Cài đặt bằng mảng (Array-based Linked List)

Trong thi đấu, thường dùng mảng để giả lập linked list — nhanh hơn do tránh cấp phát bộ nhớ động:

const int MAXN = 100005;
int val[MAXN], nxt[MAXN], head, cnt;

void init() { head = -1; cnt = 0; }

void push_front(int v) {
    val[cnt] = v;
    nxt[cnt] = head;
    head = cnt++;
}

for (int i = head; i != -1; i = nxt[i])
    cout << val[i] << " ";

Danh sách liên kết đôi (Doubly Linked List)

#include <list>
list<int> lst = {1, 2, 3};
lst.push_front(0);   // O(1)
lst.push_back(4);    // O(1)
auto it = lst.begin();
lst.erase(it);       // O(1)

from collections import deque
dq = deque([1, 2, 3])
dq.appendleft(0)  # O(1)
dq.append(4)      # O(1)
dq.popleft()      # O(1)

Ứng dụng

Cài đặt Stack và Queue.
Biểu diễn danh sách kề trong đồ thị.
LRU Cache (kết hợp với hash map).

Bình luận

Không có bình luận tại thời điểm này.