Đâ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. 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.
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ột lần tôi đo hớ: "linked list luôn thắng khi chèn/xóa"
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.
Còn 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. Bài học đo lường: "chèn/xóa O(1)" của linked list chỉ đúng khi bạn ĐÃ CÓ con trỏ tới chỗ sửa; nếu phải tìm vị trí trước, chi phí duyệt (O(N) và cache miss mỗi bước) lấn át, khiến list chậm hơn mảng nhiều lần dù mảng phải dịch phần tử — bố cục bộ nhớ lại thắng Big-O. Nếu tôi tin "list luôn thắng chèn", tôi đã chọn linked list cho một danh sách hay chèn-giữa-theo-giá-trị và tự làm chậm chương trình 16 lần, trong khi mảng liền mạch đơn giản hơn lại nhanh hơn.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: Big-O của một thao tác chỉ có nghĩa cùng với điều kiện của nó — đọc kỹ chữ "nếu". Con số mang theo: chèn/xóa linked list O(1) CHỈ khi đã có con trỏ tới chỗ sửa: chèn đầu list 0,2 ns vs mảng 13.996 ns (O(N²)) = list nhanh ~70.000x; chèn giữa đã-cầm-con-trỏ list 0,3 ns vs mảng memmove 7.770 ns. NHƯNG chèn giữa THỰC TẾ (phải tìm vị trí trước): list 335.382 ns/chèn (duyệt tìm = cache miss mỗi bước) vs mảng 20.457 ns (quét prefetch + memmove) = list CHẬM ~16x. Chi phí TÌM lấn át chi phí thao tác; mảng chèn CUỐI là O(1) amortize. Chọn theo thao tác chính + bạn có sẵn con trỏ hay không. "O(1)" không phải lời hứa vô điều kiện — nó có một cái nếu, và cái nếu đó thường không đúng.
Thử ba mươi giây
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. Ba mươi giây đó 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.
