arraylist vs linkedlist

Hồi học đại học hay lúc đi phỏng vấn, chắc ai cũng từng được dạy một kết luận quen thuộc:

• ArrayList: dùng mảng động, truy cập ngẫu nhiên rất nhanh O(1), nhưng chèn/xoá ở giữa chậm O(N) vì phải dời các phần tử.
• LinkedList: dùng danh sách liên kết kép (Doubly Linked List), truy cập ngẫu nhiên chậm O(N), nhưng chèn/xoá nhanh O(1) vì chỉ đổi con trỏ.

Từ đó nhiều người chốt luôn: "Hệ thống cần chèn/xoá phần tử nhiều thì dùng LinkedList".

Có điều trên phần cứng thật, kết luận này sai khá nặng. Nhiều team coi việc dùng LinkedList trong code mới gần như một code smell. Đến cả Joshua Bloch, người viết ra java.util.LinkedList trong Java SDK, cũng từng đùa trên Twitter (2015): "Có ai thật sự dùng LinkedList không? Tôi viết ra nó, và tôi chẳng bao giờ dùng".

Mình sẽ giải thích vì sao, nhìn từ góc độ phần cứng CPU, Cache Line và Garbage Collection.

# cpu cache line & spatial locality

Tốc độ của CPU và RAM chênh nhau cực xa:

• Đọc dữ liệu trong L1 CPU Cache: ~1 ns (~4 clock cycles).
• Đọc dữ liệu trong L2 CPU Cache: ~3 - 4 ns (~12 clock cycles).
• Đọc dữ liệu trong RAM chính (Main Memory): ~60 - 100 ns (~200 clock cycles), chậm hơn cả trăm lần!

Để đỡ độ trễ này, CPU hiện đại không bao giờ đọc lẻ từng byte từ RAM. Mỗi lần đọc bộ nhớ, CPU luôn kéo về nguyên một khối liên tục vào cache, gọi là một Cache Line: 64 bytes trên hầu hết chip x86 và ARM, 128 bytes trên Apple M-series.

# vì sao arrayList thắng khi duyệt dữ liệu

• Mảng bên trong ArrayList (Object[] elementData) là một khối bộ nhớ liền nhau (contiguous memory block).
• Khi CPU nạp phần tử index 0, cả Cache Line 64 bytes chứa luôn reference của index 0 đến index 15 (mỗi ref 4 bytes khi bật Compressed OOPs). Thêm nữa, Hardware Prefetcher thấy CPU đọc tuần tự nên kéo trước các Cache Line kế tiếp. Vòng lặp bước sang phần tử sau thì dữ liệu đã nằm sẵn trong cache, gần như không mất thời gian chờ.
• Có một điểm hay bị quên: ArrayList<Integer> chỉ giữ reference, còn object Integer thì vẫn nằm riêng trên Heap. Mảng ref thì liền nhau, nhưng muốn đọc giá trị vẫn phải nhảy sang object Integer. Đây là lý do mảng primitive int[] còn nhanh hơn ArrayList<Integer> một bậc nữa.
• Còn mỗi node của LinkedList là một object riêng, nằm lung tung ở các địa chỉ khác nhau trên Heap. Duyệt LinkedList là CPU phải "đuổi theo con trỏ" (Pointer Chasing): chưa đọc xong node này thì chưa biết địa chỉ node sau, nên prefetcher khó đoán và CPU không gửi được nhiều lệnh đọc song song. Khi các node đã nằm rải rác thì gần như bước nhảy nào cũng dính Cache Miss, CPU phải đứng (stall) chờ cỡ 100ns để kéo dữ liệu từ RAM về.
• Nói cho công bằng: một LinkedList vừa tạo bằng add() liên tục thì các node thường được cấp phát sát nhau trong TLAB (vùng cấp phát riêng của mỗi thread), nên duyệt cũng không tệ lắm. Mình đo nhanh trên Java 21 với 1 triệu phần tử vừa tạo, duyệt LinkedList chỉ chậm hơn ArrayList khoảng 1,5 - 2 lần. Chênh lệch mới lớn dần khi list sống lâu, bị chèn xoá nhiều và node bị xáo trộn khắp Heap.

# hao bộ nhớ vì node overhead

Lấy ví dụ một danh sách 1,000,000 số nguyên (Integers) trên JVM 64-bit (bật Compressed OOPs, con trỏ nén 32-bit). Phần dưới chỉ tính chi phí của chính cấu trúc list; bản thân 1 triệu object Integer (16 bytes mỗi cái, khoảng 16 MB) thì list nào cũng phải tốn như nhau:

# arrayList tốn bao nhiêu bộ nhớ

• 1 object ArrayList: Header (12B) + modCount (4B, kế thừa từ AbstractList) + size (4B) + array ref (4B) = 24 bytes.
• 1 object mảng Object[1000000]: Header mảng (16B) + 1,000,000 x 4B ≈ 4 MB.
• Tổng: ~4 MB (cấu trúc list chỉ gồm đúng 2 object: instance List và instance mảng). Nếu list tự lớn dần chứ không truyền capacity, mảng có thể dư tới khoảng 50% chỗ trống.

# linkedList tốn bao nhiêu bộ nhớ

Mỗi phần tử được bọc trong class nội bộ Node<E>:

private static class Node<E> {
    E item;          // 4 bytes (Compressed OOP)
    Node<E> next;    // 4 bytes
    Node<E> prev;    // 4 bytes
}

Chi phí cho MỖI NODE:

• Object Header: 12 bytes.
• 3 field tham chiếu (item, next, prev): 3 x 4 = 12 bytes.
• 12 + 12 = 24, vừa tròn bội số của 8 nên không cần padding.
• Tổng 1 Node: 24 bytes (kiểm bằng JOL trên Java 21 cũng ra đúng 24).

