Linked list chèn O(1)? Chỉ khi bạn đã đứng sẵn ở đúng chỗ

Hình dung một xâu chuỗi hạt rất dài. Nếu bạn đang cầm đúng chỗ cần thêm một hạt, việc thêm chỉ là tháo một mắt nối rồi cài hạt mới vào — một cái tách, một cái cài, xong ngay. Nhưng nếu bạn không biết chỗ đó ở đâu và phải lần theo xâu từ đầu, sờ từng hạt một cho tới khi đến nơi, thì phần lớn công sức nằm ở chặng đi tìm, không phải ở cái cài hạt. "Linked list chèn O(1)" là câu chuyện về cái cài hạt — và nó lặng lẽ bỏ quên chặng đi tìm.

Đây là câu trả lời phỏng vấn ai cũng thuộc: "Chèn/xóa thì dùng danh sách liên kết — nó O(1), còn mảng phải dịch phần tử nên O(N)." Nghe hợp lý: mảng nằm liền nhau, chèn vào giữa thì phải đẩy nửa mảng sang chỗ khác; linked list chỉ cần nối lại vài con trỏ. Nhưng câu đó giấu một chữ nếu to đùng — và khi tôi đo, chính cái nếu đó lật ngược kết luận trong trường hợp phổ biến nhất. Tôi đo chèn bằng cả hai cấu trúc trong container gcc:13, ba tình huống, và con số cho thấy "O(1)" của linked list là một lời hứa có điều kiện.

Dịch phần tử, hay nối con trỏ — và cái bẫy "tìm chỗ"

Mảng (liền mạch): chèn/xóa ở cuối là O(1) — push_back của vector chỉ ghi vào ô trống kế tiếp. Nhưng chèn/xóa ở đầu hay giữa thì phải memmove dịch mọi phần tử phía sau — trung bình ~N/2 phần tử, tức O(N). Nếu bạn chèn N lần liên tiếp vào đầu mảng, mỗi lần dịch cả mảng, tổng công là O(N²).

Linked list: nếu bạn đã có con trỏ tới node cần thao tác, chèn/xóa chỉ là đổi vài con trỏ next — O(1) thật, không phụ thuộc N. Đây là lời hứa nổi tiếng — cái tách-cài-hạt. Nhưng chú ý chữ nếu đã có con trỏ: trong đời thực, thường bạn không có sẵn con trỏ — bạn phải tìm vị trí trước, mà tìm trong linked list nghĩa là duyệt từ đầu, và như phần 1 của sê-ri đã đo, mỗi bước p = p->next là một cache miss ~104 ns vì node rải rác trong bộ nhớ.

Vậy chi phí thật của "chèn vào giữa" gồm hai phần: tìm vị trí + thao tác. Linked list thắng ở phần thao tác (O(1) vs O(N) dịch mảng), nhưng có thể thua nặng ở phần tìm (duyệt cache-miss vs quét mảng thân thiện cache). Tôi đo cả ba tình huống để tách bạch.

Đo: ba tình huống, kết quả đảo chiều

Chèn phần tử (gcc:13, min của nhiều lần):

A. CHÈN Ở ĐẦU
   mảng  N=200k : 13.996 ns/chèn  (tổng ~20 tỷ phần tử dịch, O(N²))
   list  N=200k :      0,2 ns/chèn (chỉ đổi con trỏ head, O(1))
   -> list nhanh hơn mảng ~70.000 lần

B. CHÈN Ở GIỮA, khi ĐÃ CÓ con trỏ tới chỗ đó (M=20k lần)
   mảng          : 7.770 ns/chèn  (memmove dịch ~N/2)
   list          :   0,3 ns/chèn  (đổi 2 con trỏ, O(1))
   -> list nhanh hơn ~26.000 lần

C. CHÈN Ở GIỮA THỰC TẾ, phải TÌM vị trí trước (M=20k lần)
   mảng          :  20.457 ns/chèn (quét tuần tự tìm + memmove)
   list          : 335.382 ns/chèn (DUYỆT tìm = cache miss mỗi bước + chèn)
   -> list CHẬM hơn mảng ~16 lần

Nhìn tình huống A (chèn đầu): linked list đúng như sách — 0,2 ns mỗi lần chèn, chỉ đổi con trỏ head, hoàn toàn O(1) bất kể N. Mảng thì thảm họa: mỗi lần chèn đầu phải dịch toàn bộ, 13.996 ns, và tổng số phần tử phải dịch lên tới ~20 tỷ (O(N²)). Ở đây linked list nhanh hơn ~70.000 lần. Nếu tác vụ của bạn là liên tục thêm vào đầu (một stack, một hàng đợi đầu), linked list (hay deque) thắng tuyệt đối.

Tình huống B (chèn giữa, đã cầm con trỏ) cũng nghiêng về list: 0,3 ns vs 7.770 ns. Nếu bạn đã giữ con trỏ tới chỗ cần sửa (ví dụ đang duyệt và sửa tại chỗ, hay giữ iterator), list chèn O(1) trong khi mảng phải memmove nửa mảng. List nhanh hơn ~26.000 lần. Đây là điều kiện lý tưởng mà lời hứa "O(1)" giả định — bạn đang cầm sẵn xâu chuỗi ở đúng chỗ.

