99 Ngày Java — Ngày 32: List — ArrayList vs LinkedList

Ngày 31 vẽ bản đồ — hôm nay ta mổ xẻ loài được dùng nhiều nhất: List, qua trận đối đầu kinh điển ArrayList vs LinkedList. Đây cũng là câu hỏi phỏng vấn Java phổ biến bậc nhất, và đa số trả lời sai theo cùng một kịch bản: "chèn giữa thì LinkedList nhanh hơn". Bài hôm nay đi xuống tận mảng động bên trong ArrayList, chuỗi node của LinkedList, số đo thật để phá hiểu lầm, và khép lại bằng kỹ năng sống còn: duyệt và xóa an toàn — nơi ConcurrentModificationException chờ sẵn người mới.

Sketchnote Ngày 32: ArrayList vs LinkedList — mảng động nới rộng 1.5 lần, chuỗi node đôi, bảng số đo hiệu năng và duyệt xóa an toàn với removeIf

ArrayList — mảng động và bí mật amortized

// ArrayList = MẢNG ĐỘNG — một mảng thường + nghệ thuật nới rộng
// Bên trong (rút gọn từ mã nguồn JDK):
public class ArrayList<E> {
    Object[] elementData;     // mảng thật đằng sau — capacity
    int size;                 // số phần tử ĐANG dùng (≠ độ dài mảng!)
}

List<Integer> ds = new ArrayList<>();   // mảng rỗng — chưa cấp phát
ds.add(1);                              // lần add đầu: cấp mảng 10 ô
// ... add đến phần tử thứ 11:
// 1. Mảng đầy → tạo mảng MỚI to gấp ~1.5 lần (10 → 15 → 22 → 33...)
// 2. Arrays.copyOf chép 10 phần tử cũ sang
// 3. Mảng cũ chờ GC

// Vì sao add cuối vẫn tính O(1)? — "AMORTIZED":
// nhân đôi hiếm dần khi mảng lớn; chia đều chi phí chép cho mọi lần add → trung bình O(1)

// get(i) là phép cộng con trỏ — O(1) đúng nghĩa:
ds.get(500_000);                        // địa_chỉ_gốc + i × kích_thước — tức thì

// add/remove GIỮA phải dịch cả đuôi — O(n):
ds.add(0, 99);                          // System.arraycopy đẩy TOÀN BỘ sang phải 1 ô

// Biết trước kích thước? Nói với constructor — khỏi nới rộng lần nào:
List<String> lon = new ArrayList<>(1_000_000);   // cấp đủ 1 lần, nhanh hơn rõ rệt

Bên trong chỉ là mảng thường + biến đếm: elementData (capacity) và size (số ô đang dùng) — hiểu cặp này là hiểu mọi hành vi: get là phép cộng địa chỉ O(1), chèn giữa phải arraycopy dịch cả đuôi O(n).
Nghi thức nới rộng: đầy thì tạo mảng mới gấp ~1.5 lần rồi chép sang — vì lần chép hiếm dần theo cấp số nhân, chia đều chi phí thì mỗi add vẫn amortized O(1) — thuật ngữ đáng nhớ để trả lời phỏng vấn chuẩn xác.
Mẹo hiệu năng miễn phí: biết trước số lượng thì new ArrayList<>(n) — triệu phần tử là tiết kiệm ~20 lần cấp phát + chép; cùng triết lý với StringBuilder báo trước capacity (Ngày 21).

LinkedList — chuỗi node và những chi phí ẩn

// LinkedList = CHUỖI NODE đôi — mỗi phần tử một object riêng
class Node<E> {
    E item;
    Node<E> next;             // trỏ tới node sau
    Node<E> prev;             // ... và node trước
}
// LinkedList giữ con trỏ first + last

// Được gì?
list.addFirst("a");           // O(1) — nối con trỏ, không dịch chuyển gì
list.addLast("z");            // O(1)
list.removeFirst();           // O(1) — vì thế LinkedList implements Deque

// Mất gì?
list.get(500_000);            // O(n) — phải ĐI BỘ từng node từ đầu (hoặc cuối)!
// "chèn giữa O(1)" chỉ đúng khi ĐÃ ĐỨNG ở vị trí đó —
// mà đi đến vị trí đã O(n): tổng vẫn O(n), không nhanh hơn ArrayList

