本文共 6423 字，大约阅读时间需要 21 分钟。
ArrayList也叫数组列表，底层使用的数组实现的，严格来说是动态数组。
ArrayList工作原理其实很简单，底层是动态数组，每次创建一个ArrayList实例时会分配一个初始容量（如果指定了初始容量的话），以add方法为例，如果没有指定初始容量，当执行add方法，先判断当前数组是否为空，如果为空则给保存对象的数组分配一个最小容量，默认为10。当添加大容量元素额时候，会先增加数组的大小，以提高添加的效率。
由于ArrayList方法较多，对源码的分析选取了我们平时最常用的add、get和remove方法来分析。
add方法重载了多个实现，包括add(E e)和add(int index,E e)，由于没有指定插入的位置，每次插入操作会把元素放到数组的末尾，而这个过程只需要保证容量够用就行.
add(E e)
public boolean add(E e) { //保证数组的容量始终够用 ensureCapacityInternal(size + 1); //size是elementData数组中元组的个数，初始为0 elementData[size++] = e; return true;}private void ensureCapacityInternal(int minCapacity) { //如果数组没有元素，给数组一个默认大小，会选择实例化时的值与默认大小中较大值 if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //保证容量够用 ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) { //modCount是数组发生size更改的次数 modCount++; // 如果数组长度小于默认的容量10，则调用扩大数组大小的方法 if (minCapacity - elementData.length > 0) grow(minCapacity);}private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 在原来容量的基础上扩容2倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 新的容量大于数组最大值，则调用hugeCapacity() if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }private static int hugeCapacity(int minCapacity) { // 超过int最大数，发生大数溢出 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // 容量为int的最大值 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;} add(int index,E e)
public void add(int index, E element) { //判断index的值是否合法，如果大于size或者小于0则将抛出异常 rangeCheckForAdd(index); //保证容量够用，并修改modCount的值 ensureCapacityInternal(size + 1); //从第index位置开始，将元素往后移动一个位置 System.arraycopy(elementData, index, elementData, index + 1, size - index); //把要插入的元素e放在第index位置 elementData[index] = element; //数组元素的个数增加1 size++;} get方法最简单，首先判断该位置是否合法，如果合法则直接返回该位置的元素。
public E get(int index) { rangeCheck(index); return elementData(index);} 由于删除操作会改变size，所以每次删除都需要把元素向前移动一个位置，然后把原来最后一个位置的元素设置为null，一次删除操作完成。
public E remove(int index) { //判断index是否合法 rangeCheck(index); //remove操作会改变size，所以modCount加1 modCount++; //保存待删除位置的元素 E oldValue = elementData(index); //要移动的元素个数 int numMoved = size - index - 1; //如果index不是最后一个元素，则从第index+1到最后一个位置，依次向前移动一个位置 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index,numMoved); //元素的size减少1，并把原来末尾位置元素的值设置为null elementData[--size] = null; //返回index位置的值 return oldValue;} 注意到源码调用了System.arraycopy方法，该方法是native的，即该代码是其他语言编写，但Java允许与其进行交互（详情请搜索JNI），那么该方法是如何让实现的呢？
//add方法的System.arraycopy()//把从第i位置的元素开始到最后一个元素，都往后移动一个位置for(int j = size - 1; j > i; j--){ elements[j] = elements[j-1];}//把第i位置的值改为eelements[i] = e;//remove方法的System.arraycopy()方法//把从第i位置到最后一个位置，都向前移动一个位置for (int j = i; j < size - 1; j++) { elements[j] = elements[j + 1];}//把数组的元素个数减少1elements[--size] = null; LinkedList底层使用的双向链表，即每个节点既包含指向其后继的引用也包括指向其前驱的引用，LinkedList实现了List接口，继承了AbstractSequentialList类，在频繁进行插入以及删除的情况下效率较高。此外LinkedList还实现了Deque（继承自Queue接口）接口，可以当做队列使用。
默认添加到list的末尾，插入一个节点非常快，直接找到该位置的节点，修改节点的前驱以及后继的引用即可
public boolean add(E e) { //把e放在链表的最后一个位置 linkLast(e); return true;}// 在list末尾添加，修改相应引用void linkLast(E e) { //last是链表最后一个节点的引用，现在l也指向最后一个节点 final Node l = last; //调用Node(Node prev, E element, Node next)构造方法 final Node newNode = new Node<>(l, e, null); //last节点指向newNode last = newNode; //如果l为空，则链表为空，直接把newNode链接在首节点后面即可，否则把newNode链接//在l节点的后面 if (l == null) first = newNode; else l.next = newNode; //链表的元素个数增加1 size++; //modCount是链表发生结构性修改的次数（结构性修改是指发生添加或者删除操作） modCount++;} 获取index节点的值要从头或尾遍历链表，当数据量很大的时候，效率无疑是低下的。
public E get(int index) { //检查index是否合法 checkElementIndex(index); //如果合法就返回该节点位置的值 return node(index).item;}//获取index位置上的节点Node node(int index) { //断言index在链表中 // assert isElementIndex(index); //从第一个节点开始寻找直到index位置，然后返回index//位置的节点 if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //从最后一个节点开始往前寻找节点 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}//检查index值的合法性private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}//判断index是否存在于链表中private boolean isElementIndex(int index) { return index >= 0 && index < size;} public E remove(int index) { checkElementIndex(index); return unlink(node(index));}E unlink(Node x) { // assert x != null; //保存x节点的值 final E element = x.item; //保存x节点的后继 final Node next = x.next; //保存x节点的前驱 final Node prev = x.prev; //如果前驱为null，说明要移除的是第一个节点，把First指向下一个节点就行 if (prev == null) { first = next; } else { //否则，把x节点前驱的后继指向x的后继，并把x的前驱设置为null prev.next = next; x.prev = null; } //如果后继为null则要移除的是最后一个节点，则把last的引用指向x节点的前驱就ok if (next == null) { last = prev; } else { //否则，把x节点的后继的前驱设置为x节点的前驱，并x节点的后继设为null next.prev = prev; x.next = null; } //把x节点的值设为null，这样x就没有任何引用了，gc处理 x.item = null; //把链表的size减少1 size--; //结构性修改的次数增加1 modCount++; //返回x节点的值，在移除之前已经保存在element中了 return element;} 转载地址：http://zyxgi.baihongyu.com/