Skip to content
TungDaDev's Blog

List trong Java: ArrayList, LinkedList và những cái bẫy ít ai để ý

Java list.webp
Published on
14 mins read

List<String> roles = Arrays.asList("USER", "ADMIN"); rồi roles.add("AUDITOR");. Code biên dịch ngon, review lướt qua cũng chẳng ai thấy gì lạ. Chạy lên thì UnsupportedOperationException.

List<E> chắc là cấu trúc dữ liệu dân backend 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. Chính vì thế mà mấy cái bẫy kiểu trên, cùng những chi phí ngầm về bộ nhớ và CPU, hay bị bỏ qua.

Biết "dùng thế nào" thì chưa đủ cho hệ thống xử lý hàng triệu request mà độ trễ vẫn thấp. Mình cần hiểu cả 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. Đó cũng là lý do LinkedList hay thua ArrayList ở đúng những chỗ sách bảo nó phải thắng.

# 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:
list-hierarchy

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

OperationComplexityLý do
get(index)O(1)Direct array access
set(index, e)O(1)Direct array access
add(e) (end)O(1) amortizedAppend, occasional resize
add(index, e)O(n)Shift elements right
remove(index)O(n)Shift elements left
remove(Object)O(n)Linear search + shift
contains(e)O(n)Linear search
indexOf(e)O(n)Linear search
size()O(1)Stored field
isEmpty()O(1)size == 0

# 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.

list-structure

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

OperationComplexityLý do
get(index)O(n)Traverse from head or tail
set(index, e)O(n)Traverse to find node
addFirst(e) / addLast(e)O(1)Update head/tail pointers
add(index, e)O(n)Traverse + O(1) link
removeFirst() / removeLast()O(1)Update head/tail
remove(index)O(n)Traverse + O(1) unlink
contains(e)O(n)Linear search

# 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

Tiêu chíArrayListLinkedList
Random accessO(1) ★O(n)
Add/remove at endO(1) amortizedO(1)
Add/remove at middleO(n) (shift)O(n) (traverse) + O(1) (link)
Add/remove at beginningO(n) (shift all)O(1) ★
Memory per element~4 bytes (+ phần dư)~24 bytes (40 nếu tắt Compressed Oops)
Cache localityExcellent (contiguous)Poor (scattered in heap)
Iterator removeO(n)O(1)

→ 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

Về thuật toán: Arrays.sort() với mảng primitive dùng Dual-Pivot Quicksort (O(nlogn) trung bình), còn với mảng object dùng TimSort (O(nlogn), stable, chạy rất nhanh với dữ liệu đã gần sắp xếp).

Từ Java 8 trở đi, Collections.sort(list) thực chất chỉ uỷ quyền sang list.sort(null). Với List nói chung, default method List.sort() phải gọi toArray() để chép dữ liệu ra mảng tạm, chạy Arrays.sort() rồi dùng ListIterator ghi ngược từng phần tử về lại list. Riêng ArrayList ghi đè sort() để sắp xếp trực tiếp ngay trên mảng nội bộ elementData, nhờ vậy tiết kiệm được một lần cấp phát và copy mảng tạm.

# 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() trực tiếp bên trong vòng for-each. Bên dưới, ArrayList giữ một biến đếm số lần thay đổi cấu trúc là modCount. Khi tạo Iterator (vòng for-each ngầm dùng Iterator), nó chụp lại giá trị expectedModCount = modCount. Nếu bạn gọi list.remove(), modCount tăng lên trong khi expectedModCount của iterator giữ nguyên; tới bước next() kế tiếp, cơ chế fail-fast phát hiện hai số lệch nhau và ném ConcurrentModificationException ngay. Ngược lại, gọi it.remove() thì chính iterator vừa xoá vừa tự cập nhật lại expectedModCount = modCount, nên chạy an toàn.

// 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

Mấy ý hay bị hỏi kỹ khi đi phỏng vấn:

  • ArrayList vs LinkedList: ArrayList dựa trên mảng động, đọc ngẫu nhiên O(1), chèn giữa O(n), đầy thì nở gấp 1.5x. LinkedList là danh sách liên kết kép, thêm/xoá hai đầu O(1) nhưng truy cập theo index mất O(n) và tốn bộ nhớ gấp khoảng 6 lần mỗi phần tử. Thực tế ArrayList thắng ở hầu hết kịch bản nhờ cache locality và ít rác trên Heap.
  • CopyOnWriteArrayList: đọc hoàn toàn không khoá (lock-free) trên snapshot hiện tại, còn ghi thì copy cả mảng. Chỉ hợp với bài toán đọc nhiều, ghi hiếm.
  • Cơ chế fail-fast: iterator so sánh modCount và expectedModCount, sửa cấu trúc list từ bên ngoài trong lúc duyệt sẽ ném ConcurrentModificationException.
  • Phân biệt Arrays.asList(), List.of() và subList(): Arrays.asList() trả về list cố định kích thước (gọi set được nhưng add/remove ném lỗi) và dùng chung mảng gốc (sửa list là sửa mảng); List.of() (Java 9+) bất biến hoàn toàn và cấm null; còn subList() chỉ là một khung nhìn (view) giữ tham chiếu tới list gốc.
  • Sort: List.sort()/Collections.sort() với object dùng TimSort, stable, O(nlogn), hợp với dữ liệu đã gần sắp xếp.

Ngoài phỏng vấn, có một việc làm được ngay trong codebase của bạn: search new LinkedList, Arrays.asList( và .subList(. LinkedList nào không dùng như hàng đợi hai đầu thì đổi sang ArrayList (hoặc ArrayDeque nếu đúng là hàng đợi). Arrays.asList nào sau đó bị add/remove là một lỗi đang chờ nổ. subList nào được giữ lâu trong field hay cache thì đang giữ luôn cả list gốc.

Muốn hiểu sâu modCount và vì sao fail-fast có lúc không báo lỗi thì đọc tiếp bài Iterator pattern.

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