List và Queue — ArrayList, LinkedList, ArrayDeque, PriorityQueue

Chọn ArrayList hay LinkedList? Hỏi 100 dev Java, 70% trả lời "LinkedList insert nhanh hơn". Viết code benchmark đo thực tế, ArrayList luôn nhanh hơn kể cả khi insert ở giữa — bất ngờ với hầu hết mọi người.

Lý do nằm ở cơ chế implementation bên dưới: ArrayList lưu trên vùng memory liền kề (contiguous array) — CPU cache load 1 cache line 64 byte = 8 element cùng lúc, iterate như đi trên đường cao tốc. LinkedList lưu mỗi element ở 1 node với 2 pointer (prev/next), node rải rác heap — iterate như nhảy qua nhiều ô không liên quan, mỗi lần nhảy CPU cache miss, đọc memory chậm gấp 100 lần cache hit.

Big-O không nói hết câu chuyện. LinkedList.add(middle) là O(1) nếu đã có iterator tại vị trí đó, nhưng tìm vị trí lại là O(n) + bị cache miss dày đặc. Thực tế chậm hơn ArrayList.add(middle) O(n) — vì ArrayList chỉ memcpy một khối memory liền kề, CPU optimize cực tốt.

Bài này giải thích tại sao mỗi implementation có đặc tính như vậy từ cách lưu trữ memory. Phạm vi: các implementation của List, Queue, Deque. Map/Set ở bài tiếp theo.

Hiểu được, bạn không bao giờ chọn sai collection nữa. Đặt hai cách lưu trữ cạnh nhau thì thấy ngay thứ mà bảng Big-O không có cột nào để ghi:

Big-O đếm số bước, không đếm giá của một bước. Toàn bộ chênh lệch thực tế nằm ở cột phải của hình.

1. Cây interface — bức tranh tổng

Iterable là gốc; Collection extends nó; List, Set, Queue extends Collection; Deque extends Queue. Các implementation gắn vào: ArrayList và LinkedList cho List, ArrayDeque và LinkedList cho Deque, PriorityQueue cho Queue.

• Iterable — gốc, duy nhất có iterator(). Cho phép for-each.
• Collection — extends Iterable, thêm add, remove, size, contains.
• List — có thứ tự + index, cho phép trùng.
• Queue — FIFO semantic (first-in-first-out).
• Deque — double-ended queue, add/remove 2 đầu. Dùng làm stack luôn.

Interface là hợp đồng. Implementation là cách thực hiện hợp đồng đó trên memory — và đây là nơi quyết định performance.

2. ArrayList — contiguous array, cache-friendly

Cấu trúc bên dưới

public class ArrayList<E> {
    private Object[] elementData;   // Mang noi bo
    private int size;               // So element thuc te (<= elementData.length)

    private static final int DEFAULT_CAPACITY = 10;
}

Chỉ 2 field chính: 1 array Java, 1 int size. Element lưu trong elementData liền kề trong memory.

Memory layout

elementData: [A][B][C][D][E][ ][ ][ ][ ][ ]
              0  1  2  3  4  5  6  7  8  9
                                size=5  capacity=10

Array Java là contiguous memory — 10 slot cạnh nhau trong heap, mỗi slot lưu reference (4 hoặc 8 byte tuỳ 32/64-bit JVM). Tổng block 10*8 = 80 byte liền kề.

get(i) — O(1) đúng nghĩa

public E get(int index) {
    return (E) elementData[index];
}

Array access = tính địa chỉ base + index * 8, fetch 1 memory location. O(1) chính xác.

Cache advantage: CPU load 64 byte (1 cache line) mỗi lần. elementData[0] đọc → CPU cache cả 8 slot đầu. Truy cập elementData[1..7] sau đó không cần đọc memory — từ cache, ~1ns. So với main memory ~100ns, nhanh 100 lần.

Đây là lý do iterate ArrayList cực nhanh — mỗi lần đọc memory load 8 element, 7 element tiếp theo từ cache.

add(e) tail — O(1) amortized

