基本概念
数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
随机访问时间复杂度O(1),添加和删除时间复杂度O(n)。
添加和删除最好的情况是添加和删除最后一位，时间复杂度O(1)，最坏情况，移动整个数组，时间复杂度O(n)。
插入和删除改进思想
插入
如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移k之后的数据。
但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。
假设数组 a[10]中存储了如下 5 个元素：a，b，c，d，e。
我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5]，将 a[2]赋值为 x 即可。最后，数组中的元素如下： a，b，x，d，e，c。
这种插入方式会将O（n）降到O（1）
删除
复杂度与插入完全一致
数组 a[10]中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。
我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
内存寻址公式
对于一维长度为k的数组，a[k]的地址为：
a[k]_address = base_address + k * type_size
对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：
address = base_address + ( i * n + j) * type_size
ArrayList源码
添加
添加元素到尾部
public boolean add(E e) {
// 数组大小是否足够，不够就扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 直接赋值
elementData[size++] = e;
return true;
}
扩容代码
1. 初始化数组大小时，是否有给定初始值，以给定的大小为准，没有给默认扩容到10.
2. 期望的最小容量大于当前数组的长度，那么就扩容。
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 扩容后的数组容量是原先的1.5倍，扩大了1/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容后的容量依然小于期望的最小容量，那么扩容后的值就等于期望值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就用 Integer 的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 将原先数组的值拷贝到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
在指定位置添加元素
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
/**
* @param src 被拷贝的数组
* @param srcPos 从数组那里开始
* @param dest 目标数组
* @param destPos 从目标数组那个索引位置开始拷贝
* @param length 拷贝的长度
* 此方法是没有返回值的，通过 dest 的引用进行传值
*/
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
删除
给定要删除的元素的index
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
// index之后的全部数据往前移一位
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 最后一位置空，方便垃圾回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
给定要删除的元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//和上面的remove(int index)处理方式基本一致
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
迭代器
用的三个方法：
hasNext 还有没有值可以迭代
next 如果有值可以迭代，迭代的值是多少
remove 删除当前迭代的值
hasNext
public boolean hasNext() {
//cursor 表示下一个元素的位置，size 表示实际大小，如果两者相等，说明已经没有元素可以迭代了，如果不等，说明还可以迭代
return cursor < limit;
}
next
public E next() {
// 注意这个，由上面源码可知，修改和删除都会引起modCount变化
// 如果在迭代器遍历的时候对集合进行修改就会报错
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 本次迭代元素的索引值
int i = cursor;
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 为下一次迭代做准备
cursor = i + 1;
return (E) elementData[lastRet = i];
}
remove
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
try {
// 通过给定index删除元素
ArrayList.this.remove(lastRet);
cursor = lastRet;
// 防止重复删除元素
lastRet = -1;
// 删除元素时 modCount 的值已经发生变化，在此赋值给 expectedModCount
// 这样下次迭代时，两者的值是一致的了
expectedModCount = modCount;
limit--;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
