Array và List bên trong

Ở khoá Java Core, array có số ô cố định, còn ArrayList thêm bao nhiêu cũng được. Bên trong ArrayList vẫn là một array. Hiểu cách nó nới rộng, bạn sẽ biết thao tác nào nhanh, thao tác nào chậm.

Khái niệm

Như bài Array và List của khoá Java Core, array xếp các phần tử vào những ô nằm liền nhau trong bộ nhớ. Nhờ vậy lấy theo vị trí chỉ mất O(1), nhưng số ô cố định từ lúc tạo.

📏 Capacity: số ô của array bên trong ArrayList, luôn lớn hơn hoặc bằng size() là số phần tử đang dùng.

Khi array bên trong đầy, ArrayList tạo array mới lớn gấp rưỡi, chép hết phần tử sang, rồi bỏ array cũ.

Ví dụ

Một bản ArrayList tối giản, chỉ chứa String, nới gấp đôi cho dễ đếm:

// Main.java
void main() {
    var cart = new MiniList();
    cart.add("Bút bi");
    cart.add("Vở");
    cart.add("Thước");
    System.out.println(cart.size());       // 3
    System.out.println(cart.capacity());   // 4
}

// MiniList.java
class MiniList {
    private String[] items = new String[2];
    private int count;

    public int size() { return count; }
    public int capacity() { return items.length; }

    public void add(String item) {
        if (count == items.length) {
            String[] bigger =
                new String[items.length * 2];
            for (int i = 0; i < count; i++) {
                bigger[i] = items[i];
            }
            items = bigger;
        }
        items[count] = item;
        count++;
    }
}

• new String[2] tạo array 2 ô trống. count đếm số ô đã dùng.
• size() và capacity() đặt tên theo kiểu của ArrayList.
• Thêm "Thước" khi 2 ô đã đầy: tạo array 4 ô, chép 2 phần tử cũ sang, rồi mới thêm.
• Chép là O(n), nhưng mỗi lần nới đều nới theo tỉ lệ nên việc chép hiếm khi xảy ra. Tính trung bình, add vẫn là O(1).

add(i, x) chèn x vào vị trí i, remove(i) xoá phần tử ở vị trí i, indexOf(x) trả về vị trí của x.

Mô phỏng chạy ArrayList thật, tạo với capacity 2. Array nới gấp rưỡi (2 thành 3, rồi 4) chứ không gấp đôi như MiniList.

var cart = new ArrayList<String>(2);
cart.add("Bút bi");
cart.add("Vở");
cart.add("Thước");
cart.add(0, "Thẻ");
cart.remove(1);
System.out.println(cart.get(2));

Thử ngay

ArrayList không cho xem capacity, nên thử trên MiniList. Thay thân main bằng đoạn sau:

var list = new MiniList();
System.out.println(list.capacity());
for (int i = 1; i <= 9; i++) {
    list.add("SP" + i);
    System.out.print(list.capacity() + " ");
}

Đoán trước khi chạy: list mới tạo có capacity bao nhiêu, và capacity thay đổi ở những lần add nào?

2
2 2 4 4 8 8 8 8 16

Lỗi hay gặp

Lấy dần phần tử đầu bằng remove(0). Mỗi lần xoá phần tử đầu, cả list dời lên một ô. Lấy hết list theo cách này là O(n²).

// SAI — mỗi remove(0) dời hết phần còn lại
List<String> orders = new ArrayList<>();
orders.add("DH1");
orders.add("DH2");
orders.add("DH3");
while (!orders.isEmpty()) {
    System.out.println(orders.get(0));
    orders.remove(0);
}

// ĐÚNG — duyệt từ đầu tới cuối, không xoá
List<String> orders = List.of("DH1", "DH2", "DH3");
for (String order : orders) {
    System.out.println(order);
}

Cần vừa lấy ra ở đầu vừa thêm vào ở cuối thì dùng ArrayDeque của bài Queue.

Tóm tắt

• ArrayList bên trong là array, đầy thì tạo array lớn hơn rồi chép sang.
• Lấy theo vị trí và add vào cuối là O(1).
• Chèn hoặc xoá ở đầu là O(n), vì phải dời các phần tử phía sau.
• size() là số phần tử đang dùng, capacity là số ô đã cấp.