[Bài đọc] Cấu trúc dữ liệu ArrayList

ArrayList là một cấu trúc dữ liệu danh sách đặc trưng. Bên trong ArrayList sử dụng mảng để lưu trữ dữ liệu, do đó nó có tên là ArrayList, tức là một List được triển khai dựa trên Array.

Kích thước của ArrayList được điều chỉnh phù hợp tuỳ theo số lượng các phần tử, điều này khác với mảng trong Java, bởi vì kích thước của mảng trong Java là luôn cố định.

Đặc điểm của cấu trúc dữ liệu ArrayList đó là hỗ trợ việc truy xuất nhanh đến các phần tử, nhờ việc hỗ trợ cơ chế truy xuất ngẫu nhiên của mảng

Ngược lại, các thao tác thêm và xoá các phần tử trong ArrayList lại không hiệu quả, bởi vì cần phải thực hiện các thao tác dịch chuyển các phần tử trong mảng.

Các thao tác cơ bản của ArrayList

• get(): Lấy về một phần tử
• add(): Thêm một phần tử
• remove(): Xoá một phần tử
• size(): Lấy về số lượng phần tử
• find(): Tìm kiếm phần tử
• isEmpty(): Kiểm tra rỗng

Xét về cấu trúc của ArrayList, thì bên trong ArrayList là một mảng để lưu trữ dữ liệu. Chúng ta có các khái niệm cơ bản, đó là:

• Capacity tức là số lượng các phần tử mà ArrayList có thể lưu trữ trong mảng hiện tại. Capacity chính là độ dài của mảng hiện tại bên trong ArrayList.
• Size là số lượng các phần tử hiện có trong ArrayList

Chẳng hạn, trong ví dụ này, độ dài của mảng bên trong ArrayList là 8, như vậy ta nói rằng ArrayList này có Capacity là 8.

Nhưng hiện tại ArrayList này chỉ chứa 2 phần tử, do đó chúng ta nói rằng ArrayList này có size là 2.

Một điều đặc biệt đó là Capacity của ArrayList có thể mở rộng khi cần thiết.

Chẳng hạn, trong trường hợp này, nếu chúng ta thêm vào nhiều hơn 8 phần tử vào trong ArrayList thì một mảng khác với độ dài lớn hơn sẽ được tạo ra đủ để lưu trữ số lượng đó thay thế cho mảng có độ dài 8 hiện tại.

Thêm phần tử vào ArrayList

Chẳng hạn, chúng ta có một ArrayList bao gồm các phần tử từ e0 đến ek. Bây giờ, chúng ta muốn chèn một phần tử e vào vị trí i.

Như vậy, chúng ta cần thực hiện dịch chuyển các phần tử ở phía sau vị trí I lùi lại một vị trí. Chẳng hạn, phần tử k sẽ dịch về k + 1, phần tử k – 1 sẽ dịch về k… và cứ như vậy, phần tử tại vị trí i sẽ dịch về vị trí i + 1 để nhường chỗ cho phần tử mới chèn vào.

Như vậy, sau khi chèn một phần tử vào thì kích thước của ArrayList sẽ tăng thêm 1.

Đây là trường hợp minh họa mà capacity của mảng vẫn đủ để thêm một phần tử mới. Còn trong trường hợp mà capacity của ArrayList bằng với Size của nó thì sẽ cần thêm một thao tác là tạo một mảng mới với kích thước lớn hơn.

Xoá phần tử khỏi ArrayList

Tương tự như trường hợp thêm phần tử vào ArrayList, giả sử chúng ta có một ArrayList với các phần tử từ e0 đến ek. Bây giờ chúng ta muốn xoá một phần tử e tại vị trí i.

Thao tác ở đây đó là dịch chuyển các phần tử từ vị trí i + 1 tiến lên trước một vị trí. Chẳng hạn, phần tử tại vị trí i + 1 sẽ thay thế cho phần tử tại vị trí i, phần tử tại vị trí i + 2 sẽ thay thế cho phần tử tại vị trí i + 1, và cứ như thế cho đến phần tử tại vị trí k sẽ thay thế cho phần tử tại vị trí k – 1.

Như vậy, sau khi xoá phần tử thì size của ArrayList sẽ giảm 1.