Java| Thao tác | ArrayList (mảng động) | LinkedList (doubly-linked) |
|---|---|---|
get(i) | O(1) | O(n) — phải duyệt |
add(0, e) đầu | O(n) — dịch hết | O(1) |
add(e) cuối | O(1) amortized | O(1) |
| Memory mỗi element | ~4-8 byte (reference) | ~24 byte (node + 2 pointer) |
| Cache locality | Tốt (liên tục) | Tệ (rải rác heap) |
Khi dùng:
- ArrayList: default cho mọi List use case. Cache-friendly nên thực tế thường nhanh hơn LinkedList.
- LinkedList: hiếm khi cần. Muốn FIFO queue/deque → dùng ArrayDeque (nhanh hơn LinkedList mọi op).
Sự thật khó tin: ngay cả add(0, e) trên ArrayList 10K element vẫn nhanh hơn LinkedList nhờ memcpy CPU hiện đại.
Tip: biết trước size → new ArrayList<>(expectedSize) để tránh resize.
Đừng chọn LinkedList chỉ vì "thêm/xoá đầu nhanh" — ArrayDeque luôn tốt hơn cho use case đó.