public boolean add(E e) {
    if (size == elementData.length) {
        grow();   // Cap phat array lon hon, copy
    }
    elementData[size++] = e;
    return true;
}

private void grow() {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);   // 1.5x
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Bình thường: elementData[size++] = e — O(1), 1 memory write.

Khi mảng đầy: grow() sẽ được kích hoạt để cấp phát một mảng mới có kích thước lớn hơn 1.5 lần so với mảng cũ, sau đó sử dụng Arrays.copyOf để copy toàn bộ các phần tử cũ sang mảng mới.

💎 Vì sao hệ số tăng là 1.5x (ArrayList) mà không phải 2x (Vector, HashMap)?

Tại sao các kỹ sư Java thiết kế hệ số tăng kích thước của ArrayList là 1.5 (oldCapacity + (oldCapacity >> 1)) thay vì gấp đôi 2.0 như Vector hay HashMap? Đây là cân bằng giữa lãng phí bộ nhớ và khả năng tái sử dụng vùng nhớ đã giải phóng:

1. Tái sử dụng vùng nhớ đã giải phóng (memory block reuse): Mỗi lần resize, mảng cũ bị bỏ đi và vùng nhớ của nó được giải phóng. Câu hỏi quyết định: vùng trống tích luỹ từ các mảng cũ có đủ chỗ cho mảng mới không?

   • Với k = 2: các mảng liên tiếp có kích thước C, 2C, 4C, ..., 2ⁿC. Mảng mới luôn lớn hơn tổng tất cả mảng cũ cộng lại (2ⁿ so với 1 + 2 + ... + 2ⁿ⁻¹ = 2ⁿ - 1). Vùng trống cũ không bao giờ đủ chỗ → allocator luôn phải xin vùng nhớ hoàn toàn mới, các vùng cũ thành "lỗ hổng" phân mảnh trên heap.
   • Với k = 1.5: tổng quát, khi growth factor k nhỏ hơn tỷ lệ vàng φ ≈ 1.618 (điều kiện k² ≤ k + 1 — block mới fit vào không gian của các block giải phóng ngay trước đó), thì chỉ sau vài lần resize, vùng nhớ đã giải phóng đủ lớn để chứa mảng mới. Vì 1.5 nhỏ hơn 1.618, allocator có cơ hội cấp phát mảng mới ngay trên vùng cũ — giảm phân mảnh, dùng heap hiệu quả hơn.

2. Cân bằng hiệu năng (Trade-off Sweet Spot):

   • Lãng phí bộ nhớ (Internal Fragmentation): Nếu chọn k quá lớn (ví dụ k = 2), ở trạng thái tệ nhất ngay sau khi resize, chúng ta có thể lãng phí tới 50% không gian mảng (khi chỉ thêm 1 phần tử vượt ngưỡng). Với k = 1.5, tỷ lệ lãng phí tối đa giảm xuống chỉ còn khoảng ~33%.
   • Số lần cấp phát lại (Allocation Overhead): Nếu chọn k quá nhỏ (ví dụ 1.1 hay 1.2), mảng sẽ phải resize liên tục, tốn chi phí CPU để copy dữ liệu và tăng áp lực dọn rác cực nặng lên GC. Hệ số 1.5 giữ cho chi phí thêm phần tử luôn là O(1) amortized cực kỳ ổn định.
   • Tối ưu hóa ở mức Bitwise: Phép toán oldCapacity + (oldCapacity >> 1) sử dụng toán tử dịch bit phải >> 1 (chia đôi) được thực hiện trực tiếp trên thanh ghi CPU chỉ trong 1 chu kỳ xung nhịp (clock cycle), tránh được lệnh chia số nguyên DIV vô cùng đắt đỏ ở mức phần cứng.

Mẹo tối ưu: Nếu biết trước số lượng phần tử tối đa, hãy luôn khởi tạo new ArrayList<>(expectedSize) hoặc gọi list.ensureCapacity(n) để triệt tiêu hoàn toàn quá trình resize mảng, đưa chi phí thêm phần tử về O(1) tuyệt đối.

