Array Lists
Danh sách mảng được thực thi sử dụng mảng
Một mảng là một cấu trúc dữ liệu có kích thước cố định. Một khi mảng được tạo ra, kích thước của nó không thể thay đổi. Tuy nhiên, bạn vẫn có thể sử dụng các mảng để thực thi các cấu trúc dữ liệu động. Bí quyết là tạo một mảng mới lớn hơn để thay thế mảng hiện tại, nếu mảng hiện tại không thể chứa các phần tử mới trong danh sách.
Ban đầu, một mảng, nói dữ liệu của kiểu E [], được tạo ra với kích thước mặc định. Khi chèn một phần tử mới vào mảng, đầu tiên hãy chắc chắn rằng có đủ chỗ trong mảng đó. Nếu không, tạo ra một mảng mới lớn hơn hai lần so với hiện tại. Sao chép các phần tử từ mảng hiện tại sang mảng mới. Mảng mới bây giờ trở thành mảng hiện tại. Trước khi chèn một phần tử mới tại một vị trí được chỉ định, hãy dịch chuyển về bên phải tất cả các phần tử sau vị trí phần tử được chèn và tăng kích thước danh sách lên 1, như thể hiện trong hình 24.4.
Hình 24.4 Việc chèn một phần tử mới vào mảng yêu cầu tất cả các phần tử ở sau vị trí cần chèn di chuyển sang phải một vị trí để cho phần tử mới có thể được chèn vào tại điểm chèn.
Chú ý: Mảng dữ liệu thuộc kiểu dữ liệu E[]. Mỗi ô trong mảng lưu một đối tượng tham chiếu.
Để loại bỏ một phần tử tại một vị trí được chỉ định, hãy dịch toàn bộ phần tử sau vị trí của phần tử được chỉ định sang trái một ví trí và giảm kích thước của mảng đi 1, như thể hiện trong hình 24.5.
Hình 24.5 Xóa một phần tử khỏi mảng đòi hỏi tất cả các phần tử sau vị trí của phần tử cần xoá được chuyển một ví trí sang trái.
MyArrayList sử dụng một mảng để thực thi MyAbstractList, như thể hiện trong hình 24.6. Sự thực thi của MyArrayList được chỉ ra trong Listing 24.3.
Hình 24.6 MyArrayList thực thi một danh sách sử dụng mảng
public class MyArrayList extends MyAbstractList {
public static final int INITIAL_CAPACITY = 16;
private E[] data = (E[]) new Object[INITIAL_CAPACITY];
/**
* Create a default list
*/
public MyArrayList() {
}
/**
* Create a list from an array of objects
*/
public MyArrayList(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]); // Warning: don't use super(objects)!
}
@Override
/** Add a new element at the specified index */
public void add(int index, E e) {
ensureCapacity();
// Move the elements to the right after the specified index
for (int i = size - 1; i >= index; i--) data[i + 1] = data[i];
// Insert new element to data[index]
data[index] = e;
// Increase size by 1
size++;
}
/**
* Create a new larger array, double the current size + 1
*/
private void ensureCapacity() {
if (size >= data.length) {
E[] newData = (E[]) (new Object[size * 2 + 1]);
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
}
@Override
/** Clear the list */
public void clear() {
data = (E[]) new Object[INITIAL_CAPACITY];
size = 0;
}
@Override
/** Return true if this list contains the element */
public boolean contains(E e) {
for (int i = 0; i < size; i++)
if (e.equals(data[i]))
return true;
return false;
}
@Override
/** Return the element at the specified index */
public E get(int index) {
checkIndex(index);
return data[index];
}
private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException
("index " + index + " out of bounds");
}
@Override
/** Return the index of the first matching element 66 * in this list. Return -1 if no match. */
public int indexOf(E e) {
for (int i = 0; i < size; i++)
if (e.equals(data[i])) return i;
return -1;
}
@Override
/** Return the index of the last matching element 75 * in this list. Return -1 if no match. */
public int lastIndexOf(E e) {
for (int i = size - 1; i >= 0; i--) if (e.equals(data[i])) return i;
return -1;
}
@Override
/** Remove the element at the specified position 84 * in this list. Shift any subsequent elements to the left. 85 * Return the element that was removed from the list. */
public E remove(int index) {
checkIndex(index);
E e = data[index];
// Shift data to the left
for (int j = index; j < size - 1; j++)
data[j] = data[j + 1];
data[size - 1] = null; // This element is now null
// Decrement size
size--;
return e;
}
@Override
/** Replace the element at the specified position
* in this list with the specified element. */
public E set(int index, E e) {
checkIndex(index);
E old = data[index];
data[index] = e;
return old;
}
@Override
public String toString() {
StringBuilder result = new StringBuilder("[");
for (int i = 0; i < size; i++) {
result.append(data[i]);
if (i < size - 1) result.append(", ");
}
return result.toString() + "]";
}
/**
* Trims the capacity to current size
*/
public void trimToSize() {
if (size != data.length) {
E[] newData = (E[]) (new Object[size]);
System.arraycopy(data, 0, newData, 0, size);
data = newData;
} // If size == capacity, no need to trim
}
@Override
/** Override iterator() defined in Iterable */
public java.util.Iterator iterator() {
return new ArrayListIterator();
}
private class ArrayListIterator implements java.util.Iterator {
private int current = 0; // Current index
@Override
public boolean hasNext() {
return (current < size);
}
@Override
public E next() {
return data[current++];
}
@Override
public void remove() {
MyArrayList.this.remove(current);
}
}
}
Listing 24.4 gives an example that creates a list using MyArrayList. It uses the add method to add strings to the list and the remove method to remove strings. Since MyArrayList implements Iterable, the elements can be traversed using a for-each loop (lines 35–36).
Listing 24.4 Tạo ra một danh sách sử dụng MyArrayList. Nó sử dụng phương thức add để thêm các chuỗi vào danh sách và phương thức remove để loại bỏ các chuỗi. Vì MyArrayList thực thi Iterable, nên việc duyệt các phẩn tử có thể sử dụng vòng lặp for-each (dòng 35-36).
public static void main(String[] args) {
// Create a list
MyList list = new MyArrayList();
// Add elements to the list
list.add("America"); // Add it to the list
System.out.println("(1) " + list);
list.add(0, "Canada"); // Add it to the beginning of the list
System.out.println("(2) " + list);
list.add("Russia"); // Add it to the end of the list
System.out.println("(3) " + list);
list.add("France"); // Add it to the end of the list
System.out.println("(4) " + list);
list.add(2, "Germany"); // Add it to the list at index 2
System.out.println("(5) " + list);
list.add(5, "Norway"); // Add it to the list at index 5
System.out.println("(6) " + list);
// Remove elements from the list
list.remove("Canada"); // Same as list.remove(0) in this case
System.out.println("(7) " + list);
list.remove(2); // Remove the element at index 2
System.out.println("(8) " + list);
list.remove(list.size() - 1); // Remove the last element
System.out.print("(9) " + list + "\n(10) ");
for (String s : list)
System.out.print(s.toUpperCase() + " ");
}
