🔗 Danh sách liên kết

Ở trang Mảng, điểm yếu lớn nhất là chèn/xóa ở giữa tốn O(n) vì phải dịch chuyển hàng loạt phần tử - hệ quả trực tiếp của việc dữ liệu buộc phải nằm liên tục trong bộ nhớ. Danh sách liên kết (linked list) giải quyết đúng vấn đề này bằng cách từ bỏ tính liên tục: các phần tử (gọi là node) có thể nằm rải rác bất cứ đâu trong bộ nhớ, mỗi node chỉ cần biết địa chỉ của node tiếp theo thông qua một con trỏ (pointer/reference).

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None   # con trỏ tới node kế tiếp, None nếu là node cuối

Một danh sách liên kết được xác định chỉ bằng cách nắm giữ node đầu tiên - gọi là head. Muốn đi tới node thứ i, không có cách nào khác ngoài đi từng bước từ head qua next, nên truy cập theo chỉ số là O(n) - đây chính là điểm yếu đối lập với mảng.

Đánh đổi: chèn/xóa nhanh, truy cập chậm

	Mảng	Linked List
Truy cập `arr[i]`	O(1)	O(n) - phải đi từng bước từ head
Chèn/xóa khi đã có con trỏ tới vị trí	O(n) - phải dịch chuyển	O(1) - chỉ đổi vài con trỏ
Bộ nhớ	Chỉ chứa dữ liệu	Tốn thêm bộ nhớ cho con trỏ mỗi node
Cache locality	Tốt (dữ liệu liền kề)	Kém (node nằm rải rác)

Chèn một node mới vào giữa danh sách chỉ cần đổi hai con trỏ - không đụng đến bất kỳ node nào khác:

def insert_after(prev, new_node):
    new_node.next = prev.next
    prev.next = new_node   # O(1), miễn là đã có con trỏ 'prev'

So với mảng phải dịch chuyển toàn bộ phần tử phía sau, đây là lợi thế rõ rệt. Cái giá phải trả: để chèn vào một vị trí cụ thể (ví dụ “vị trí thứ 5”), bạn vẫn phải tốn O(n) để đi bộ tới đó trước - linked list chỉ nhanh khi bạn đã có sẵn con trỏ tới điểm cần thao tác, ví dụ trong lúc đang duyệt.

Ba kỹ thuật “hai con trỏ” kinh điển

Rất nhiều bài toán trên linked list được giải bằng cách chạy đồng thời hai con trỏ theo những nhịp độ khác nhau, thay vì tạo cấu trúc dữ liệu phụ.

Đảo ngược danh sách

Duyệt qua danh sách một lần, ở mỗi bước “xoay ngược” con trỏ next để trỏ về node trước đó thay vì node sau:

def reverse(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next   # lưu lại trước khi ghi đè
        curr.next = prev         # đảo hướng con trỏ
        prev = curr
        curr = next_node
    return prev   # prev giờ là head mới

Độ phức tạp O(n) thời gian, O(1) bộ nhớ phụ trội - không cần tạo danh sách mới, chỉ “xoay” các con trỏ đã có sẵn.

Tìm điểm giữa: con trỏ nhanh - chậm (Floyd)

Vì không truy cập được theo chỉ số, muốn tìm node ở giữa không thể làm phép chia length / 2 rồi nhảy thẳng tới. Thay vào đó, chạy hai con trỏ cùng lúc: một con trỏ chậm đi 1 bước mỗi lần, một con trỏ nhanh đi 2 bước mỗi lần. Khi con trỏ nhanh chạm cuối danh sách, con trỏ chậm vừa vặn đứng ở giữa - vì nó luôn đi được đúng một nửa quãng đường của con trỏ nhanh.

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # node ở giữa

Phát hiện vòng lặp (cũng dùng con trỏ Floyd)

Cùng ý tưởng hai con trỏ nhanh-chậm, nhưng dùng cho mục đích khác: nếu danh sách có vòng lặp (node cuối trỏ ngược về một node đã đi qua thay vì None), con trỏ nhanh sẽ đuổi kịp và va vào con trỏ chậm ở đâu đó bên trong vòng lặp - giống hai người chạy vòng quanh một đường đua với tốc độ khác nhau, người chạy nhanh chắc chắn sẽ vượt qua và “gặp lại” người chạy chậm.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:   # hai con trỏ gặp nhau -> có vòng lặp
            return True
    return False   # fast chạm None -> không có vòng lặp

Nếu danh sách không có vòng lặp, con trỏ nhanh sẽ chạm tới None trước khi có cơ hội gặp lại con trỏ chậm. Cách làm này chỉ tốn O(1) bộ nhớ - so với cách “trực quan” hơn là dùng một hash set lưu lại mọi node đã đi qua (cũng đúng, nhưng tốn thêm O(n) bộ nhớ).

Khi nào chọn linked list thay vì mảng?

Linked list phù hợp khi khối lượng dữ liệu thay đổi liên tục và bạn thường xuyên chèn/xóa ở giữa (ví dụ cài đặt hàng đợi, ngăn xếp, hoặc danh sách phát nhạc có thể chèn bài hát bất kỳ vị trí nào). Ngược lại, nếu chủ yếu là truy cập ngẫu nhiên theo chỉ số hoặc cần tận dụng cache CPU cho hiệu năng cao, mảng (đặc biệt là mảng động) vẫn là lựa chọn mặc định.