// Chi phí ẩn ít ai nói:
// 1. BỘ NHỚ: mỗi phần tử tốn thêm ~2 con trỏ + object header (~24-40 byte/node)
//    → LinkedList 1 triệu Integer ≈ gấp 3-4 lần RAM so với ArrayList
// 2. CACHE: node rải rác khắp heap — CPU cache miss liên tục khi duyệt;
//    ArrayList nằm LIỀN MẠCH → duyệt nhanh hơn nhiều lần dù cùng O(n)
// → Cha đẻ Java (Joshua Bloch) từng đùa: "Tôi có dùng LinkedList đâu"

Mỗi phần tử là một Node riêng với hai con trỏ prev/next: thêm/xóa ở hai đầu chỉ là nối lại con trỏ — O(1) thật, và là lý do LinkedList implements Deque.
Hiểu lầm số một được giải phẫu: "chèn giữa O(1)" chỉ đúng khi đã đứng sẵn tại vị trí — mà đi đến đó phải duyệt từng node O(n): tổng chi phí không hề thắng ArrayList, trong khi get ngẫu nhiên thì thua thảm.
Hai chi phí ẩn quyết định trận đấu: bộ nhớ (mỗi node cõng thêm header + 2 con trỏ — gấp 3-4 lần RAM) và cache locality (node rải rác khắp heap → CPU cache miss liên tục, duyệt chậm hơn nhiều lần dù cùng Big-O) — bài học lớn: Big-O giống nhau, tốc độ thật có thể khác chục lần.

Đối đầu bằng số đo thật

// Đối đầu trực tiếp — 100.000 phần tử (số đo minh họa trên máy thường):
//
//                              ArrayList    LinkedList
// add cuối (100k lần)             ~3 ms        ~5 ms
// get(i) ngẫu nhiên (10k lần)     ~1 ms     ~4.200 ms   ← O(n) mỗi lần get!
// add(0, x) đầu (10k lần)       ~120 ms         ~1 ms   ← chỗ DUY NHẤT thắng
// duyệt for-each toàn bộ          ~2 ms        ~9 ms   ← cache miss
//
// Đọc kết quả cho đúng:
// - ArrayList thắng ÁP ĐẢO ở get + duyệt — hai thao tác chiếm 95% đời thực
// - LinkedList chỉ thắng khi thêm/xóa Ở HAI ĐẦU rất nhiều lần
//   ... nhưng việc đó ArrayDeque (Ngày 36) còn làm TỐT HƠN nữa
//
// Tự đo (mẫu — luôn đo trước khi tin):
long t0 = System.nanoTime();
for (int i = 0; i < 10_000; i++) ds.get(rnd.nextInt(ds.size()));
System.out.println((System.nanoTime() - t0) / 1_000_000 + " ms");

// Kết luận thực dụng 2026:
// - Mặc định: ArrayList (99% trường hợp)
// - Cần hàng đợi/stack hai đầu: ArrayDeque — KHÔNG phải LinkedList
// - LinkedList: gần như chỉ còn giá trị lịch sử + câu hỏi phỏng vấn

Bảng số cho câu trả lời không cãi được: get ngẫu nhiên chênh hàng nghìn lần, duyệt chênh vài lần vì cache — hai thao tác chiếm gần hết đời thực; LinkedList chỉ thắng đúng ô addFirst, và ngay ô đó ArrayDeque (Ngày 36) còn tốt hơn.
Kết luận thực dụng: mặc định ArrayList; cần hàng đợi/stack → ArrayDeque; LinkedList gần như chỉ còn giá trị lịch sử — chính tác giả Joshua Bloch cũng nói không dùng nó.
Kỹ năng bền hơn kết luận: cách đo bằng System.nanoTime trước–sau (Ngày 27) — mọi tranh luận hiệu năng nên kết thúc bằng con số trên máy của chính bạn, không bằng niềm tin.

Duyệt và xóa an toàn

// Duyệt & xóa — nơi mọi người từng ngã ít nhất một lần

// Bẫy 1: xóa trong for thường — NHẢY CÓC phần tử
List<String> ds = new ArrayList<>(List.of("a", "b", "b", "c"));
for (int i = 0; i < ds.size(); i++) {
    if (ds.get(i).equals("b")) ds.remove(i);   // xóa i=1 → "b" thứ hai TRƯỢT lên i=1
}                                               // i++ → bỏ qua nó! Kết quả: [a, b, c] ❌

