1. Các thành phần Implementations của List Interface
Một số lớp (class) thực thi List interface thường được sử dụng:
| Tên các thành phần | Định nghĩa |
|---|---|
| Array List | Một class dạng list được implement dựa trên mảng có kích thước thay đổi được. |
| Vector | Thực thi lưu trữ như mảng (array) nhưng có thể thay đổi kích thước. Tương đồng với ArrayList nhưng Vector là 1 synchronized, có thể hoạt động trong môi trường đa luồng mà không cần phải khai báo synchronize |
| Linked List | Một class dạng list hoạt động trên cơ sở của cấu trúc dữ liệu danh sách liên kết đôi (double-linked list) |
| Stack | Một class dạng list hoạt động trên cơ sở của cấu trúc dữ liệu ngăn xếp (stack) với kiểu vào ra LIFO (last-in-first-out hay vào sau ra trước) |
1. ArrayList
Lớp ArrayList được sử dụng như một mảng động (Object[]) để lưu trữ các phần tử. Khi khởi tạo mặc định 1 ArrayList (không tham số) nó sẽ khởi tạo 1 kích cỡ ban đầu là 10.
Một số điểm nổi bật của ArrayList:
- Có thể chứa các phần tử trùng lặp
- Duy trì thứ tự của phần tử được thêm vào.
- Không đồng bộ (non-synchronized).
- Cho phép truy cập ngẫu nhiên, tốc độ truy xuất (get) phần tử nhanh vì nó lưu dữ liệu theo chỉ mục (index).
- Thao tác thêm/ xóa (add/ remove) phần tử chậm vì cần nhiều sự dịch chuyển nếu bất kỳ phần tử nào thêm/ xoá khỏi danh sách.
Algorithms
Thêm phần tử
Khi thêm 1 phần tử vào ArrayList thông qua phương thức add(value):
- Kiểm tra xem có đủ không gian trong mảng để chèn một phần tử mới không thông qua phương thức: ensureCapacity(size + 1)
- Chèn phần tử vào vị trí cuối cùng: elementData[size++] = element
- Nếu kích thước bị vượt, nó sẽ tiến hành tính toán lại kích thước mới thông qua công thức (oldCapacity * 3) / 2 + 1 (Java 6) hoặc tăng thêm 50% oldCapacity thông qua 1 shift operator (từ Java 7 trở đi): elementData = (E []) new Object[newCapacity];
Tiếp đến chuyển toàn bộ phần tử từ mãng cũ sang mảng mới: System.arraycopy(oldData, 0, elementData, 0, size);
Khi chèn1 phần tử vào giữa ArrayList thông qua phương thức add(index,value):
- Kiểm tra xem có đủ không gian trong mảng để chèn một phần tử mới không?
- Tiến hành dời các phần tử bên phải 1 phần tử: System.arraycopy(elementData, index, elementData, index + 1, size — index);
- Gán trực tiếp phần tử vào vị trí cần chèn: elementData[index] = element; size++;
Xóa phần tử
ArrayList cho phép 2 cách để xóa phần tử:
- Xóa thông qua chỉ mục (index): remove(index)
- Xóa trực tiếp phần tử: remove(value)
Khi xóa bằng chỉ mục, ArrayList sẽ thực hiện thông qua các bước sau:
- Trước tiên tính toán xem bao nhiêu phần tử cần phải sắp xếp lại: int numMoved = size - index - 1;
- Tiếp đến chèn "đè" toàn bộ các phần tử đứng sau nó và xóa đi phần tử cuối cùng : System.arraycopy(elementData, index + 1, elementData, index, numMoved); elementData[--size] = null;
Với trường hợp xóa thứ 2, nó sẽ duyệt và tìm toàn bộ trên mảng cho đến khi tìm được phần tử tương ứng sau đó thực hiện lệnh xóa như trường hợp 1. Lưu ý chỉ có phần tử đầu tiên được tìm thấy sẽ bị xóa ra khỏi mảng.
Sau khi xóa 1 phần tử, kích thước của mảng sẽ không thay đổi, điều này rất quan trọng khi thao tác dữ liệu lớn, nó sẽ dẫn đến ArrayList chiếm hết vùng nhớ mà không sử dụng đến. Để giải quyết vấn đề đó, ArrayList cung cấp phương thức trimToSize().
2. Vector
Tương tự như ArrayList, nhưng có 1 số khác biệt. Khi thực hiện tính toán lại không gian, Vector tăng kích thước mảng lên gấp đôi tuy nhiên Vector cho phép gán bước tăng thông qua thuộc tính capacityIncrement. Và điểm khác biệt lớn nhất của Vector chính là synchronized. Bất kỳ các phương thức nào thao tác trên Vector đều là thread safe
No comments:
Post a Comment