ArrayList, LinkedList, ArrayDeque bên trong: vì sao import 1 triệu đơn lại chậm

Hay. Bài 1.5 cho bảng chi phí; bài này mở code bên trong để thấy vì sao có con số đó, và thêm ArrayDeque, thứ thay thế đúng cho Stack và LinkedList khi làm queue.

1. Bài toán: job import đơn hàng từ file CSV

List<Order> orders = new LinkedList<>();              // "thêm nhiều thì LinkedList cho nhanh"
for (String line : Files.readAllLines(csv)) orders.add(parse(line));

for (int i = 0; i < orders.size(); i++) {
    validate(orders.get(i));                              // ❌ 1 triệu dòng: treo cả chục phút
}

2. Vấn đề

• LinkedList.get(i) phải đi từ đầu (hoặc cuối, chọn bên gần hơn) tới node thứ i: O(n). Trong vòng for → O(n²).
• Kể cả duyệt bằng iterator, mỗi node là một object riêng nằm rải rác trên heap → CPU liên tục cache miss.

3. Giải pháp: hiểu cấu trúc bên trong

• ArrayList: bọc một mảng Object[] elementData + size. Hết chỗ thì tạo mảng mới lớn gấp 1.5 lần và System.arraycopy sang.
• LinkedList: danh sách liên kết đôi, mỗi phần tử là Node{item, prev, next}; giữ first, last.
• ArrayDeque: mảng vòng (circular buffer) với hai chỉ số head, tail; thêm/bớt ở cả hai đầu O(1), không dịch mảng.

4. Code từng bước

Bước 1: Xem ArrayList grow (rút gọn từ JDK 17)

// new ArrayList<>() → elementData = {} (rỗng), lần add đầu mới cấp 10 ô
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);      // ×1.5
    return elementData = Arrays.copyOf(elementData, Math.max(newCapacity, minCapacity));
}

public void add(int index, E e) {                              // chèn giữa
    ...
    System.arraycopy(elementData, index, elementData, index + 1, size - index);  // dịch phải
    elementData[index] = e;
}

Bước 2: Sửa job import

List<String> lines = Files.readAllLines(csv);
List<Order> orders = new ArrayList<>(lines.size());      // cấp đủ chỗ, không grow lần nào
for (String line : lines) orders.add(parse(line));
for (Order o : orders) validate(o);                        // O(n), duyệt mảng liền mạch

Bước 3: Queue và stack bằng ArrayDeque

// Queue FIFO: đơn chờ gửi email
Deque<Order> queue = new ArrayDeque<>();
queue.offerLast(o1); queue.offerLast(o2);
queue.pollFirst();                    // o1

// Stack LIFO: undo thao tác trong giỏ hàng
Deque<CartAction> undo = new ArrayDeque<>();
undo.push(addItem);                   // = addFirst
undo.push(removeItem);
undo.pop();                           // removeItem

Bước 4: Đo: chạy job với 1 triệu dòng, log thời gian: LinkedList + get(i) vài phút, ArrayList vài trăm ms.

5. Cách hoạt động

ArrayList (capacity 10, size 10) → add thứ 11:
 [A B C D E F G H I J]            đầy
 [A B C D E F G H I J K _ _ _ _]  mảng mới 15 ô, arraycopy 10 phần tử
 10 → 15 → 22 → 33 → 49 → 73 ...

LinkedList:
 first                                   last
   ▼                                       ▼
 [prev|A|next] ⇄ [prev|B|next] ⇄ [prev|C|next]
  object @0x1a00   object @0x7f30   object @0x2c88   ← rải rác, mỗi bước = 1 lần nhảy pointer

ArrayDeque (circular buffer, capacity 8):
 index:  0   1   2   3   4   5   6   7
       [ C | D | _ | _ | _ | _ | A | B ]
                 ▲tail           ▲head
 addFirst → head lùi (6→5), addLast → tail tiến (2→3), quay vòng bằng modulo
 đầy (head == tail) → tăng gấp đôi khi nhỏ, ×1.5 khi lớn

6. So sánh

7. Khi nào nên dùng / không nên

• List thông thường: ArrayList; biết trước số lượng thì truyền capacity hoặc gọi ensureCapacity.
• Queue, stack, sliding window, BFS: ArrayDeque.
• LinkedList: chỉ khi thật sự cần xóa giữa qua ListIterator với list rất lớn, hoặc cần chứa null trong queue. Hiếm.
• Không dùng Stack, Vector (lý do ở câu sau).

Đúng là tên rõ hơn, nhưng Stack là class từ Java 1.0 với ba lỗi thiết kế:

1. Extends Vector: mọi method đều synchronized, trả giá lock kể cả khi chỉ một thread dùng.
2. Lộ ra method của List: stack.add(0, x), stack.get(3), stack.remove(1) đều gọi được, phá nguyên tắc LIFO. Đây là ví dụ kinh điển vi phạm "composition over inheritance".
3. Thứ tự duyệt ngược đời: for (x : stack) duyệt từ đáy lên, còn ArrayDeque duyệt từ đỉnh xuống.

