arraylist vs linkedlist

Trong hầu hết các giáo trình Khoa học Máy tính đại học và các câu hỏi phỏng vấn cơ bản, chúng ta đều được dạy một kết luận kinh điển:

• ArrayList: Dùng mảng động, truy cập ngẫu nhiên cực nhanh O(1), nhưng chèn/xóa ở giữa rất chậm O(N) vì phải dịch chuyển 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/xóa cực nhanh O(1) chỉ bằng cách đổi con trỏ.

Từ kết luận lý thuyết đó, nhiều lập trình viên đưa ra quyết định: "Nếu hệ thống cần chèn/xóa phần tử thường xuyên, hãy dùng LinkedList".

Tuy nhiên, trong kỹ nghệ phần mềm hiện đại chạy trên kiến trúc phần cứng máy tính thực tế, đây là một sai lầm chết người. Trên thực tế tại các tập đoàn công nghệ lớn, LinkedList gần như bị cấm sử dụng hoàn toàn. Ngay cả chính tác giả viết ra java.util.LinkedList trong Java SDK — Joshua Bloch — cũng từng chia sẻ hài hước trên Twitter: "Tôi là người viết ra LinkedList, và tôi không bao giờ dùng nó".

Bài viết này sẽ phân tích nguyên nhân gốc rễ dưới góc độ kiến trúc phần cứng CPU, cơ chế bộ nhớ đệm Cache Line và Garbage Collection.

# phần cứng cpu cache line & spatial locality

Khoảng cách về tốc độ giữa CPU và RAM vật lý là một vực thẳm:

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

Để khắc phục độ trễ này, kiến trúc vi xử lý hiện đại không bao giờ đọc từng byte đơn lẻ từ RAM. Mỗi khi có lệnh đọc bộ nhớ, CPU luôn tải một khối liên tục 64 bytes vào bộ nhớ đệm, được gọi là một Cache Line.

# tại sao arrayList chiến thắng khi duyệt dữ liệu

• Mảng nội bộ của ArrayList (Object[] elementData) là một khối bộ nhớ liền mạch (contiguous memory block).
• Khi CPU nạp phần tử index 0, cơ chế phần cứng Hardware Prefetcher sẽ tự động nạp luôn các phần tử từ index 1 đến index 7 vào Cache Line. Khi vòng lặp bước sang phần tử kế tiếp, dữ liệu đã nằm sẵn trong L1 Cache với độ trễ gần bằng 0!
• Trong khi đó, mỗi node trong LinkedList là một đối tượng độc lập được cấp phát ngẫu nhiên ở các địa chỉ khác nhau trên Heap. Khi duyệt qua LinkedList, CPU phải thực hiện "đuổi bắt con trỏ" (Pointer Chasing). Mỗi bước nhảy sang node kế tiếp hầu như chắc chắn gây ra một Cache Miss, buộc CPU phải dừng hoạt động (Stall) chờ 100ns để kéo dữ liệu từ RAM vật lý về.

# lãng phí bộ nhớ và node overhead

Xét một danh sách chứa 1,000,000 số nguyên (Integers) trên máy ảo 64-bit (bật Compressed OOPs - con trỏ nén 32-bit):

# chi phí bộ nhớ trong arrayList

• 1 đối tượng ArrayList: Header (12B) + size (4B) + array ref (4B) + padding = 24 bytes.
• 1 đối tượng mảng Object[1000000]: Header mảng (16B) + 1,000,000 x 4B ≈ 4 MB.
• Tổng cộng: ~4 MB (Chỉ có duy nhất 2 đối tượng trên Heap: instance List và instance mảng).

# chi phí bộ nhớ trong linkedList

Mỗi phần tử được bọc trong một 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 trường tham chiếu (item, next, prev): 3 x 4 = 12 bytes.
• Padding canh chỉnh bộ nhớ (bội số của 8 bytes): 8 bytes.
• Tổng chi phí 1 Node: 12 + 12 + 8 = 32 bytes!