// Bẫy 2: xóa trong for-each — nổ ngay lập tức
for (String s : ds) {
    if (s.equals("b")) ds.remove(s);           // 💥 ConcurrentModificationException
}
// (cơ chế fail-fast — Ngày 37 mổ xẻ; nay chỉ cần biết: ĐỪNG)

// Cách đúng #1 — removeIf (Java 8+, gọn nhất):
ds.removeIf(s -> s.equals("b"));               // ✅ [a, c] — một dòng, an toàn

// Cách đúng #2 — Iterator.remove khi cần logic phức tạp giữa chừng:
var it = ds.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove();    // ✅ xóa qua iterator — hợp lệ
}

// Bẫy 3: List<Integer> — remove(int) hay remove(Object)?
List<Integer> so = new ArrayList<>(List.of(10, 20, 30));
so.remove(1);                    // xóa THEO CHỈ SỐ → [10, 30]  (autoboxing KHÔNG xảy ra)
so.remove(Integer.valueOf(20));  // xóa THEO GIÁ TRỊ → overload resolution (Ngày 22, 25)

// Xóa NHIỀU theo giá trị? removeAll + Set cho nhanh:
ds.removeAll(Set.of("b", "c"));  // Set.contains O(1) — List to thì khác biệt lớn (Ngày 31)

Hai bẫy khi xóa trong vòng lặp: for-chỉ-số làm phần tử sau trượt lên rồi bị nhảy cóc (bug im lặng — nguy hiểm hơn), for-each thì nổ ConcurrentModificationException (fail-fast — Ngày 37 giải thích cơ chế); cả hai cùng một thuốc.
Thuốc theo thứ tự ưu tiên: removeIf cho điều kiện gọn — một dòng, an toàn, chạy nhanh; Iterator.remove khi cần logic phức tạp giữa vòng duyệt; và removeAll với đối số là Set khi xóa theo tập giá trị (tra O(1) — bài Ngày 31 áp dụng ngay).
Bẫy tinh vi riêng của List<Integer>: remove(1) xóa theo chỉ số còn remove(Integer.valueOf(1)) xóa theo giá trị — overload resolution chọn bản int trước, không autoboxing (Ngày 22 + 25 bắt tay nhau tạo bug).

Chọn gì trong thực tế — tóm tắt

Mặc định vô điều kiện: ArrayList — nhanh nhất ở get/duyệt, gọn bộ nhớ, cache thân thiện.
Biết trước kích thước → new ArrayList<>(n); dữ liệu cố định → List.of (Ngày 29, 31).
Cần queue/deque/stack → ArrayDeque (Ngày 36) — đừng lấy LinkedList vì "nó cũng là Deque".
Xóa theo điều kiện → removeIf; xóa theo tập giá trị → removeAll(Set); đừng bao giờ xóa trong for-each.
Nghe ai nói "chèn giữa dùng LinkedList" → mời họ chạy benchmark của bài này ☕

Bài tập nhỏ

Tự viết MyArrayList tối giản: mảng Object[], add với nới rộng 1.5x, get có kiểm tra biên — hiểu bằng tay nhanh hơn đọc chay.
Chạy benchmark 4 hàng của bài trên máy bạn với 100k phần tử — số của bạn chênh bảng bao nhiêu?
Tái hiện bug nhảy cóc: xóa mọi "b" khỏi [a, b, b, c] bằng for-chỉ-số và giải thích vì sao còn sót; sửa bằng removeIf.
Với List<Integer> [10, 20, 30]: dự đoán kết quả remove(1) và remove(Integer.valueOf(1)) trước khi chạy — rồi kiểm chứng.
Đo khác biệt new ArrayList<>() vs new ArrayList<>(1_000_000) khi add 1 triệu phần tử.

Kết luận

Bốn ý mang về: ArrayList là mảng động — get O(1), add cuối amortized O(1) nhờ nới rộng 1.5x, chèn giữa O(n); LinkedList chỉ thắng ở hai đầu nhưng thua về bộ nhớ lẫn cache — "chèn giữa nhanh hơn" là hiểu lầm vì đi tới vị trí đã O(n); thực dụng: ArrayList mặc định, ArrayDeque cho hàng đợi; và xóa trong vòng lặp bằng removeIf/Iterator.remove — đừng để ConcurrentModificationException dạy bạn bài này lúc 2 giờ sáng. Ngày 33 sang loài hứa duy nhất: Set — HashSet, LinkedHashSet, TreeSet và hợp đồng equals/hashCode/Comparable đằng sau. Hẹn gặp lại!