Sách giáo khoa dạy rất rõ: danh sách liên kết chèn và xóa trong O(1) (chỉ đổi vài con trỏ), còn mảng cần O(n) (phải dịch các phần tử). Kết luận có vẻ hiển nhiên: tải nào chèn/xóa nhiều thì chọn danh sách liên kết. Tôi định viết bài đúng theo lý thuyết đó — rồi đo, và con số lật ngược hẳn. Danh sách liên kết chậm hơn mảng động (vector) ngay ở chính thao tác chèn mà nó được cho là mạnh. Thủ phạm, một lần nữa, là cache.
Lý thuyết đẹp, thực tế khác
Big-O của các thao tác đúng như sách nói. Vấn đề là big-O đếm số phép trên cấu trúc, không đếm chi phí thật của mỗi phép chạm bộ nhớ — và như bài mở sê-ri đã nhấn, big-O là hình dạng khi n lớn, không phải tốc độ thật. Ở đây có hai điều bị bỏ qua, và chúng đảo ngược mọi thứ.
Thứ nhất, node của danh sách liên kết rải khắp bộ nhớ. Mỗi lần cấp phát một node, bộ cấp phát trả về một địa chỉ bất kỳ; các node kề nhau về mặt logic (theo con trỏ next) lại nằm cách xa nhau trong RAM. Duyệt danh sách vì thế là pointer-chasing — đúng cái mẫu truy cập ngẫu nhiên mà bài trước đo là chậm hàng trăm lần. Mảng thì ngược lại: các phần tử nằm liền nhau, duyệt tuần tự, thân thiện cache và prefetch.
Thứ hai, "chèn O(1)" của danh sách liên kết ẩn một điều kiện: bạn phải đã có con trỏ tới vị trí cần chèn. Trong thực tế, thường bạn phải tìm vị trí trước — và tìm nghĩa là đi bộ từ đầu danh sách qua từng node, một cuộc pointer-chase O(n) cache-hostile. Cái O(1) đẹp đẽ chỉ là phần cuối, sau một O(n) đắt đỏ.
Đo: mảng thắng cả duyệt lẫn chèn
Tôi viết cả hai bằng C, đo bằng clock_gettime lấy trung vị. Đầu tiên, duyệt tổng 10 triệu phần tử — cộng tất cả giá trị:
mảng (tuần tự) : 2 ms (0,24 ns/phần tử)
linked list (rải) : 965 ms (96,5 ns/phần tử)
-> linked list chậm 395 lần
Cùng O(n), cùng 10 triệu phép cộng, mà danh sách liên kết chậm 395 lần — vì mỗi node là một cache-miss phải chờ RAM, còn mảng streamed qua với prefetch. Đây chưa phải chỗ bất ngờ; ai cũng biết mảng duyệt nhanh hơn. Con số 96,5 ns/phần tử của danh sách liên kết gần đúng bằng độ trễ một chuyến xuống RAM đo ở bài trước (103 ns) — không phải trùng hợp: mỗi node là một lần đọc RAM đầy đủ vì node kế tiếp không thể đoán trước để prefetch, đúng bản chất pointer-chase. Bất ngờ nằm ở phép chèn, nơi danh sách liên kết được cho là vô địch.
Tôi chèn 40.000 lần, mỗi lần tại một vị trí ngẫu nhiên, xây dần cấu trúc:
vector (memmove) : 49,6 ms
linked list (walk+splice): 1560,5 ms
-> linked list chậm 31 lần
Danh sách liên kết chậm hơn vector 31 lần ngay ở thao tác chèn. Đây đúng là chỗ tôi đo hớ. Tôi tin "chèn O(1) tốt hơn chèn O(n)", nên trông đợi list thắng. Nhưng với vector, chèn tại vị trí p là một lệnh memmove dịch phần đuôi — O(n) về số phép, nhưng memmove là chép một khối liền mạch, được phần cứng và trình biên dịch tối ưu cực mạnh, chạy gần tốc độ băng thông bộ nhớ. Với danh sách liên kết, để chèn tại vị trí p tôi phải đi bộ p node từ đầu — mỗi bước một cache-miss — rồi mới splice O(1). Cái O(n) walk cache-hostile đó nuốt trọn lợi thế O(1) splice, và thua đậm memmove tuần tự.
Nói cách khác: cả vector lẫn list đều tốn O(n) cho một lần chèn-cần-tìm (dịch, hoặc đi bộ), nhưng O(n) của vector là tuần tự (nhanh) còn O(n) của list là ngẫu nhiên (chậm). Big-O ghi cả hai là "O(n)" và che mất khác biệt cả chục lần. Đây là một chủ đề sẽ lặp lại trong sê-ri: hai thuật toán cùng ký hiệu big-O có thể chênh nhau rất xa vì hằng số ẩn — mà ở cấu trúc dữ liệu, hằng số ẩn lớn nhất thường chính là chi phí truy cập bộ nhớ.
Khi nào danh sách liên kết thật sự thắng
Để công bằng: danh sách liên kết không vô dụng. Cái O(1) splice là thật — nhưng chỉ hữu ích khi bạn đã giữ sẵn con trỏ tại vị trí, không phải tìm. Ví dụ điển hình: bạn đang duyệt danh sách và xóa/chèn ngay tại node hiện tại; hoặc bạn giữ nhiều iterator và splice qua lại giữa các danh sách mà không cần tìm kiếm. Trong những ca đó, splice O(1) của list thắng memmove O(n) của vector, và list là lựa chọn đúng. Một biến thể hay dùng là danh sách liên kết cấp phát từ một pool liền mạch (các node nằm sát nhau trong một mảng), vừa giữ được splice O(1) vừa bớt cache-miss khi duyệt — một cách vá đúng cái nhược điểm ta vừa đo, cho thấy vấn đề gốc là bố cục bộ nhớ, không phải bản thân ý tưởng liên kết. Nhưng đó là ngoại lệ, không phải mặc định — và điểm mấu chốt là phải giữ sẵn vị trí, thứ mà mô hình "chèn O(1)" trong đầu thường quên mất.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: mặc định hãy dùng mảng động (vector, ArrayList, slice), không phải danh sách liên kết. Với hầu hết tải thực — duyệt, tìm rồi chèn, xây rồi đọc — mảng thắng nhờ locality, thường vài chục tới vài trăm lần, dù big-O của vài thao tác nghe có vẻ tệ hơn. Danh sách liên kết là công cụ chuyên dụng cho trường hợp bạn giữ con trỏ và splice nhiều mà không tìm. Cũng đáng nhớ: mảng động còn thắng ở những chi phí khó thấy — ít cấp phát hơn (một khối lớn thay vì một node mỗi phần tử), ít tốn bộ nhớ hơn (không phải lưu con trỏ next cho từng phần tử), và thân thiện hơn với mọi tầng tối ưu của phần cứng.
Hệ quả thứ hai: big-O của một thao tác đơn lẻ không phải toàn bộ câu chuyện. Con số mang theo: lý thuyết cho linked list chèn/xóa O(1) so với mảng O(n), nhưng đo thật thì mảng thắng cả hai — duyệt 10 triệu phần tử mảng 2ms so linked list 965ms (chậm 395 lần vì pointer-chase cache-miss), và chèn 40k lần vector 49,6ms so linked list 1560ms (chậm 31 lần vì O(1) splice bị O(n) walk tìm vị trí nuốt); linked list chỉ thắng khi đã giữ sẵn con trỏ. Đừng chọn cấu trúc dữ liệu bằng big-O của một thao tác trên giấy — đo cả tải thật, và nhớ rằng locality thường quan trọng hơn số phép.
Thử ba mươi giây
Trong đầu, hình dung bạn cần một hàng đợi mà thỉnh thoảng xóa phần tử ở giữa. Trực giác "xóa giữa nên dùng linked list" nghe hợp lý. Nhưng hỏi: bạn tìm phần tử cần xóa thế nào? Nếu phải quét từ đầu để tìm nó, bạn đã trả một O(n) pointer-chase cache-hostile trước khi splice — và một vector với memmove gần như luôn nhanh hơn ở cùng việc đó. Chỉ khi bạn đã có tay cầm trực tiếp tới phần tử (một iterator đang trỏ vào nó) thì O(1) của linked list mới thật sự đáng. Ba mươi giây tự hỏi "tôi có sẵn con trỏ, hay phải đi tìm?" gần như luôn dẫn bạn về lại mảng.
