声明：本文使用JDK1.8
先看下List在Collection中的框架图：
image
这次的源码是基于Java8的。
ArrayList源码分析
大家基本都知道ArrayList的底层是数组的数据结构，下面来看下它的随机访问、删除等的源码：
private static final int DEFAULT_CAPACITY = 10;//初始容量为10
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//ArrayList扩容函数方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 计算当前ArrayList大小
int oldCapacity = elementData.length;
//这里我们可以看出，ArrayList每次扩容是增加50%，oldCapacity >> 1是指往左移一位，也就是除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
//根据下标index获取元素值
public E get(int index) {
rangeCheck(index);//检查小标是否越界
return elementData(index);
}
//将index位置的值设为element，并返回原来的值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//向数组中末尾增加一个元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//向指定位置index处增加element
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index以及index之后的数据复制到index+1的位置往后，即从index开始向后挪了一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//根据指定的index，删除元素
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源码分析
来看下LinkedList的部分源码，底层是基于双向链表的数据结构。
定义：
package java.util;public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
}
方法：
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {//如果index<(size/2),则从前找
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;
}
}
//直接删除某个元素
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//根据下标查询某个元素
public E get(int index) {
checkElementIndex(index);//检查下标是否越界
return node(index).item;//可以看第一个node的方法，其中有查询
}
//设置index位置处的值为element
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//在下标index位置处新增element
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)//index是末尾，则在末尾新增一个
linkLast(element);
else //这里的插入需要先去查询相应的位置，这会导致性能降低
linkBefore(element, node(index));
}
ArrayList和LinkedList区别
平时在看博客的时候，网上很多博客都说，ArrayList基于数组的数据机构，LinkedList是基于链表的数据结构，所以有以下几种特性：
1、对于随机查询，ArrayList比LinkedList快
2、对于插入或者删除，LinkedList由于是链表，所以是比ArrayList性能更好。
通过两者的源码比较，我们发现对于随机查找，ArrayList直接根据下标index查询相对于的值，而LinkedList虽然源码对其做了部分优化，index小于（size/2）,从前往后找，否则从后往前找，即使这样，还是ArrayList比LinkedList快。
下面通过实际代码来看下插入的性能比较。
public class ListTest {
public static void main(String[] args) {
List<Integer> array = new ArrayList<Integer>();
List<Integer> linked = new LinkedList<Integer>();
//首先分别给两者插入10000条数据
for (int i = 0; i < 10000; i++) {
array.add(i);
linked.add(i);
}
//获得两者随机访问的时间
System.out.println("array time:" + getTime(array));
System.out.println("linked time:" + getTime(linked));
//获得两者插入数据的时间
System.out.println("array insert time:" + insertTime(array));
System.out.println("linked insert time:" + insertTime(linked));
}
//插入数据
public static long insertTime(List<Integer> list) {
/*
* 插入的数据量和插入的位置是决定两者性能的主要方面，
*/
long num = 10000; //表示要插入的数据量
int index = 700; //表示从哪个位置插入
long time = System.currentTimeMillis();
for (int i = 1; i < num; i++) {
list.add(index, i);
}
return System.currentTimeMillis() - time;
}
public static long getTime(List<Integer> list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
int index = Collections.binarySearch(list, list.get(i));
if (index != i) {
System.out.println("ERROR!");
}
}
return System.currentTimeMillis() - time;
}
}
这个是运行时间:
array time:5
linked time:315
array insert time:15
linked insert time:17
这里我们可以看出，对于大数据的随机查询，ArrayList比较快。但是对于插入和删除，并不是和上面讲的一样，这里反而ArrayList比较快。在数据量不是很大的时候，两者的插入性能相差不大，但是对于很大的数据，在插入数据量很大的时候，我自己从100开始，每次往上加100，测试发现，在700左右，ArrayList的性能就比LinkedList好了，而且数据量越大，ArrayList的性能越明显，而在这个之前尤其是index比较小的时候，性能相对来说LinkedList比较好。不过，测试的时候两者插入时间有波动，不是很稳定。
不过我们从源码比较知道LinkedList性能比较差的原因是因为在中间插入的时候，性能耗在了查询相应的位置上面了，如果只是直接在首插入的话，性能还是ArrayList快。