Với 1,000,000 phần tử, LinkedList tiêu tốn:

1,000,000 x 32 bytes ≈ 32 MB

Gấp 8 LẦN so với ArrayList!

# áp lực lên garbage collector

• ArrayList: GC chỉ cần theo dõi và đánh dấu (mark-and-sweep) đúng 2 đối tượng.
• LinkedList: GC phải quản lý và quét qua 1,000,001 đối tượng phân mảnh! Điều này làm bùng nổ thời gian quét Heap của GC, gây ra hiện tượng giật lag Stop-The-World kéo dài trên các ứng dụng chịu tải cao.

# phản bác định kiến chèn xóa nhanh hơn

Lập luận kinh điển: "Chèn vào giữa LinkedList chỉ tốn O(1) thao tác đổi con trỏ, trong khi ArrayList tốn O(N) dịch chuyển mảng".

# thực tế đo lường hiệu năng

Để 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 danh sách đến vị trí k. Việc duyệt O(N) trong LinkedList bị chậm đi hàng chục lần vì Cache Miss liên tục!

Trong khi đó, ArrayList dịch chuyển các phần tử mảng bằng lệnh native:

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

Phương thức System.arraycopy() được HotSpot JIT biên dịch thành các lệnh SIMD Vectorized Memory Move (memmove) của CPU. Nó copy hàng loạt Cache Lines ở tốc độ bus phần cứng (hàng chục Gigabytes mỗi giây).

# giải pháp thay thế tối thượng: arrayDeque

Nếu nghiệp vụ thực sự yêu cầu cấu trúc dữ liệu kiểu Hàng đợi (Queue), Ngăn xếp (Stack), hoặc Thao tác chèn/xóa ở hai đầu (FIFO / LIFO), tuyệt đối không dùng LinkedList. Hãy sử dụng ArrayDeque!

ArrayDeque được xây dựng trên mô hình Mảng Vòng (Circular Array Buffer):

# tại sao arrayDeque vượt trội hơn linkedList

1. Zero Node Allocation: Hoàn toàn không tạo ra bất kỳ đối tượng Node trung gian nào; không gây áp lực rác lên Garbage Collector.
2. Cache Locality: Dữ liệu lưu trong mảng liền kề, tận dụng tối đa L1/L2 Cache của CPU.
3. Hiệu năng: Nhanh hơn LinkedList từ 2 đến 5 lần trong mọi thao tác push, pop, poll, offer ở hai đầu danh sách.

# tối ưu hóa arrayList trong thực tế

Mặc dù ArrayList vượt trội, nó vẫn có một điểm nghẽn: Khi mảng bị đầy, nó phải cấp phát một mảng mới lớn gấp 1.5 lần và copy toàn bộ dữ liệu cũ sang:

newCapacity = oldCapacity + (oldCapacity >> 1)

# luôn chỉ định initialCapacity

Nếu bạn biết trước số lượng phần tử xấp xỉ (ví dụ khi query database hoặc parse JSON), hãy chỉ định kích thước ban đầu để loại bỏ hoàn toàn các lần resize mảng:

// 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);

# ma trận so sánh toàn diện

# kết luận

Sự khác biệt giữa một sinh viên mới ra trường và một Kỹ sư Hệ thống nằm ở chỗ: Sinh viên nhìn cấu trúc dữ liệu qua công thức Big-O trên giấy, còn Kỹ sư Hệ thống nhìn cấu trúc dữ liệu qua đường truyền bus phần cứng, chu kỳ xung nhịp CPU, Cache Line và áp lực lên bộ nhớ ảo của hệ điều hành.

Trong thế giới thực của Java hiện đại:

• Mặc định luôn luôn chọn ArrayList.
• Cần hàng đợi Queue, Stack, hay Deque? Hãy chọn ArrayDeque.
• Hãy để LinkedList yên nghỉ trong sách giáo khoa lịch sử.

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 😎 👍🏻 🚀 🔥.