Giờ tình huống C — chèn giữa như thực tế xảy ra: bạn không có sẵn con trỏ, phải tìm vị trí giữa trước. Kết quả đảo chiều hoàn toàn: mảng 20.457 ns/chèn, còn linked list 335.382 ns/chèn — chậm hơn mảng ~16 lần. Vì sao? Với mảng, "tìm" là quét tuần tự (prefetch nạp trước, gần như free) rồi memmove. Với list, "tìm" là duyệt ~N/2 node, mỗi node một cache miss ~104 ns — 50.000 bước × 104 ns ≈ 5,2 µs chỉ để tìm, và thao tác O(1) sau đó chẳng cứu nổi. Chi phí tìm nuốt chửng lợi thế thao tác.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, mỗi số lấy MIN của nhiều lần. Con số đổi theo máy; cái cần nhìn là lợi thế O(1) của list biến mất khi phải trả chi phí tìm-vị-trí đầy cache miss.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với niềm tin sách vở nguyên xi: "chèn/xóa thì linked list luôn tốt hơn vì O(1)". Tình huống A và B xác nhận, làm tôi càng tin. Rồi tình huống C phá tan: khi phải tìm vị trí trước — đúng cái xảy ra trong hầu hết code thực tế — linked list chậm hơn mảng 16 lần. "O(1)" của chèn linked list là O(1) cho riêng thao tác nối con trỏ, với điều kiện đã có con trỏ; nó im lặng về chi phí O(N) để đến được chỗ đó, và chi phí đó là cache-miss đắt gấp hàng trăm lần quét mảng.

Nhưng niềm tin ngược lại cũng sai: "chèn vào mảng thì luôn chậm". Sai — chèn ở cuối (push_back) là O(1) amortize, rẻ như không. Mảng chỉ đắt khi chèn ở đầu/giữa, và ngay cả khi đó, nếu phải tìm vị trí thì quét mảng vẫn rẻ hơn duyệt list. Cả hai định kiến đều tan khi tách "tìm" ra khỏi "thao tác" và đo cả hành trình.

Về đến code hằng ngày

Điều đầu tiên: hỏi "tôi có sẵn con trỏ/iterator tới chỗ sửa không?" trước khi chọn linked list. Nếu có (đang duyệt và sửa tại chỗ, hay giữ tham chiếu ổn định) — list chèn/xóa O(1) là thật và rất mạnh. Nếu không — bạn phải tìm trước, và duyệt list đắt hơn quét mảng nhiều; lúc đó mảng thường thắng dù phải dịch. Rất nhiều "danh sách" trong đời thực là loại thứ hai: tìm-theo-giá-trị rồi mới sửa.

Điều thứ hai: mặc định std::vector/ArrayList cho chèn ở cuối và mọi tác vụ trộn đọc-ghi. Chèn cuối là O(1) amortize, duyệt thì nhanh nhờ cache locality. Chỉ chuyển sang linked list (hay deque, hay cấu trúc chuyên biệt) khi bạn thật sự chèn/xóa nhiều ở đầu/giữa và đã cầm sẵn con trỏ tới chỗ đó, hoặc cần con trỏ tới phần tử không đổi khi cấu trúc thay đổi. Còn muốn tra cứu-rồi-sửa nhanh theo khóa, một hash map hay cây cân bằng thường đúng hơn cả hai.

Chỗ này chính là lý do các thư viện chuẩn "dìm" linked list đi mà nhiều người không để ý. Tài liệu Java khuyên dùng ArrayList gần như mọi lúc và LinkedList gần như không bao giờ — vì đúng đo C ở trên: chi phí duyệt-để-tìm giết lợi thế O(1). C++ có std::list nhưng người ta hiếm khi dùng, và std::vector là mặc định của cả cộng đồng. Rust thậm chí không có linked list "tiện dụng" trong lối viết thông thường, và tài liệu std::collections nói thẳng: hầu như luôn nên dùng Vec hoặc VecDeque thay vì LinkedList. Linked list vẫn sống ở những chỗ thật sự cần con trỏ ổn định và ghép/tách O(1) — danh sách rảnh trong allocator, LRU cache (map + list đôi), hàng đợi trong kernel — đúng những nơi bạn đã cầm sẵn node. Ngoài các chỗ đó, mảng gần như luôn thắng.

Muốn tự thấy thì dựng một mảng và một linked list, mỗi cái chứa vài chục nghìn số. Thử ba việc và bấm giờ: (1) chèn liên tục vào đầu — list bay, mảng lê lết O(N²); (2) chèn vào giữa khi bạn đã giữ con trỏ/iterator tới giữa — list vẫn thắng đậm; (3) chèn vào giữa nhưng phải tìm vị trí trước (duyệt tới node giữa) — giờ list chậm hơn hẳn, vì mỗi bước duyệt là một cache miss còn quét mảng thì prefetch nuốt gọn. Vài phút đó cho bạn thấy điều mà "linked list chèn O(1)" giấu đi: O(1) là cho thao tác, không phải cho việc đến được chỗ thao tác — và trong hầu hết code, cái phần "đến được chỗ đó" mới là phần đắt. Đo cả hành trình, đừng chỉ đo bước cuối.