Danh sách liên kết (linked list): cách hoạt động, code và độ phức tạp

Danh sách liên kết giải quyết vấn đề gì

Mảng (một list trong Python) lưu các phần tử trong một khối bộ nhớ liên tục. Đọc a[i] là tức thì, nhưng chèn vào đầu mảng buộc mọi phần tử khác dịch sang phải một ô, tốn O(n). Danh sách liên kết tránh việc dịch này: mỗi phần tử nằm trong node riêng, các node nối với nhau bằng tham chiếu. Khi chèn, bạn chỉ cần đổi vài tham chiếu.

Danh sách liên kết là viên gạch nền móng của nhiều cấu trúc khác: ngăn xếp, hàng đợi, bucket của bảng băm (nối chuỗi - separate chaining), bộ nhớ đệm LRU và danh sách kề trong đồ thị.

Ý tưởng giải thích đơn giản

Hãy hình dung trò chơi tìm kho báu: mỗi manh mối chỉ cho bạn manh mối tiếp theo ở đâu. Bạn không thể nhảy thẳng tới manh mối số 7, mà phải đi qua manh mối 1 đến 6 trước. Bản thân danh sách chỉ nhớ node đầu tiên, gọi là head. Node cuối trỏ tới không có gì (None).

Ví dụ minh họa: chèn và xóa

Bắt đầu với danh sách 3 -> 7 -> 9. Ta chèn 5 sau 3, rồi xóa 7.

1. Tạo một node mới có giá trị 5.
2. Gán new.next bằng node đứng sau 3 (node 7).
3. Gán node3.next bằng node mới. Danh sách lúc này là 3 -> 5 -> 7 -> 9.
4. Để xóa 7, tìm node đứng trước nó (5) bằng cách đi từ head.
5. Gán node5.next = node5.next.next, thao tác này bỏ qua 7. Danh sách lúc này là 3 -> 5 -> 9. Bộ thu gom rác của Python sẽ giải phóng node không còn truy cập được.

Cài đặt danh sách liên kết đơn bằng Python

Lớp này giữ tham chiếu tới head và một biến đếm kích thước. Nó hỗ trợ thêm vào đầu và cuối, xóa giá trị khớp đầu tiên, và duyệt (iteration).

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1
    def push_back(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1
    def remove(self, value):
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False          # not found
        if prev is None:
            self.head = cur.next  # removing the head
        else:
            prev.next = cur.next
        self.size -= 1
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next

items = LinkedList()
for x in [3, 7, 9]:
    items.push_back(x)
items.push_front(1)
items.remove(7)
print(list(items), items.size)  # [1, 3, 9] 3

Ở đây push_back đi qua toàn bộ danh sách nên tốn O(n). Giữ thêm một tham chiếu tail sẽ đưa nó về O(1); các cài đặt hàng đợi thực tế đều làm như vậy.

Thao tác kinh điển: đảo ngược và phát hiện chu trình

Đảo ngược danh sách tại chỗ là câu hỏi phỏng vấn về danh sách liên kết phổ biến nhất. Duyệt danh sách một lần và quay ngược từng con trỏ next.

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next     # remember the rest
        cur.next = prev    # turn the pointer around
        prev, cur = cur, nxt
    return prev            # new head
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)  # 3 2 1
print(has_cycle(head))  # False

has_cycle là thuật toán rùa và thỏ của Floyd: con trỏ chậm đi một bước, con trỏ nhanh đi hai bước. Nếu có vòng lặp, con trỏ nhanh cuối cùng sẽ gặp con trỏ chậm; nếu không, nó sẽ tới None. Thuật toán chỉ dùng O(1) bộ nhớ phụ.

Độ phức tạp thời gian và không gian

Trên thực tế, mảng thường nhanh hơn ngay cả ở những thao tác mà danh sách liên kết có Big O tốt hơn, vì các phần tử mảng nằm cạnh nhau trong bộ nhớ và tận dụng tốt cache của CPU. Các node của danh sách liên kết nằm rải rác.

Các biến thể và lỗi thường gặp

• Quên trường hợp danh sách rỗng: luôn kiểm tra head is None trước khi đọc head.next.
• Mất phần còn lại của danh sách do ghi đè next trước khi lưu nó lại (xem nxt trong reverse).
• Không cập nhật head khi xóa node đầu tiên, hoặc tail khi xóa node cuối.
• Dùng đệ quy trên danh sách rất dài: giới hạn đệ quy mặc định của Python khoảng 1000 khung, nên code lặp an toàn hơn.
• Một node đầu giả (sentinel) loại bỏ hầu hết các trường hợp đặc biệt: khi đó mọi node thật đều có node đứng trước.
• Trong danh sách liên kết đôi, mỗi lần chèn và xóa phải cập nhật bốn tham chiếu; sót một cái sẽ làm hỏng danh sách mà không báo lỗi.

Khi nào dùng danh sách liên kết, và nên dùng gì trong Python

Hãy dùng danh sách liên kết khi bạn chèn và xóa ở hai đầu hoặc ở giữa tại những vị trí bạn đã nắm sẵn tham chiếu, và hiếm khi cần truy cập ngẫu nhiên. Ví dụ: bộ nhớ đệm LRU (danh sách liên kết đôi cộng bảng băm), free list của bộ cấp phát bộ nhớ, lịch sử hoàn tác (undo), hoặc các bucket của bảng băm.

Trong code Python hằng ngày bạn hiếm khi tự viết. Với hàng đợi hoặc deque, hãy dùng collections.deque, cho phép thêm và lấy ở cả hai đầu với O(1). Với các dãy thông thường, dùng list. Chỉ tự viết danh sách liên kết để học, để phỏng vấn, và khi cần ghép node trong O(1), như trong bộ nhớ đệm LRU.

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
print(q.popleft(), q.pop(), list(q))  # 0 4 [1, 2, 3]