JavaArrayList bọc một mảng Object[]. Khi add mà mảng đã đầy, nó cấp mảng mới lớn hơn rồi copy toàn bộ phần tử sang.
- Khởi tạo mặc định là rỗng; lần
addđầu tiên cấp dung lượng 10. - Khi đầy, dung lượng mới ≈ cũ × 1.5 (
oldCapacity + (oldCapacity >> 1)), rồiArrays.copyOf.
10 → 15 → 22 → 33 → 49 → ...Vì sao 1.5 chứ không phải ×2: cân bằng giữa số lần copy và bộ nhớ phí. Nhờ nhân theo hệ số, add có chi phí amortized O(1) dù mỗi lần grow là O(n).
Tối ưu: biết trước số phần tử → new ArrayList<>(expectedSize) để tránh nhiều lần resize + copy. remove ở giữa phải dịch trái các phần tử sau nó (O(n)) — đó là lý do LinkedList nhỉnh hơn ở chèn/xoá giữa, nhưng thua ở truy cập ngẫu nhiên.