list in java

Làm backend thì List<E> chắc là cấu trúc dữ liệu mình gõ nhiều nhất. Nó đơn giản, dễ dùng, và hình như lúc nào cũng chạy ổn. Nhưng cái tiện bề ngoài đó hay giấu đi những chi phí ngầm về bộ nhớ và CPU.

Làm Engineer thì chỉ biết "dùng thế nào" là chưa đủ. Muốn làm hệ thống xử lý hàng triệu request mà độ trễ vẫn thấp, mình cần hiểu phần cứng bên dưới (Mechanical Sympathy): từng byte bộ nhớ được cấp phát ra sao, CPU cache làm việc với cấu trúc dữ liệu của mình thế nào.

Bài này mổ xẻ List Interface trong Java: cấu trúc bên trong, độ phức tạp thuật toán, tới mấy cái bẫy hay gặp ngoài thực tế.

# tổng quan list interface

List<E> là một ordered collection (dãy dữ liệu có thứ tự). Nó cho chứa phần tử trùng (duplicate) và hỗ trợ truy xuất ngẫu nhiên (random access) qua index.

Gia phả của List trông thế này:

Lưu ý: từ Java 21 có thêm SequencedCollection, đem các method chung như getFirst(), getLast() tới mọi collection có thứ tự, thao tác với List cũng gọn hơn.

# arraylist

ArrayList là implementation mà 95% dev sẽ gõ theo phản xạ khi cần một List. Nó mạnh chính vì nó đơn giản.

# internal structure

Nói cho cùng, ArrayList chỉ là một lớp bọc (wrapper) quanh mảng tĩnh Object[], kèm một biến size để đếm số phần tử thật sự đang có.

// Khởi tạo một ArrayList
ArrayList<String> list = new ArrayList<>();
 
// Bên dưới low-level (Java 8+):
// elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA (mảng rỗng dùng chung)
// size = 0
// Lần add() đầu tiên mới cấp phát mảng 10 phần tử (default capacity)

# grow mechanism: mảng phình ra thế nào

Mảng trong Java có kích thước cố định. ArrayList mà đầy thì phải cấp phát lại (resize), và việc này khá tốn:

• Cấp phát một mảng mới to khoảng 1.5 lần mảng cũ (oldCapacity + (oldCapacity >> 1)). Riêng lần đầu của new ArrayList<>() là nhảy từ mảng rỗng lên 10.
• Dùng System.arraycopy() (một native method) bê hết dữ liệu từ mảng cũ sang mảng mới.
• Mảng cũ bị bỏ lại, chờ Garbage Collector (GC) dọn.

Mỗi lần resize tốn thời gian tuyến tính O(n). Nhưng vì capacity tăng theo cấp số nhân, tổng số phần tử bị copy qua mọi lần resize chỉ cỡ vài lần n, nên tính trung bình (amortized) add(e) vẫn là O(1).

# operations complexity

# memory layout

Dữ liệu trong ArrayList nằm liền nhau trên RAM: [elem0, elem1, elem2, ..., null, null]

• Overhead: mỗi phần tử chỉ tốn một tham chiếu (reference) trỏ tới object thật, 4 bytes khi bật Compressed Oops (mặc định với heap dưới khoảng 32GB), 8 bytes khi tắt.
• Wasted Space: phần capacity dư ra mà chưa dùng tới.

# best practices

• Đoán trước capacity: biết trước sẽ đổ 10,000 records từ database vào List thì khởi tạo luôn new ArrayList<>(10000). Đỡ được cả đống lần System.arraycopy() vô ích, GC cũng nhẹ hơn.
• Trả bớt bộ nhớ: populate xong một danh sách lớn và không định thêm gì nữa thì gọi list.trimToSize(), phần mảng null dư sẽ được trả lại cho Heap.
• Bulk operations: dùng addAll() thay vì lặp từng phần tử rồi add(). addAll() grow mảng tối đa 1 lần rồi copy cả cụm bằng arraycopy.

# LinkedList

Nhiều tài liệu cũ khuyên dùng LinkedList khi cần chèn/xoá nhiều ở giữa danh sách. Với phần cứng bây giờ, nghe theo lời khuyên này thường là tự bắn vào chân về hiệu năng.

# internal structure

LinkedList trong Java là danh sách liên kết kép (Doubly-linked list). Mỗi phần tử là một Node riêng, giữ tham chiếu tới Node trước và Node sau.

Cú pháp Java:

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

Sao LinkedList chạy thực tế lại chậm? Lý thuyết thì thêm/xoá ở giữa LinkedList chỉ tốn O(1) để đổi con trỏ. Nhưng muốn tới được vị trí đó thì phải duyệt danh sách, mất O(n).

Chưa hết, Cache Locality (tính cục bộ của cache) là điểm yếu chí mạng của LinkedList:

