前言：在前面我们提到数据结构的线性表表。那么今天我们详细看下Java源码是如何实现线性表的，这一篇主要讲解顺序表ArrayList链式表下一篇在提及。
1：ArrayList结构图
2：关于Collection和List的区别
最好的比对就是查看他们的源码我们先看Collection的所有接口
public interface Collection<E> extends Iterable<E> { int size(); boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray(); <T> T[] toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean retainAll(Collection<?> c); void clear();
boolean equals(Object o); int hashCode();
}
在看List接口
public interface List<E> extends Collection<E> {
int size(); boolean isEmpty();
Iterator<E> iterator();
Object[] toArray(); <T> T[] toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean addAll(int index, Collection<? extends E> c); boolean removeAll(Collection<?> c); boolean retainAll(Collection<?> c); void clear(); boolean equals(Object o); int hashCode();
E get(int index);
E set(int index, E element); void add(int index, E element);
E remove(int index); int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
}
由于List是继承Collection，所有具有Collection所有的功能，从Collection接口中我们也可以看出，Collection不具有索引，不可以取元素的值，而List取可以，List是具有索引的，这样一来在获取元素方面远远好于Collection。
3：Iterable接口
从ArrayList中我们可以看出，最顶端的接口就是Iterable这个接口，这个是一个迭代器，接口如下
public interface Iterable<T> {
Iterator<T> iterator();
}这个接口主要是返回一个对象，这个对象是Iterator，那么我们在看看Iterator接口里面的方法
public interface Iterator<E> { boolean hasNext();
E next(); void remove();
}那么我们主要看ArrayList是如何实现迭代器Iterator的。Iterator的实现在AbstractList这个抽象类中的一个私有类Itr中。我们看看具体实现
private class Itr implements Iterator<E> { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; public boolean hasNext() { return cursor != size();
}
cursor：记录即将调用索引的位置
lastRet：最后一个元素的索引
modCount后面会单独说下。 判断这个集合是否存在最后一个元素，通过cursor != size();size表示数组的长度，因为数组中元素索引从0开始，所以当最后一个索引等于数组长度的时候说明已经到数组的尾部了。
public E next() {
checkForComodification(); try {
E next = get(cursor);
lastRet = cursor++; return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification(); throw new NoSuchElementException();
}
}
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException();
}modCount：记录所有数组数据结构变动的次数，包括添加、删除、更改等，为了避免并发时候，当多个线程同时操作时候，某个线程修改了数组结构，而另一个线程恰恰读取这个数组，这样一来就会产生错误。所以在这段代码中加入了modCount != expectedModCount，比如A线程对数据结构修改一次，那么modCount比如+1，而expectedModCount并没有发生变化，所以这样就会抛出异常。
public void remove() { if (lastRet == -1) throw new IllegalStateException();
checkForComodification(); try {
AbstractList.this.remove(lastRet); if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException();
}
}
我们刚刚说了lastRet记录的是最后一个元素，所以删除的时候直接按照索引删除即可，因为modCount会减一，所以重新对expectedModCount 进行赋值，避免遍历时候产生错误。而且把lastRed在次赋初始值。
4：分析ArrayList
刚刚目的是为了更加连接ArrayList做个铺垫，ArrayList和我们以前数据结构中提到的顺序表一样，采用Object[] 数组进行存储元素，用size来记录元素的元素的个数。
/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. */ private transient Object[] elementData; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
关于transient，一旦变量被transient修饰，变量将不再是对象持久化的一部分，那么为啥采用transient修饰呢，由于elementData本身是一个缓存数组，通常会预留一些容量，当容量不够时然后进行扩充，比如现在elementData容量是10，但是只有5个元素，数组中的最后五个元素是没有实际意义的，不需要储存，所以ArrayList的设计者将elementData设计为transient，然后在writeObject方法中手动将其序列化，并且只序列化了实际存储的那些元素，而不是整个数组。我们看下writeObject方法
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject(); // Write out array length s.writeInt(elementData.length); // Write out all elements in the proper order.
for (int i=0; i<size; i++)
s.writeObject(elementData[i]); if (modCount != expectedModCount) { throw new ConcurrentModificationException();
}
}
关于ArrayList的初始化。ArrayList的设计者采用3种方式初始化。（默认数组容量是10）
public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity); this.elementData = new Object[initialCapacity];
} public ArrayList() { this(10);
} public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
trimToSize方法，这个方法可能我们好多人用的少，其实意义蛮大的，它主要把没用的容量去除掉，这样一来可以减少内存的开销
public void trimToSize() {
modCount++; int oldCapacity = elementData.length; if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}ensureCapacity方法，我们知道数组如果满了就会进行扩容，这个方法就是扩容的。
public void ensureCapacity(int minCapacity) {
modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) {
Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity)
newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
modCount就是增加因子，记录操作数组结构的次数，首先和容量进行比对，如果不够了进行扩容。这是Java1.6版本的就是在原来的基础上扩容1.5倍。1.7采用>>1也就是所有元素像右边移动一位然后加上原来的容量。其中
indexOf方法，这个方法是获取元素索引。通过索引然后进行查询元素
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i;
} else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i;
} return -1;
}
从中我们也可以看出ArrayList是支持null的插入的。同样采用的是循环遍历来进行查找，时间复杂的为n。
contains方法，验证数组是否包含某元素，直接通过indexOf验证返回值即可
public boolean contains(Object o) { return indexOf(o) >= 0;
}lastIndexOf方法，和indexOf相对，indexOf是从前往后，lastIndexOf是从后面往前查找如下
public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i;
} else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i;
} return -1;
}
toArray方法，就是把List转换成数组形式
public Object[] toArray() { return Arrays.copyOf(elementData, size);
}get和set方法，这个就很简单了大家看下就行
public E get(int index) {
RangeCheck(index); return (E) elementData[index];
} public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element; return oldValue;
}
RangeCheck方法是进行验证的，查询的索引不可以超过数组的长度如下
private void RangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size);
}add(E e)添加一个元素，这个采用尾插入，先验证容量，size+1是加入1个元素后长度，看原来数组容量是否够。
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e; return true;
}add(int index, E element)按照索引进行插入，第一个还是一样进行扩容，然后把索引index后面的元素全部向后面移一位。System.arraycopy(elementData, index, elementData, index + 1,
size - index);的意思就是将elementData的第index个元素移到第index+1个元素上，长度为size-index。
public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
addAll(Collection<? extends E> c)
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew; return numNew != 0;
}
首先把集合c转换成a数组，然后计算要进行添加的数组长度，其它的基本和添加元素一致。arraycopy(Object src, int srcPos,Object dest, int destPos,int length)
参数次数依次 源数组，源数组起始位置，目标数组，目标数组起始位置，复制数组元素数目。
addAll(int index, Collection<? extends E> c)把数组插入到指定位置
public boolean addAll(int index, Collection<? extends E> c) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + size);
Object[] a = c.toArray(); int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
int numMoved = size - index; if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew; return numNew != 0;
}
首先判断是是否越界，然后和上面的基本一样，就是进行扩容判断，然后index后面的值进行后移包括index，然后留下的空间插入集合a。所以2次进行复制元素。
E remove(int index)和add相对，删除这个元素然后把index后面的元素往前面移一位size - index - 1其中-1是因为index这个元素会被删除，会少一位元素。
public E remove(int index) {
RangeCheck(index);
modCount++;延伸阅读
- ArrayList源码解析（二）自动扩容机制与add操作 2017-06-03 16:56:08.63
- JAVA常用集合源码解析系列-ArrayList源码解析（基于JDK8） 2017-05-06 16:24:13.3
学习是年轻人改变自己的最好方式