源码上分析ArrayList/LinkedList的性能
环境：
JDK8
概述：
ArrayList底层是一个数组，数组有容量限制，超出限制时会增加50%容量，默认第一次插入元素时创建大小为10的数组。
LinkedList底层维护一个Node的双向链表
参考其内部类Node<E>
private static class Node<E> { E item; //当前元素 Node<E> next; //前驱元素 Node<E> prev; //后继元素 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
源码分析：
add向末尾追加元素
ArrayList 核心是add之前判断数组容量，当数组容量不足时，会进行扩容
public boolean add(E e) { // 确定ArrayList的容量大小 必要时进行扩容 // 注意：size + 1，保证资源空间不被浪费， //按当前情况，保证要存多少个元素，就只分配多少空间资源 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * 私有方法：明确 ArrayList 的容量，提供给本类使用的方法 * - 用于内部优化，保证空间资源不被浪费：尤其在 add() 方法添加时起效 * @param minCapacity 指定的最小容量 */ private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { // 将“修改统计数”+1，该变量主要是用来实现fail-fast机制的 modCount++; // 防止溢出代码：确保指定的最小容量 > 数组缓冲区当前的长度 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * 私有方法：扩容，以确保 ArrayList 至少能存储 minCapacity 个元素 * - 扩容计算：newCapacity = oldCapacity + (oldCapacity >> 1); 扩充当前容量的1.5倍 * @param minCapacity 指定的最小容量 */ private void grow(int minCapacity) { // overflow-conscious code //防止溢出代码 int oldCapacity = elementData.length; // 运算符 >> 是带符号右移. 如 oldCapacity = 10,则 newCapacity = 10 + (10 >> 1) = 10 + 5 = 15 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) // 若 newCapacity 大于最大存储容量，则进行大容量分配 newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
LinkedList 核心是在新建Node后会修改相邻Node的next及prev
public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } /** * 将其作为尾节点 * Links e as last element. */ void linkLast(E e) { //将新加节点的前驱指向last节点 final java.util.LinkedList.Node<E> l = last; //创建节点(前驱是last节点，元素为e，后继为null节点) final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(l, e, null); //将last节点修改为指向新节点 last = newNode; //判断新节点的前节点(就是以前的last节点)是不是为空 if (l == null) //如果新节点的前节点为空， // 说明这个list集合是一个空集合，这个新加节点是添加的第一个节点， //将first节点修改为指向新节点 first = newNode; else //如果新节点的前节点不为空 //说明这个list集合有元素 //将前节点的后继修改为新节点 l.next = newNode; size++; modCount++; } /** * //在指定节点前插入节点，节点succ不能为空 * Inserts element e before non-null Node succ. */ void linkBefore(E e, java.util.LinkedList.Node<E> succ) { // assert succ != null; final java.util.LinkedList.Node<E> pred = succ.prev;//取出指定节点的前驱节点 //新建一个以指定节点为后继节点，指定节点的前驱节点为前驱节点的节点 final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, succ); //修改指定节点的前驱为新节点 succ.prev = newNode; if (pred == null) //如果指定节点为first节点 first = newNode; else //将指定节点的后节点指向新节点 pred.next = newNode; size++; modCount++; }性能比较：
ArrayList如果不考虑扩容的情况，效率和LinkedList不会有太大差别，当然一旦数组容量不足须要扩容时，ArrayList会将old array copy至扩容后的new array，ArrayList的初始数组大小为10，所以在大批量的add操作中，性能会比LinkedList差。
Add 向指定位置添加元素
ArrayList 通过arraycopy方法实现指定位置之后的元素向后顺移一位
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
LinkedList 和末位追加没太大区别，同样是修改相邻Node的next及prev
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * Returns the (non-null) Node at the specified element index. */ java.util.LinkedList.Node<E> node(int index) { // assert isElementIndex(index); // 判断位置在链表前半段或者是后半段 if (index < (size >> 1)) { java.util.LinkedList.Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { java.util.LinkedList.Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }性能比较：
一目了然，ArrayList每次添加元素后，须要对后面的元素依次顺移一位，效率上和LinkedList没法比
get元素
ArrayList直接按数组下标访问元素，性能上没有多余损耗
public E get(int index) { rangeCheck(index); return elementData(index); } E elementData(int index) { return (E) elementData[index]; }
LinkedList 须要遍历链表中的元素
public E get(int index) { checkElementIndex(index); return node(index).item; }
性能比较：由于ArrayList直接按数组下标访问元素，性能上没有多余损耗，在get元素上的效率比LinkedList高
remove元素
和Add一样，ArrayList在remove（末位移除除外）之后须要对后面的元素下标进行变更
public E remove(int index) { rangeCheck(index); modCount++; 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; }
LinkedList 始终只是修改相邻Node的next及prev
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(java.util.LinkedList.Node<E> x) { // assert x != null; final E element = x.item; final java.util.LinkedList.Node<E> next = x.next; final java.util.LinkedList.Node<E> prev = x.prev; 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; size--; modCount++; return element; }
性能比较：
同向指定位置添加元素一样，ArrayList还要copy一份新的数组，性能上和LinkedList没法比
总结：
ArrayList内部维护一个数组，末位追加元素和get元素的性能很客观，但是在指定位置上进行添加移除操作上的性能较LinkedList差。
LinkedList是一个双向链表，不管是添加抑或是移除，额外操作只是修改相邻元素，性能强大，但是get元素须要遍历获取，性能上较ArrayList差。
ArrayList强在读数据，LinkedList强在写数据，如果集合仅需要读取或者不涉及大批量元素的添加，以及不涉及大批量对中间元素的添加移除操作，建议使用ArrayList，其余情况建议使用LinkedList。