add(i, e) giữa — O(n) nhưng nhanh thực tế

public void add(int index, E element) {
    if (size == elementData.length) grow();
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

Dịch chuyển toàn bộ các phần tử sang phải 1 slot thông qua System.arraycopy.

⚡ Sức mạnh từ JVM Intrinsic: Tại sao System.arraycopy lại nhanh kinh ngạc?

Dù về mặt lý thuyết Big-O, việc dịch chuyển mảng là một thao tác O(n), nhưng thực tế benchmark cho thấy nó chạy nhanh đến mức không tưởng, thường đánh bại hoàn toàn việc chèn phần tử của LinkedList ở hầu hết mọi vị trí. Bí mật nằm ở chỗ:

• JVM_ArrayCopy Intrinsic: System.arraycopy không phải là một hàm Java thông thường, cũng không hoạt động thông qua cơ chế JNI (Java Native Interface) truyền thống vốn đi kèm overhead chuyển đổi ngữ cảnh stack rất lớn. Nó là một JIT Intrinsic method được định nghĩa đặc biệt trong HotSpot JVM.
• Ánh xạ trực tiếp sang CPU Assembly: Khi mã nguồn được biên dịch JIT (C2 compiler), HotSpot JVM sẽ nhận diện signature này và thay thế (inline) toàn bộ lệnh gọi hàm bằng các đoạn mã máy (assembly) tối ưu nhất của nền tảng phần cứng hiện tại. Lệnh này ánh xạ trực tiếp tới các hàm copy bộ nhớ cực mạnh ở cấp độ hệ thống như memcpy hoặc memmove.
• Vector hóa bằng phần cứng: CPU hiện đại có các tập lệnh vectorized SIMD (như AVX-512, AVX2, SSE) có khả năng dịch chuyển hàng chục byte dữ liệu cùng một lúc trên thanh ghi. Trình JIT compiler sẽ sinh mã tận dụng các instruction này, kết hợp với các chỉ thị phần cứng siêu tối ưu như REP MOVSB / REP MOVSD trên kiến trúc x86-64 để copy và dịch chuyển hàng GB dữ liệu trên một giây.

Đây chính là cột trái của sơ đồ đầu bài: cả khối liền kề đi qua prefetcher một lần, không sinh node object mới nên cũng không tạo rác cho GC.

Pitfall ArrayList

• Tốn memory khi remove nhiều: size giảm nhưng elementData.length không shrink. Phải gọi trimToSize() thủ công để giải phóng.
• Resize 1.5x có thể waste ~33% memory trung bình. new ArrayList<>(knownSize) giúp.

3. LinkedList — doubly-linked list, memory scatter

Cấu trúc bên dưới

public class LinkedList<E> {
    Node<E> first;   // head
    Node<E> last;    // tail
    int size;

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
}

Mỗi element wrap trong 1 Node với 3 field: value, next pointer, prev pointer.

Memory layout

Heap (dia chi ngau nhien, khong lien ke):
  Node A @ 0x1000: {item=A, next=0x3A00, prev=null}
  Node B @ 0x3A00: {item=B, next=0x7F00, prev=0x1000}
  Node C @ 0x7F00: {item=C, next=null,   prev=0x3A00}

Mỗi node cấp phát qua new — OS/JVM đặt ở địa chỉ bất kỳ có sẵn trong heap. Rải rác (scattered), không cạnh nhau.

Thêm: mỗi node có object header (12-16 byte trên 64-bit JVM) + 3 field × 8 byte = ~40 byte / element. So với ArrayList 8 byte / element. Overhead 5x memory.

get(i) — O(n)

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) x = x.next;   // Walk tu head
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) x = x.prev;   // Walk tu tail
        return x;
    }
}

Phải duyệt linked list từ head (hoặc tail, tuỳ gần hơn) đến index. O(n/2) = O(n).