• ArrayList để các phần tử nằm sát nhau trên RAM. CPU đọc phần tử đầu là nạp luôn mấy phần tử kế tiếp vào L1/L2 Cache, duyệt mảng nhanh như chớp.
• LinkedList thì mỗi Node là một object riêng, sau một thời gian thêm/xoá và GC dọn dẹp thì chúng dễ nằm rải rác khắp Heap. Mỗi lần nhảy qua next là một lần đọc phụ thuộc vào kết quả lần trước, CPU không đoán trước được để nạp sẵn, nên dễ dính "Cache Miss" và tốn cả trăm chu kỳ clock để lôi dữ liệu từ RAM lên. Thêm nữa, phần tử thật (item) lại là một object khác, tức thêm một lần nhảy nữa.

# operations complexity

# linkedlist implements deque

LinkedList<String> deque = new LinkedList<>();
deque.addFirst("A");    // push to front
deque.addLast("B");     // push to back
deque.peekFirst();      // view front without remove
deque.pollLast();       // remove from back

# memory overhead

Mỗi phần tử thêm vào, LinkedList tạo một object Node. Trên JVM 64-bit với cấu hình mặc định (Compressed Oops và compressed class pointers bật): 12 bytes (Object header) + 4 bytes (prev) + 4 bytes (next) + 4 bytes (item) = 24 bytes. Tắt Compressed Oops (heap lớn hơn khoảng 32GB) thì thành 16 + 8 + 8 + 8 = 40 bytes. Tức là gấp khoảng 6 lần mức 4 bytes mỗi phần tử của ArrayList, chưa kể GC phải theo dõi thêm một object cho mỗi phần tử. Lên tới hàng triệu phần tử thì khoản phí này rất đáng kể.

# ArrayList vs LinkedList

→ 95% trường hợp cứ chọn ArrayList. LinkedList chỉ đáng dùng khi bạn xài nó như hàng đợi hai đầu (Deque), liên tục thêm/xoá ở đầu/cuối danh sách, hoặc khi dùng Iterator.remove() trong một vòng lặp lớn.

# CopyOnWriteArrayList

Trong code đa luồng, trạng thái chia sẻ (shared state) là gốc của đủ loại bug concurrency. ArrayList không thread-safe. Vector hay Collections.synchronizedList() thì an toàn, nhưng mọi thao tác đều đi qua cùng một lock, nhiều thread tranh nhau là thành nghẽn cổ chai (bottleneck). Lại thêm một cái bẫy: duyệt bằng iterator trên synchronizedList vẫn phải tự bọc trong synchronized (list) { ... }, không thì vẫn dính ConcurrentModificationException.

Với dữ liệu đọc nhiều, ghi ít thì có CopyOnWriteArrayList:

• Đọc: không khoá gì cả (lock-free). Các thread đọc từ một "snapshot" cố định, tốc độ O(1).
• Ghi: mỗi lần thêm/xoá/sửa, nó copy nguyên mảng bên dưới ra bản mới, sửa trên bản copy, rồi tráo (swap) tham chiếu.

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
 
// Write: copy entire array → modify copy → swap reference
list.add("item"); // O(n) — expensive!
 
// Read: no locking, read from current snapshot
list.get(0); // O(1), always consistent snapshot
 
// Iterator: snapshot at creation time, never throws ConcurrentModificationException
for (String item : list) {
   list.add("new"); // OK! Iterator sees old snapshot
}

Dùng ở đâu: rất hợp với tình huống Read-Heavy, Write-Rare như danh sách Event Listeners, cache cấu hình (Config Caches) hay danh sách instance trong Service Discovery. Ngược lại, ghi thường xuyên vào một list lớn thì mỗi lần ghi là copy cả mảng, vừa chậm vừa sinh rác cho GC. Trường hợp đó dùng synchronizedList vẫn hợp lý hơn, hoặc đổi sang cấu trúc khác như ConcurrentLinkedQueue/ConcurrentLinkedDeque nếu chỉ cần thêm vào và lấy ra theo thứ tự.

# vector & stack (legacy)

// Vector = synchronized ArrayList (every method synchronized)
Vector<String> vector = new Vector<>(); // DON'T USE — use ArrayList + external sync
 
// Stack = LIFO, extends Vector
Stack<String> stack = new Stack<>(); // DON'T USE — use ArrayDeque

Thay thế:

• Vector → ArrayList (hoặc CopyOnWriteArrayList nếu cần thread-safe)
• Stack → ArrayDeque

# immutable lists

Bất biến (Immutability) làm code dễ đoán và an toàn hơn, nhất là trong Clean Architecture. Mấy bản Java gần đây có sẵn khá nhiều API cho chuyện này:

// Java 9+: Immutable tuyệt đối (Không cho phép null)
List<String> immutable = List.of("Clean", "Architecture", "CQRS");
immutable.add("Saga"); // Bắn lỗi: UnsupportedOperationException!
 
// Java 10+: Copy tạo ra một Immutable List mới
List<String> copy = List.copyOf(mutableList);
 
