动态数组
数组的容量可以动态伸缩，当新元素装不下时，就把数组的容量扩大；当元素太少时，就把数组容量缩小；扩容和缩容的实现是通过新建一个更大或更小的数组，把现有数组复制到新数组中，并用新数组代替现有数组。
扩容
- 扩容的策略是：添加元素时，如果容量已满，就将容量扩大一倍；
// 在index索引的位置插入一个新元素e
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
if(size == data.length)
resize(2 * data.length);
for(int i = size - 1; i >= index ; i --)
data[i + 1] = data[i];
data[index] = e;
size ++;
}
// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
}
缩容
- 缩容的策略是：删除元素后，如果元素个数是容量一半时，将容量缩小一半；
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret = data[index];
for(int i = index + 1 ; i < size ; i ++)
data[i - 1] = data[i];
size --;
data[size] = null; // loitering objects != memory leak
if(size == data.length / 2)
resize(data.length / 2);
return ret;
}
存在的问题
由于扩容和缩容的因子都是 1/2，会出现当在 1/2 处交替增删元素时，都要进行 resize 操作；解决方案是，把缩容的因子调整为 1/4，即当元素的个数为容量的 1/4 时，将容量索为 1/2，由 eager 变为 lazy；