Cache nightmare: mỗi x.next fetch node ở địa chỉ khác nhau — CPU cache miss mỗi lần. 10k element = 10k cache miss × 100ns = 1 millisecond chỉ để duyệt list. ArrayList.get(9999) = 1 memory access = 100ns = 10000x nhanh hơn.

add(e) tail — O(1) thật

Tạo node mới, trỏ last.next → node mới, update last. O(1). Không như ArrayList không bao giờ cần resize/copy.

Nhưng: tạo object node mới — tốn memory allocation + GC pressure. Add 1M element = 1M node object mới = 40MB heap + GC work. ArrayList 1M = 1 array 8MB, không GC pressure.

add(0, e) head — O(1) thật

LinkedList add đầu list O(1) — chỉ update first.prev và tạo node mới. ArrayList add(0, e) phải shift toàn bộ array O(n).

Đây là tình huống duy nhất LinkedList thắng ArrayList thực tế. Nhưng cần queue/deque → ArrayDeque thắng cả hai.

Bảng so sánh

Josh Bloch (tác giả Collections framework) từng tự nhận rằng chính ông viết LinkedList nhưng chưa bao giờ dùng nó — nguyên văn: "Does anyone actually use LinkedList? I wrote it, and I never use it".

Kết luận

• ArrayList — mặc định 99% trường hợp.
• LinkedList — gần như không nên dùng. Cần queue/deque → ArrayDeque.

4. ArrayDeque — circular buffer

Cấu trúc

public class ArrayDeque<E> {
    Object[] elements;   // circular array
    int head;            // index element dau
    int tail;            // index slot trong tiep theo
}

Array với 2 pointer head/tail di chuyển vòng tròn (circular). Add/remove 2 đầu chỉ di chuyển pointer — O(1) không cần shift.

Memory layout

elements: [ ][ ][C][D][E][A][B][ ]
                 tail=2   head=5
               (wrap around)

Head = 5, tail = 2 (wrap around). Element theo thứ tự: A (5), B (6), [wrap], C (0), D (1), E (2).

Add tail: elements[tail] = e; tail = (tail + 1) % length; — O(1). Add head: head = (head - 1 + length) % length; elements[head] = e; — O(1).

Bảng so sánh stack/queue

Rule: cần stack/queue không concurrent → ArrayDeque luôn thắng. Stack class Java legacy (Java 1.0) — không dùng vì synchronized bất cứ thứ gì không cần thiết.

Dùng làm stack

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();   // 3 (LIFO)

Dùng làm queue

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.poll();   // 1 (FIFO)

5. PriorityQueue — binary heap

Cấu trúc

Binary heap thực tế được biểu diễn và lưu trữ phẳng trong một array tuần tự. Để tìm mối quan hệ cha-con giữa các node, ta không cần dùng con trỏ pointer phức tạp mà tính toán trực tiếp bằng chỉ số index:

• Node cha ở vị trí index i sẽ có:
  • Node con trái (Left Child) tại index: 2i + 1
  • Node con phải (Right Child) tại index: 2i + 2
• Ngược lại, một node con bất kỳ ở index c luôn tìm được node cha của nó tại index: (c - 1) / 2 (phép chia số nguyên tự động làm tròn xuống).

Dưới đây là sơ đồ ASCII minh họa mối liên kết cha-con tương ứng với mảng heap [1, 3, 2, 5, 4, 7, 6]:

Mảng lưu trữ heap nhị phân (Binary Heap Array):
+-------+-------+-------+-------+-------+-------+-------+
|   1   |   3   |   2   |   5   |   4   |   7   |   6   |
+-------+-------+-------+-------+-------+-------+-------+
 Index 0 Index 1 Index 2 Index 3 Index 4 Index 5 Index 6


Sơ đồ cây nhị phân ASCII tương ứng (Visualizing Index & Parent-Child Relations):

                         Index 0
                         [  1  ] (Root)
                       /         \
             Index 1                 Index 2
             [  3  ]                 [  2  ]
            /       \               /       \
       Index 3     Index 4     Index 5     Index 6
       [  5  ]     [  4  ]     [  7  ]     [  6  ]