Stack<String> s = new Stack<>();
s.push("a"); s.push("b");
s.add(0, "hack");                 // compile được 😬
System.out.println(s);            // [hack, a, b]

Deque<String> d = new ArrayDeque<>();
d.push("a"); d.push("b");
System.out.println(d);            // [b, a] — đỉnh trước

Javadoc của Stack cũng ghi rõ nên dùng Deque. Cần stack thread-safe thì dùng ConcurrentLinkedDeque hoặc LinkedBlockingDeque, không quay về Stack.

Bạn suy luận đúng: xóa k phần tử bằng remove(i) từng lần là O(k·n). Dùng removeIf:

cart.getLines().removeIf(line -> line.qty() == 0);

ArrayList.removeIf làm trong một lượt: đánh dấu phần tử cần xóa, rồi dồn các phần tử còn lại lên một lần, cuối cùng gán null phần đuôi để GC thu. Tổng O(n).

trước:  [A0 B2 C0 D1 E0]      (số = qty)
dồn:    [B2 D1 _  _  _ ]      1 lượt copy
size = 2, phần đuôi = null

Tương tự, subList(from, to).clear() xóa một đoạn liên tiếp với một lần arraycopy. Còn chuyện vì sao xóa trong for-each bị ConcurrentModificationException thì đã có ở bài 1.12.

Không hẳn. clear() chỉ gán null cho các ô và đặt size = 0; các Order được GC thu, nhưng mảng elementData 1 triệu ô vẫn còn (khoảng 4–8 MB reference).

orders.clear();          // elementData.length vẫn ~1.000.000
orders.trimToSize();     // thu mảng về đúng size (0)
// hoặc đơn giản: orders = new ArrayList<>();   bỏ hẳn list cũ cho GC

ArrayList không bao giờ tự co lại. Với list sống lâu (field của singleton bean, cache) mà từng phình to, đây là kiểu "rò" bộ nhớ âm thầm. Với biến cục bộ trong method thì không cần lo, hết method là cả list được thu.

Ba câu hay gặp:

Câu 1: ArrayList hoạt động bên trong và tăng kích thước thế nào?

🇻🇳 Tiếng Việt:

ArrayList bọc một mảng Object và biến size. Tạo bằng constructor mặc định thì mảng rỗng, lần add đầu cấp 10 ô. Khi đầy, nó tạo mảng mới lớn gấp 1.5 lần và copy sang bằng System.arraycopy, nên add cuối là amortized O(1). Chèn hoặc xóa ở giữa phải dịch phần sau, O(n). Mảng không tự co lại; biết trước số phần tử thì nên truyền capacity.

🇬🇧 English:

ArrayList wraps an Object array plus a size field. With the default constructor the array starts empty and gets 10 slots on the first add. When full, it allocates an array 1.5 times larger and copies with System.arraycopy, so appending is amortized O(1). Inserting or removing in the middle shifts elements, which is O(n). It never shrinks automatically, so I pass an initial capacity when I know the size.

Câu 2: Vì sao thực tế LinkedList thường chậm hơn ArrayList?

🇻🇳 Tiếng Việt:

O(1) của LinkedList chỉ đúng khi đã có sẵn node; tìm vị trí vẫn O(n). Mỗi node là object riêng, tốn thêm bộ nhớ cho header và hai con trỏ, nằm rải rác nên gây cache miss. ArrayList dùng bộ nhớ liền kề, CPU prefetch tốt, arraycopy rất nhanh.

🇬🇧 English:

LinkedList's O(1) only holds once you already have the node; finding the position is still O(n). Each node is a separate object with header and two pointers, scattered across the heap, causing cache misses. ArrayList uses contiguous memory, benefits from CPU prefetching, and arraycopy is very fast.

Câu 3: Nên dùng gì làm stack/queue? Vì sao không dùng Stack?

🇻🇳 Tiếng Việt:

Dùng ArrayDeque: mảng vòng với head và tail, thêm bớt hai đầu O(1), không cho null. Stack kế thừa Vector nên synchronized không cần thiết và lộ các method của List như add theo index, phá tính LIFO.

🇬🇧 English:

Use ArrayDeque: a circular array with head and tail indexes, O(1) at both ends, no nulls allowed. Stack extends Vector, so it pays for unnecessary synchronization and exposes List methods like indexed add, which breaks LIFO.

Cách nhớ ngắn gọn

• ArrayList: mảng, grow ×1.5, arraycopy, không tự co.
• LinkedList: Node rải rác, get O(n), cache miss.
• ArrayDeque: mảng vòng, head/tail, stack + queue.
• Stack/Vector: di sản, đừng dùng.