Sự khác biệt giữa ArrayList và LinkedList trong Java

Cả hai đều implement List interface, không synchronized, cho phép null và duplicate. Khác biệt cốt lõi là cấu trúc dữ liệu bên dưới dẫn đến đặc tính hiệu năng khác nhau.

Bảng so sánh chi tiết

STT	Tiêu chí	ArrayList	LinkedList
1	Cấu trúc nội bộ	Mảng động (`Object[] elementData`). Mở rộng bằng copy mảng.	Doubly Linked List (node prev/next). Mỗi node là object riêng.
2	Truy cập theo index (get/set)	O(1) - truy cập trực tiếp qua index mảng.	O(n) - phải duyệt từ head hoặc tail gần hơn.
3	Thêm/xóa ở cuối (add/remove last)	O(1) amortized (trừ khi resize).	O(1) - có tail pointer.
4	Thêm/xóa ở giữa/đầu	O(n) - phải shift array (System.arraycopy).	O(1) sau khi có reference đến node (ListIterator).
5	Memory overhead	Thấp: chỉ mảng object reference + wasted capacity.	Cao: Mỗi node = object + 2 reference (prev, next) + header.
6	Implement interface	Chỉ `List`.	`List` + `Deque` + `Queue` (có push/pop, offer/poll).
7	Cache locality	Tốt (liền mạch memory) → CPU cache friendly.	Kém (node rải rác heap) → cache miss nhiều.
8	Iterator	`Iterator`, `ListIterator` (fail-fast).	`Iterator`, `ListIterator`, `DescendingIterator`.

Ví dụ code

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class JavaTester {
    public static void main(String args[]) {
        List arrayList = new ArrayList<>();
        arrayList.add("A"); arrayList.add("B"); arrayList.add("C"); arrayList.add("D");
        
        List linkedList = new LinkedList<>();
        linkedList.add("A"); linkedList.add("B"); linkedList.add("C"); linkedList.add("D");
        
        System.out.println("ArrayList: " + arrayList);
        System.out.println("LinkedList: " + linkedList);
        
        // Demo Deque operations (LinkedList only)
        ((LinkedList) linkedList).push("First");  // addFirst
        ((LinkedList) linkedList).addLast("Last");
        System.out.println("After push/addLast: " + linkedList);
    }
}

Kết quả

ArrayList: [A, B, C, D]
LinkedList: [A, B, C, D]
After push/addLast: [First, A, B, C, D, Last]

Benchmark tham khảo (JMH style)

Operation                    ArrayList (ns/op)   LinkedList (ns/op)
get(index)                           ~5                    ~5000 (index=mid)
add(last)                            ~3                    ~10
add(0) / addFirst                    ~50000                ~10
remove(0) / removeFirst              ~50000                ~10
iterate (for-each)                   ~0.3/element          ~0.5/element
memory (1M elements)                 ~8 MB                 ~40 MB+

Quy tắc chọn lựa

Mặc định chọn ArrayList cho 95% trường hợp.

ArrayList khi:
- Truy cập ngẫu nhiên (get(i)) nhiều.
- Chỉ thêm/xóa ở cuối.
- Dữ liệu nhỏ-vừa, cache locality quan trọng.
- Cần serialize, clone, toArray() hiệu quả.
LinkedList khi:
- Thêm/xóa nhiều ở đầu/giữa (queue, deque, buffer).
- Cần Deque operations: push/pop, offer/poll, peek.
- Duyệt tuần tự nhiều, ít random access.
- Implement LRU cache, undo/redo stack.

Lưu ý quan trọng

LinkedList không implement RandomAccess - flag báo hiệu không nên dùng index access.
Với Queue/Deque, ưu tiên ArrayDeque (circular array) - nhanh hơn LinkedList, không GC pressure node object.
ArrayDeque không implement List (không get(index)), nhưng là Deque implementation mặc định khuyên dùng.
Java 21+: List.of(), Set.of() immutable - dùng khi không cần mutate.