Với 1,000,000 phần tử, LinkedList ăn hết:

1,000,000 x 24 bytes ≈ 24 MB

Gấp 6 lần ArrayList. Tính cả 16 MB của các object Integer thì là khoảng 40 MB so với 20 MB, vẫn gấp đôi.

(Từ Java 25 có thể bật Compact Object Headers bằng -XX:+UseCompactObjectHeaders (JEP 519), header còn 8 bytes, mỗi Node xuống 16 bytes. Mặc định vẫn tắt.)

# gánh nặng cho garbage collector

• ArrayList: phần cấu trúc chỉ có 2 object cho GC đánh dấu (cộng 1 triệu object Integer mà list nào cũng có).
• LinkedList: thêm 1,000,000 object Node nữa, tức số object GC phải lần theo tăng gần gấp đôi. Mỗi lần thêm phần tử lại sinh thêm một object, nên GC chạy thường hơn; list sống lâu thì node bị đẩy lên Old Gen, khi GC phải quét chúng thì pause dài hơn.

# chèn xoá nhanh hơn? không hẳn

Lập luận quen thuộc: "Chèn vào giữa LinkedList chỉ tốn O(1) để đổi con trỏ, còn ArrayList tốn O(N) để dời mảng".

# đo thật thì sao

Muốn chèn vào vị trí k trong LinkedList:

Total Time = Traverse to index k (O(N)) + Pointer Swap (O(1))

Bạn phải duyệt từ đầu (hoặc từ cuối, LinkedList chọn đầu gần hơn) tới vị trí k. Mà duyệt O(N) trên LinkedList lại là kiểu đuổi theo con trỏ, chậm hơn hẳn so với copy một khối bộ nhớ liền nhau.

Trong khi đó, ArrayList dời phần tử bằng lệnh native:

System.arraycopy(elementData, index, elementData, index + 1, size - index);

System.arraycopy() là một intrinsic của HotSpot: JIT thay lời gọi bằng đoạn copy bộ nhớ viết sẵn, dùng lệnh SIMD (vector) của CPU, kiểu memmove, copy liền một mạch nhiều Cache Line với băng thông cỡ hàng chục GB mỗi giây.

# nên dùng gì thay: arrayDeque

Nếu bài toán thật sự cần hàng đợi (Queue), ngăn xếp (Stack) hay chèn/xoá ở hai đầu (FIFO / LIFO), đừng dùng LinkedList. Dùng ArrayDeque!

ArrayDeque dựng trên mảng vòng (Circular Array Buffer):

# vì sao arrayDeque hơn linkedList

Trong ArrayDeque của JDK, head trỏ vào phần tử đầu, còn tail trỏ vào ô trống ngay sau phần tử cuối. Hai con trỏ chạy vòng quanh mảng (hết mảng thì quay về index 0); mảng đầy thì cấp phát mảng lớn hơn rồi copy sang, nên thêm phần tử là O(1) khấu hao (amortized), giống ArrayList.

1. Không tạo Node: không sinh ra object Node trung gian nào, GC không phải dọn thêm rác.
2. Cache Locality: dữ liệu nằm trong mảng liền nhau, tận dụng tốt L1/L2 Cache của CPU.
3. Hiệu năng: các thao tác push, pop, poll, offer ở hai đầu thường nhanh hơn LinkedList. Bài đo nhanh của mình (1 triệu addLast rồi pollFirst, Java 21) cho ArrayDeque nhanh hơn khoảng 1,5 - 2 lần; chênh lệch thật tuỳ kích thước và áp lực GC.

Hai chỗ cần để ý khi đổi từ LinkedList sang: ArrayDeque không nhận phần tử null (ném NullPointerException), và nó không thread-safe. Cần hàng đợi cho nhiều thread thì dùng ArrayBlockingQueue, LinkedBlockingQueue hoặc ConcurrentLinkedDeque.

# tối ưu arrayList khi dùng thật

ArrayList ngon nhưng vẫn có một chỗ nghẽn: mảng đầy thì nó phải cấp phát mảng mới lớn gấp 1.5 lần rồi copy hết dữ liệu cũ sang:

newCapacity = oldCapacity + (oldCapacity >> 1)

# luôn truyền initialCapacity

Nếu biết trước số phần tử áng chừng (ví dụ lúc query database hay parse JSON), truyền luôn kích thước ban đầu để khỏi phải resize mảng lần nào:

// KÉM TỐI ƯU: Mảng khởi tạo mặc định capacity = 10.
// Khi thêm 10,000 phần tử, mảng phải resize và copy gần 20 lần!
List<TransactionDto> list = new ArrayList<>();
 
// TỐI ƯU CHUẨN KỸ SƯ: Cấp phát một lần duy nhất, 0 lần resize!
List<TransactionDto> optimizedList = new ArrayList<>(10_000);

# bảng so sánh

# kết luận

Sinh viên mới ra trường hay nhìn cấu trúc dữ liệu qua công thức Big-O trên giấy. Người làm hệ thống lâu năm thì nhìn thêm cả bus phần cứng, chu kỳ xung nhịp CPU, Cache Line và áp lực lên bộ nhớ.

Với Java ngày nay:

• Mặc định cứ chọn ArrayList.
• Cần Queue, Stack hay Deque? Chọn ArrayDeque.
• Còn LinkedList thì để yên trong sách giáo khoa.

Chỉ là những ghi chép cá nhân với hy vọng mang lại chút giá trị. Nếu thấy hữu ích, đừng ngại chia sẻ cho bạn bè & đồng nghiệp nhé!

Happy coding 😎 👍🏻 🚀 🔥.