// Bẫy Unmodifiable View:
List<String> view = Collections.unmodifiableList(mutableList);
mutableList.add("New Event"); // CẢNH BÁO: 'view' cũng sẽ bị thay đổi theo!

# sorting

Bên dưới, Java dùng thuật toán khác nhau cho từng loại dữ liệu:

• Arrays.sort() cho primitives: dùng Dual-Pivot Quicksort, trung bình O(nlogn). Không cần stable vì hai số bằng nhau thì không phân biệt được.
• Arrays.sort() cho Objects (và Collections.sort()): dùng TimSort, một thuật toán stable sort khá khôn, tận dụng các đoạn đã sắp sẵn (runs) để chạy nhanh hơn, rất hợp với dữ liệu ngoài đời.

// Natural order
Collections.sort(list);
list.sort(Comparator.naturalOrder());
 
// Custom comparator
list.sort(Comparator.comparing(User::getName));
list.sort(Comparator.comparing(User::getAge).reversed());
 
// Multiple fields
list.sort(Comparator.comparing(User::getLastName)
   .thenComparing(User::getFirstName)
   .thenComparingInt(User::getAge));
 
// Null-safe
list.sort(Comparator.nullsLast(Comparator.naturalOrder()));

# sort algorithms

• Arrays.sort() (primitives): Dual-Pivot Quicksort - O(nlogn) average
• Arrays.sort() (objects): TimSort - O(nlogn), stable, good for partially sorted
• Collections.sort(): gọi list.sort(). ArrayList sort thẳng trên mảng bên trong; các List khác thì copy ra mảng, sort bằng Arrays.sort() rồi ghi ngược lại

# stream operations

Xử lý dữ liệu với Streams thì gọn gàng hơn hẳn:

// Filter + transform
List<String> names = users.stream()
   .filter(u -> u.getAge() > 18)
   .map(User::getName)
   .collect(Collectors.toList());
 
// toList() (Java 16+, unmodifiable)
List<String> unmodifiableNames = users.stream()
   .map(User::getName)
   .toList();
 
// Flat map
List<String> allTags = posts.stream()
   .flatMap(p -> p.getTags().stream())
   .distinct()
   .collect(Collectors.toList());
 
// Reduce
int total = orders.stream()
   .mapToInt(Order::getAmount)
   .sum();
 
// Partition
Map<Boolean, List<User>> partition = users.stream()
   .collect(Collectors.partitioningBy(u -> u.getAge() >= 18));

# common pitfalls

# ConcurrentModificationException

Đừng bao giờ gọi list.remove() bên trong vòng for-each. Cơ chế fail-fast của Iterator sẽ ném exception ngay.

// WRONG: modify list during iteration
for (String item : list) {
   if (item.equals("remove")) {
       list.remove(item); // ConcurrentModificationException!
   }
}
 
// RIGHT: use Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
   if (it.next().equals("remove")) {
       it.remove(); // safe
   }
}
 
// RIGHT: removeIf (Java 8+)
list.removeIf(item -> item.equals("remove"));

# Arrays.asList() trap

Method này không trả về java.util.ArrayList, mà là một class nội bộ có kích thước cố định (fixed-size), dùng thẳng luôn mảng gốc.

List<String> list = Arrays.asList("a", "b", "c");
list.add("d");    // UnsupportedOperationException! (fixed-size)
list.set(0, "x"); // OK (modification allowed)
 
// Mutable copy:
List<String> mutable = new ArrayList<>(Arrays.asList("a", "b", "c"));

# subList() is a VIEW

subList() không tạo List mới, nó chỉ trả về một VIEW (khung nhìn) đặt lên danh sách ban đầu.

• Sửa trên subList là danh sách gốc đổi theo.
• Nguy hiểm: đổi cấu trúc danh sách gốc (add/remove) là subList hỏng luôn, truy cập vào sẽ ném ConcurrentModificationException.
• Memory Leak: giữ lại một subList nhỏ xíu là GC không dọn được cả danh sách gốc to đùng phía sau.

List<String> original = new ArrayList<>(List.of("a", "b", "c", "d"));
List<String> sub = original.subList(1, 3); // ["b", "c"]
sub.set(0, "X"); // original is now ["a", "X", "c", "d"]!
original.add("e"); // sub is now INVALID → ConcurrentModificationException on next access

# interview tips

• ArrayList: dynamic array, O(1) get, O(n) insert middle, 1.5x growth
• LinkedList: doubly-linked, O(1) add/remove ends, O(n) random access, ~6x memory per element
• ArrayList wins almost always (cache locality, less memory)
• CopyOnWriteArrayList: snapshot reads, copy-on-write, read-heavy scenarios
• fail-fast iterators: ConcurrentModificationException nếu modify during iteration
• Arrays.asList(): fixed-size, backed by original array
• List.of(): truly immutable, no null
• TimSort: stable, O(nlogn), good for partially sorted data

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