JavaArrayList là mảng động, LinkedList là danh sách liên kết đôi (doubly-linked list). Khác biệt cốt lõi nằm ở cấu trúc dữ liệu bên trong: ArrayList lưu phần tử liên tục trong một mảng, còn LinkedList lưu mỗi phần tử trong một node riêng có con trỏ tới node trước và sau.
Hãy hình dung ArrayList như một dãy ghế trong rạp: muốn chèn người vào giữa thì phải dịch cả hàng. LinkedList như một đoàn tàu: muốn chèn toa mới thì chỉ cần nối lại hai toa kế bên, nhưng muốn tìm toa thứ 100 thì phải đếm từ đầu.
Cơ chế hoạt động:
- get(i): ArrayList truy cập trực tiếp bằng chỉ số mảng nên O(1); LinkedList phải duyệt từ đầu hoặc cuối nên O(n).
- add(0, e): ArrayList dịch toàn bộ phần tử sang phải O(n); LinkedList chỉ thêm node mới ở đầu O(1).
- add(e) cuối: ArrayList O(1) amortized (có thể resize khi đầy); LinkedList O(1) vì có con trỏ tới node cuối.
- Bộ nhớ: mỗi phần tử ArrayList chỉ tốn reference (~4–8 byte), LinkedList tốn thêm node và 2 con trỏ (~24 byte).
- Cache locality: ArrayList liên tục nên CPU cache hoạt động tốt; LinkedList rải rác trên heap nên cache miss nhiều.
Ví dụ minh hoạ:
List<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add(0, "B"); // dịch phần tử, O(n)
List<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add(0, "B"); // thêm node đầu, O(1)Edge case: LinkedList cũng implement Deque, nhưng nếu bạn cần queue/deque thì dùng ArrayDeque — nó nhanh hơn LinkedList ở các thao tác thêm/xoá ở hai đầu của queue/deque nhờ cache locality tốt hơn. Ngay cả add(0, e) trên ArrayList 10K phần tử thường vẫn nhanh hơn LinkedList nhờ memcpy của CPU hiện đại.
Lưu ý: Đừng chọn LinkedList chỉ vì "thêm/xoá đầu nhanh". Trong thực tế, ArrayList là lựa chọn mặc định cho hầu hết use case; nếu cần queue/deque, hãy dùng ArrayDeque.