publicMyArrayList(int initCapacity){ data = (E[]) new Object[initCapacity]; size = 0; }
/***** 增 *****/
// 在数组尾部添加一个元素 publicvoidaddLast(E e){ int cap = data.length; // 检验是否需要扩容 if (size == cap) { resize(2 * cap); } // 在尾部插入元素 data[size] = e; size++; }
// 在 index 索引的位置添加一个元素 e publicvoidadd(int index, E e){ // 检查索引越界(只能确定索引位置是否合法,与当前数组元素个数有关,与数组容量无关) checkPositionIndex(index); // 插入前检查数组容量是否够用,如果数组已满则扩容 int cap = data.length; if (size == cap) { resize(2 * cap); }
// 删除数组的最后一个元素并返回 public E removeLast(){ // 1. 考虑数组是否为空 if (size == 0) { thrownew NoSuchElementException(); } // 2. 考虑是否是否可以缩容 int cap = data.length; if (size == cap / 4) { resize(cap / 2); }
// 删除 index 位置的元素并返回 public E remove(int index){ // 检查索引越界 checkElementIndex(index);
// 考虑可否可以缩容 int cap = data.length; if (size == cap / 4) { resize(cap / 2); }
// 数据搬移 E deletedVal = data[index]; System.arraycopy(data, index + 1, data, index, size - index - 1);
data[size - 1] = null; size--;
return deletedVal; }
/***** 查 *****/
// 返回 index 位置对应的元素 public E get(int index){ // 检查索引越界 checkElementIndex(index);
return data[index]; }
/***** 改 *****/ // 将索引 index 的元素改为 e 并将旧的元素返回 public E set(int index, E e){ checkElementIndex(index); E oldVal = data[index]; data[index] = e; return oldVal; }
/***** 工具函数 *****/
publicintsize(){ return size;}
publicbooleanisEmpty(){ return size == 0; }
/***** 私有函数 *****/
privatebooleanisElementIndex(int index){ return index >= 0 && index < size; }
privatebooleanisPositionIndex(int index){ return index >=0 && index <= size; }
/* * 检查 index 索引位置是否可以存在元素 */ privatevoidcheckElementIndex(int index){ if (!isElementIndex(index)) thrownew IndexOutOfBoundsException("Index: " + index + ", Size: " + size); }
/* * 检查 index 索引位置是否可以添加元素,用于插入操作 * 对应的位置可以理解是数组元素间隔的缝隙,所以比元素个数多一个 * 插入时要保证插入后数组中的数据依然是连续存储的,中间不能有NULL值,所以用size判断而不是length */ privatevoidcheckPositionIndex(int index){ if (!isPositionIndex(index)) thrownew IndexOutOfBoundsException("Index: " + index + ", Size: " + size); }
// 将数组 data 的容量改为 newCap privatevoidresize(int newCap){ // 若当前数组存储的元素个数大于 newCap,则不做修改,防止数据丢失 if (size > newCap) { return; } E[] tempData = (E[]) new Object[newCap];
for (int i = 0; i < size; i++) { tempData[i] = data[i]; } // System.arraycopy(data, 0, tempData, 0, size); data = tempData; }
@Override public Iterator<E> iterator(){ returnnew Iterator<E>() { privateint p = 0;
@Override publicbooleanhasNext(){ return p != size; }
@Override public E next(){ return data[p++]; } }; }