前言

List家族常用的类有3个，ArrayList、LinkedList、Vector。

ArrayList和Vector的底层是基于数组实现的，LinkedList的底层是基于链表实现的。

三者的比较如下：

ArrayList和LinkedList不是线程安全的，Vector是线程安全的。
对于随机访问（get和set），ArrayList的性能要优于LinkedList。
对于add和remove操作，LinkedList和ArrayList性能差距不是很大。
三者均实现了Collection接口。

分析

UML图

三者与其他类的继承实现关系UML图如下。

ArrayList：

LinkedList：

Vector：

源码分析

核心实现

ArrayList是基于数组实现。

1 2	transient Object[] elementData; private int size;

LinkedList是基于链表实现。

1
2
3

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

Vector是基于数组实现。

1
2
3

protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;

核心参数

ArrayList 可以设置初始大小（由于数组实现的原因），不设置默认为10。

LinkedList不需要设置参数（由于使用链表实现，无界）。

Vector不仅可以设置初始大小，还可以设置容量增幅。

//ArrayList传参构造函数
  public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
   }
   //LinkedList构造函数
   public LinkedList() {
   }
  //Vector传参构造函数 
   public Vector(int initialCapacity, int capacityIncrement) {
       super();
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       this.elementData = new Object[initialCapacity];
       this.capacityIncrement = capacityIncrement;
   }

关于初始化大小和扩容机制下面讲。

核心方法

我们主要分析get、set、add、remove这几个方法。对于ArrayList和Vector，还要分析扩容方法。

get、set方法

ArrayList get，set方法：

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}
public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

Vector get，set方法：

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

二者的逻辑一样，get方法判断是否下标越界，不越界返回index下的数值。set方法判断是否越界，不越界将新值放到指定下标上。它俩的区别在与synchronized关键字，正好说明了Vector是线程安全的。

LinkedList get，set方法：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
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的get方法会先检查是否越界，不越界返回指定下标node的item值。
set方法也是先检查越界情况，不越界将该点的node的item赋为新值。取node指定位置上的值时要循环遍历，所以对于随机的get，set，ArrayList的性能要优于LinkedList的。

add、remove方法

ArrayList add、remove方法：

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}
public E remove(int index) {
    Objects.checkIndex(index, size);

    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;
}

Vector add、remove方法：

public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    elementCount = s + 1;
}
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

它们里面有add、remove方法不止一个，我们只拿一个来举例。

可以看到，Vector和ArrayList十分相近了，除了synchronized关键字。

add方法当elementData.length和elementCount相等时（容量满），会执行扩容操作，并将元素放到指定位置。

remove方法先判断下标是否越界，不越界会删除指定位置的元素，并且将数组重新拷贝合并。

同时它们有一个计数器modCount，在HashMap那边已经讲过，是用来fast-fail的，当多个线程同时操作，modCount不一致，就会抛出异常。

LinkedList的add、remove方法：

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
 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;
    size++;
    modCount++;
}
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final 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;
}

可以看到，LinkedList的add方法开始也会校验指针位置，然后如果在末尾，就在链表最后面添加节点，否则就插入到链表指定位置上。

remove方法校验指针位置后，会删除指定位置上的node。

上面可以看到，对于add和remove，ArrayList数组要进行扩容或者删除部分长度，执行Sysetm.arraycopy方法，这是要消耗一些性能的，对于LinkedList，不需要维护容量问题，但是每次新增或者删除时，都会创建或删除一个Node对象，也是要消耗一些性能的。

扩容方法

对于ArrayList或者Vector，扩容方法如下：

ArrayList 扩容方法：

private static final int DEFAULT_CAPACITY = 10;
   private int newCapacity(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity <= 0) {
           if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
               return Math.max(DEFAULT_CAPACITY, minCapacity);
           if (minCapacity < 0) // overflow
               throw new OutOfMemoryError();
           return minCapacity;
       }
       return (newCapacity - MAX_ARRAY_SIZE <= 0)
           ? newCapacity
           : hugeCapacity(minCapacity);
   }
   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE)
           ? Integer.MAX_VALUE
           : MAX_ARRAY_SIZE;
   }

Vector扩容方法：

public Vector() {
       this(10);
   }
   private int newCapacity(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                        capacityIncrement : oldCapacity);
       if (newCapacity - minCapacity <= 0) {
           if (minCapacity < 0) // overflow
               throw new OutOfMemoryError();
           return minCapacity;
       }
       return (newCapacity - MAX_ARRAY_SIZE <= 0)
           ? newCapacity
           : hugeCapacity(minCapacity);
   }

   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }

上面代码可以看到，对于ArrayList，如果不传入初始容量，默认为10。容量达到最值，执行扩容，每次扩容 int newCapacity = oldCapacity + (oldCapacity >> 1);

默认原容量的1.5倍。

Vector，如果不传入初始容量和自增容量，默认初始容量也为10.扩容时执行
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);

默认为原容量的2倍。

两者的最大值容量均为Integer.MAX_VALUE.

LinkedList由于是链表实现，没有容量限制。无需扩容。

代码

我们从代码的角度比较下ArrayList和LinkedList，Vector。

我们构建一个有200W数据的ArrayList和LinkedList。

public static void main(String[] args){
    List<Integer> list = new ArrayList();
    //List<Integer> list = new LinkedList<Integer>();
    //Vector<Integer> list=new Vector<>();
    for (int i = 0; i < 2000000; i++) {
        list.add(i);
    }

    Integer tmp;
    long start=System.currentTimeMillis() ;   //ForEach
    for(Integer s:list){
        tmp=s;
    }
    System.out.println("foreach spend:"+(System.currentTimeMillis()-start));
    start = System.currentTimeMillis();
    for(Iterator<Integer> it = list.iterator(); it.hasNext();){
        tmp=it.next();
    }
    System.out.println("Iterator spend;"+(System.currentTimeMillis()-start));
    start=System.currentTimeMillis();
    int size=list.size();
    for(int i=0;i<size;i++){
        tmp=list.get(i);
    }
    System.out.println("for spend;"+(System.currentTimeMillis()-start));
}

某一次的结果：

数组	forEach遍历	Iterator遍历	for遍历
ArrayList	9ms	9ms	12ms
LinkedList	17ms	16ms	???
Vector	44ms	55ms	41ms

由于for循环遍历是随机访问，故LinkedList在数据量很大的情况下时间消耗会很长，基本不能接受。由于Vector线程安全，synchronized，故其整体效率会比ArrayList低些。在实际开发中，应用的ArrayList还是比较多的。

结语

以上就是对ArrayList、LinkedList、Vector的全部分析。对于不同的应用场景，合理的选择List的类型也是至关重要的。三种List都是比较基础的知识，应当学习和掌握。

SakuraTears的博客

ArrayList、LinkedList和Vector分析

前言

分析