ArrayList 其实是一个动态数组，来看源码。
public class ArrayList<E> { /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size; }
1）elementData 是 Object 类型的数组，用来保存添加到 ArrayList 中的元素。如果通过默认构造参数创建 ArrayList 对象时，elementData 的默认大小是 10。当 ArrayList 容量不足以容纳全部元素时，就会重新设置容量，新的容量 = 原始容量 + (原始容量 >> 1)（参照以下代码）。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity);
}
>> 运算符还没有驾驭了。不过，通过代码测试后的结论是，当原始容量为 10 的时候，新的容量为 15；当原始容量为 20 的时候，新的容量为 30。
2） size 是 ArrayList 的元素个数。当往 ArrayList 添加一个元素时，size+1，删除一个元素时，size-1。
由于 LinkedList 和 ArrayList 底层实现的不同（一个双向链表，一个动态数组），它们之间的区别也很一目了然。
关键点1 ：LinkedList 在添加（add(E e)）、插入（add(int index, E element)）、删除（remove(int index)）元素的性能上远超 ArrayList。
为什么呢？先来看 ArrayList 的相关源码。
// ensureCapacityInternal() 方法内部会调用 System.arraycopy() public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } public E remove(int index) { E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; }
观察 ArrayList 的源码，就能够发现，ArrayList 在添加、插入、删除元素的时候，会有意或者无意（扩容）的调用 System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 方法，该方法对性能的损耗是非常严重的。
再来看 LinkedList 的相关源码。
/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; } /** * Unlinks non-null node x. */ E unlink(Node<E> x) { if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; return element; }
LinkedList 不存在扩容的问题，也不需要对原有的元素进行复制；只需要改变节点的数据就好了。
关键点2：LinkedList 在查找元素时要慢于 ArrayList。
为什么呢？先来看 LinkedList 的相关源码。
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
观察 LinkedList 的源码，就能够发现， LinkedList 在定位 index 的时候会先判断位置（是在 1 / 2 的前面还是后面），再从前往后或者从后往前执行 for 循环依次找。
再来看 ArrayList 的相关源码。
@SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
ArrayList 直接根据 index 从数组中取出该位置上的元素，不需要 for 循环遍历啊——这样显然更快！
