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 page = 64 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.

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

flowchart TD
    Iterable --> Collection
    Collection --> List
    Collection --> Set
    Collection --> Queue
    Queue --> Deque

    List -.-> ArrayList
    List -.-> LinkedList
    Deque -.-> ArrayDeque
    Deque -.-> LinkedList
    Queue -.-> PriorityQueue

• 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 array đầy: grow() cấp array mới 1.5x capacity, Arrays.copyOf copy toàn bộ O(n). Nhưng op này chỉ xảy ra khi vượt capacity.

Amortized analysis: với n add lần, tổng resize cost ≈ 2n. Chia đều cho n add → trung bình O(1) amortized.

Mẹo tối ưu: biết trước size → new ArrayList<>(expectedSize) hoặc list.ensureCapacity(n) → tránh resize, add luôn O(1).

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++;
}

Shift element sang phải 1 slot qua System.arraycopy — native method, dùng memcpy OS-level. Với array primitive/reference liền kề, memcpy cực nhanh — CPU có instruction REP MOVSB copy hàng GB/s.

O(n) về lý thuyết, nhưng thực tế benchmark nhanh hơn LinkedList.add(middle) vì:

• Memcpy 1 block liền kề — CPU cực tối ưu.
• Không tạo node object (GC friendly).
• Cache line optimal — prefetch automatic.

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 (thiết kế Collections): "I don't think anyone has ever used LinkedList correctly in 20+ years of Java".

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 lưu trong array — node tại index i có child tại 2i+1 và 2i+2, parent tại (i-1)/2.

array:    [1, 3, 2, 5, 4, 7, 6]

tree view (min-heap):
              1
            /   \
           3     2
          / \   / \
         5   4 7   6

Parent luon <= children (min-heap property)

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

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

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10_000; i++) list.add(i);

long sum = 0;
for (int i = 0; i < list.size(); i++) {
  sum += list.get(i);
}

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