Java源码学习--ArrayList、LinkedList、Vector比较

在进行三个的总结之前，还有一个需要了解一下的就是Stack这个类。

一、Stack

这个类继承了Vector，而且该类只是提供了栈操作的方法，没有其他任何的东西：

public class Stack<E> extends Vector<E> {

public Stack() {
}

public E push(E item) {
    addElement(item);

    return item;
}

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

public boolean empty() {
    return size() == 0;
}

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

private static final long serialVersionUID = 1224463164541339165L;

}

二、ArrayList、LinkedList、Vector比较

1. ArrayList

1.1 add方法

ArrayList的add系列的方法的实现逻辑为：

• 检查index是否合法(不是每种add方法都会，当add时指定index时才会有这一步)
• 检查size+1时是否到达了容量上限，即是否需要扩容
• 将index后面的元素通过System.arraycopy方法向后移动一个位置
• 执行元素的添加，在ArrayList中这一步只是一个数组某一位置的赋值操作

由于ArrayList中维护的是一个数组，而数组根据下标的操作的时间复杂度都是O(1)所以ArrayList的add方法几乎是没有耗时的，当调用在指定位置添加的方法时由于需要把index后面的元素向后移动一格而调用了System.arraycopy方法，会产生一些耗时,当遇到需要扩容时由于执行了Arrays.copyof方法，此时需要一些耗时

1.2 addAll方法

ArrayList的addAll系列方法的实现逻辑为：

• 检查index是否合法(不是每种addAll方法都会，当addAll时指定index时才会有这一步)
• 通过toArray方法将方法参数的Collection对象转化为数组类型
• 检查size+newLength时是否到达了容量上限，即是否需要扩容
• 将index后面的元素通过System.arraycopy方法向后移动newLength个位置
• 执行元素的添加，在ArrayList中也是通过System.arraycopy方法实现的

在ArrayList的addAll方法中，和add相比，多执行了一次System.arraycopy方法，多出的耗时就是在这里。

1.3 remove方法

ArrayList的remove(int index)方法实现逻辑为：

• 检查index是否小于当前的size
• 将index后面的元素通过System.arraycopy方法向前移动一个位置
• 执行元素的删除，在ArrayList中这一步只是将数组中下标为size的元素赋值为null

可见ArrayList的删除执行位置的方法，唯一耗时的就是向前移动元素。

ArrayList的remove(Object o)方法的实现逻辑为：

• 通过for循环找到(通过equals方法进行判断)需要删除的元素的位置position
• 调用fastRemove(position)执行删除，该方法的实现几乎和remove(index)是一样的

直接删除对象的方法更加耗时，原因就在于多了一个for来寻找被删除对象的位置。

ArrayList中还有一个removeAll的方法，其作用是将参数集合中所有的元素都从ArrayList中删除；该方法效率很低下，就是对于参数中的每一个元素ArrayList都要调用contains方法来判断是否含有该元素，关键是contains方法的实现就是一个for循环遍历ArrayList中是所有元素，所以removeAll的复杂度为O(n^2)

1.4 get和set方法

ArrayList的get和set就是一个数组根据下标来查找元素的方法，所以没任何毛病；不过发扬传统，在执行数组的写和读的操作之前还是要检查一下index的合法性问题。

2. LinkedList

2.1 add方法

LinkedList的add方法就是一个双向链表的插入方法，其逻辑为：

• 首先找到index位置对应的节点(在指定插入位置时，通过for循环中计数得到)
• 执行节点的插入

LinkedList方法的插入和ArrayList相比会慢一些，首先是节点的插入肯定比不上数组根据下标进行读写，其次是虽然指定添加位置时ArrayList需要将index后面的元素拷贝一下，但是LinkedList中却需要找到index位置的节点，所以前者耗时在后续数据的移动，而后者耗时在index位置节点的获取，这么一比还是ArrayList占据了上风；但是LinkedList有一个优点就是没有需要扩容的情况。

2.2 addAll方法

LinkedList的addAll方法的逻辑为：

• 首先找到index位置对应的节点(在指定插入位置时，通过for循环中计数得到)
• 对参数的Collection对象中的元素通过for循环挨个进行节点的加入

额，这个方法好像没啥好说的。

2.3 remove方法

LinkedList的remove(Object o)方法的实现逻辑是：

• 一个for循环找到o对应的对象
• 执行节点的删除方法

可见该方法和ArrayList相比在找该对象时使用的都是for循环，在这一步上是势均力敌的(ArrayList稍微领先)，包括数据的删除都是ArrayList要由于LinkedList；但是ArrayList在删除数据之后还要把后面的数据整体向前移动一个位置，而LinkedList则没有这一步。

LinkedList的remove(int index)方法的实现逻辑是：

• 首先通过for循环找到index对应的节点
• 执行节点的删除方法

LinkedList的该方法和ArrayList相比就没有多大的优势了，因为ArrayList通过index删除时根本不需要通过for循环，直接一个数组的根据下标操作数据秒杀LinkedList，但是ArrayList还是有一个后续数据的前移的工作要做，因此这个方法ArrayList以微弱优势取胜。

2.4 get和set方法

LinkedList的get和set方法就都很惨了，因为只要涉及到指定了位置index，那LinkedList就只能通过for遍历来找到，所以这里相较于ArrayList直接通过数组的下标操作数据，LinkedList通过for循环找到数据变完全被秒杀了。

3. Vector

由于Vector和ArrayList几乎是一样的实现，这里就不在进行对比了。

三、总结

看完了List系列的源代码，虽然这些源代码确实很简单易懂，但是还是有很多能够学习的：

• 良好的习惯：涉及到index的操作，可以看到所有的方法第一件做的是就是检查index的合法性，这等细节却能反应很多东西；在各种面试的书集中，都会说到考虑要完善，考虑到特殊情况等，这都是在考验我们的严谨性
• 主动释放资源：在涉及到删除的操作时，特别是批量的删除，源代码中都会有一个将被删除的位置或者区间的元素赋值为null的操作，并且代码中通常会有注释：// clear to let GC do its work；这也是一个好的习惯，“不要以为我的size属性会卡主操作者他不会访问到那些数据，我干嘛要去删除”