2.2 数组列表
对于java程序员来说，数组列表可能是用得最多的了，对于年限比较高的程序员来说，ArrayList都写吐了，哈哈。数组列表的出现是为了克服链表的一些缺点而诞生的。链表这个数据结构虽然好用，但是也存在一个最重要的缺点，就是按索引访问比较慢，需要按照引用或者指针去循环检索。为此，才有了数组列表。数组列表内部实现是一个数组，内部有个字段记录最后一个元素所在的数组索引。添加元素直接在在这个位置后添加。当数组满了的时候就对数组进行扩容。
扩容的方法是长度加一然后翻倍。
但是数组列表，也有缺点，就是从头部删除，需要将所有元素前移，性能十分低下。
其数据字段如下图
数组列表代码比链表简单，我这里贴一下Java代码：
public class ArrayList { private Object[] data = new Object[0]; private int index; public void addLast(T value) { ensureCapacity(); data[index++] = value; } public T removeLast() { return (T) data[index--]; } public void addFirst(T value) { ensureCapacity(); System.arraycopy(data, 0, data, 1, index); data[0] = value; index++; } public T removeFirst() { T temp = (T) data[0]; System.arraycopy(data, 1, data, 0, data.length - 1); index--; return temp; } public T get(int index) { return (T) data[index]; } private void ensureCapacity() { if (index >= data.length) { Object[] array = new Object[(data.length + 1) << 1]; System.arraycopy(data, 0, array, 0, data.length); data = array; } }}同样，对于数组列表，不建议自己实现，而是建议使用各个语言官方库里的实现。比如java有ArrayList实现。
