Danh sách mảng động (ArrayList) là một cấu trúc dữ liệu quen thuộc và thường được sử dụng rộng rãi bởi các lập trình viên. Hãy cùng khám phá cách nó hoạt động.

Cấu trúc dữ liệu bên dưới

ArrayList thực chất là một mảng có thể thay đổi kích thước.

Khi khởi tạo, bạn có thể chỉ định dung lượng ban đầu. Nếu không chỉ định, ArrayList sẽ bắt đầu với một mảng trống và chỉ khi lần đầu tiên thêm dữ liệu vào thì mới khởi tạo dung lượng tối thiểu là 10.

Quản lý dung lượng của ArrayList

Mỗi khi thêm dữ liệu vào ArrayList, trước tiên cần kiểm tra dung lượng:

private void kiemTraDungLuong(int minCap) {
    soThayDoi++;
    if (minCap - luuTru.length > 0)
        tangDungLuong(minCap);
}

Nếu dung lượng hiện tại không đủ để lưu trữ dữ liệu mới, phương thức tangDungLuong sẽ được gọi để mở rộng mảng:

private void tangDungLuong(int minCap) {
    int cuDungLuong = luuTru.length;
    int moiDungLuong = cuDungLuong + (cuDungLuong >> 1);
    if (moiDungLuong - minCap < 0)
        moiDungLuong = minCap;
    if (moiDungLuong - MAX_SIZE > 0)
        moiDungLuong = dungLuongLon(minCap);
    luuTru = Arrays.copyOf(luuTru, moiDungLuong);
}

Lưu trữ dữ liệu

Để thêm dữ liệu vào cuối danh sách, hãy gọi phương thức them(E e). Để thêm tất cả phần tử từ một tập hợp khác, hãy dùng themTatCa(Collection<? extends E> c).

Thêm dữ liệu vào vị trí cụ thể thông qua them(int viTri, E phanTu), điều này sử dụng System.arraycopy để thực hiện việc di chuyển dữ liệu.

Lấy dữ liệu ra

Có hai cách phổ biến để lấy dữ liệu: lấy phần tử tại vị trí cụ thể bằng lay(int viTri), hoặc kiểm tra xem danh sách có chứa phần tử nào đó hay không bằng chuaPhanTu(Object o):

public boolean chuaPhanTu(Object o) {
    return timViTri(o) >= 0;
}

public int timViTri(Object o) {
    if (o == null) {
        for (int i = 0; i < kichThuoc; i++)
            if (luuTru[i] == null)
                return i;
    } else {
        for (int i = 0; i < kichThuoc; i++)
            if (o.equals(luuTru[i]))
                return i;
    }
    return -1;
}

Tổng kết

Việc đọc mã nguồn không chỉ giúp hiểu rõ hơn về cách hoạt động của các cấu trúc dữ liệu mà còn học hỏi được tư duy lập trình của những nhà phát triển tài năng nhất. Ví dụ như cách giải phóng bộ nhớ:

private void xoaNhanh(int viTri) {
    soThayDoi++;
    int soDiChuyen = kichThuoc - viTri - 1;
    if (soDiChuyen > 0)
        System.arraycopy(luuTru, viTri+1, luuTru, viTri, soDiChuyen);
    luuTru[--kichThuoc] = null;
}

Hay tái sử dụng mã:

public boolean giuLaiHet(Collection c) {
    Objects.requireNonNull(c);
    return xoaBatch(c, true);
}

public boolean xoaHet(Collection c) {
    Objects.requireNonNull(c);
    return xoaBatch(c, false);
}