Mối quan hệ cha-con từ trực quan đến toán học:

• Node giá trị 3 ở Index i = 1:
  • Con trái: 2 * 1 + 1 = 3 -> Trỏ tới Index 3 (giá trị 5).
  • Con phải: 2 * 1 + 2 = 4 -> Trỏ tới Index 4 (giá trị 4).
  • Cha của nó: (1 - 1) / 2 = 0 -> Trỏ tới Index 0 (giá trị 1).
• Node giá trị 7 ở Index c = 5:
  • Cha của nó: (5 - 1) / 2 = 2 -> Trỏ tới Index 2 (giá trị 2).

Tính chất cốt lõi của Min-Heap: Giá trị của node cha luôn nhỏ hơn hoặc bằng giá trị của các node con (array[parent] <= array[child]), đảm bảo phần tử nhỏ nhất luôn nằm ở Root (array[0]).

Operation

• peek() — root = array[0]. O(1).
• offer(e) — thêm vào array[size], sau đó sift-up: so với parent, swap nếu cần. O(log n).
• poll() — lấy root, swap root với last element, giảm size, sift-down: so với smaller child, swap nếu cần. O(log n).

Use case

• Top-K: maintain heap size k, push mọi element, pop khi vượt k.
• Dijkstra: lấy node chưa visit có distance nhỏ nhất.
• Scheduling: task có priority, luôn lấy task priority cao nhất.
• Merge K sorted list: push head mỗi list, pop min, push next.

Mặc định min-heap. Max-heap: pass Comparator.reverseOrder().

6. Pitfall tổng hợp

❌ Nhầm 1: Dùng LinkedList vì "đọc trên internet nói insert nhanh".

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10_000; i++) list.add(i);
for (int i = 0; i < list.size(); i++) sum += list.get(i);   // O(n^2) nightmare

✅ ArrayList 99% trường hợp.

❌ Nhầm 2: Stack legacy thay ArrayDeque.

Stack<Integer> stack = new Stack<>();   // Synchronized, cham, extends Vector

✅ Deque<Integer> stack = new ArrayDeque<>();

❌ Nhầm 3: Thêm/remove ArrayList ở đầu liên tục.

for (int i = 0; i < 100_000; i++) list.add(0, i);   // O(n^2)

✅ ArrayDeque cho add đầu O(1).

❌ Nhầm 4: Modify collection đang iterate → ConcurrentModificationException.

for (String s : list) { if (bad(s)) list.remove(s); }

✅ list.removeIf(...) hoặc Iterator.remove().

7. 📚 Deep Dive Oracle

Liên kết khoá học khác

• Khoá Thuật toán — bài 01.1 Array vs ArrayList — primitive array vs ArrayList performance, kích thước memory và khi nào chọn loại nào.
• Khoá Java Internals — ArrayList.grow() — case study sâu về ArrayList.grow() tăng 1.5x trong OpenJDK source.
• Khoá Thuật toán — bài 2.2 Linked List — vì sao LinkedList chậm hơn ArrayList dù cùng O(1) insert (cache locality và memory scatter).

8. Tóm tắt

• ArrayList: contiguous array, cache-friendly, O(1) get, O(1) amortized add tail. Mặc định 99%.
• LinkedList: doubly-linked node scatter, O(n) get với cache miss dày. Gần như không nên dùng.
• ArrayDeque: circular buffer, O(1) 2 đầu, best cho stack/queue/deque.
• PriorityQueue: binary heap array, O(log n) offer/poll, O(1) peek.
• Big-O không nói hết — cache locality + allocation pattern quyết định thực tế.
• ArrayList thường thắng LinkedList cả ở case Big-O ngang bằng — vì memcpy liền kề + không GC pressure.
• ArrayDeque thay Stack legacy (synchronized vô ích) và LinkedList cho queue/deque.

9. Tự kiểm tra

Bài tiếp theo: Map và Set — HashMap, TreeMap, HashSet