JAVA中ArrayList、LinkedList、Vector、Stack的比较 _JAVA

一、介绍先回顾一下List的框架图

文章插图

由图中的继承关系，可以知道，ArrayList、LinkedList、Vector、Stack都是List的四个实现类。

AbstractList是一个抽象类，它继承于AbstractCollection 。AbstractList实现List接口中除size()、get(int location)之外的函数。
AbstractSequentialList 是一个抽象类，它继承于AbstractList 。AbstractSequentialList 实现了“链表中，根据index索引值操作链表的全部函数” 。
ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。
LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率低。
Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。
Stack 是栈，它继承于Vector 。它的特性是：先进后出(FILO, First In Last Out) 。

二、性能测试在对ArrayList、LinkedList、Vector、Stack进行比较之前，我们先来对他们进行一个性能测试，结合源码和测试结果来对ArrayList、LinkedList、Vector、Stack进行详细的分析。

文章插图

文章插图

得到的结果如下

文章插图

根据结果，可以很明显的看出ArrayList、LinkedList、Vector、Stack的性能有很大的区别。

文章插图

读取：ArrayList > Vector > Stack > LinkedList
插入：LinkedList > Vector > ArrayList > Stack
删除：LinkedList > Vector > ArrayList > Stack
三、插入的分析LinkedList

文章插图

从中，我们可以看出：通过add(int index, E element)向LinkedList插入元素时。先是在双向链表中找到要插入节点的位置index；找到之后，再插入一个新节点。
双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。
ArrayList

文章插图

【JAVA中ArrayList、LinkedList、Vector、Stack的比较】在这里面有一个非常耗时的操作
System.arraycopy(elementData, index, elementData, index + 1, size - index);
该方法被标记了native，调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码。
该函数实际上最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。JAVA强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。
Vector

文章插图

可以看到Vector和ArrayList是一样的，都调用了System.arraycopy 。由于Stack和继承与Vector，就不仔细分析了。
四、查找的分析LinkedList

文章插图

从中，我们可以看出：通过get(int index)获取LinkedList第index个元素时。先是在双向链表中找到要index位置的元素；找到之后再返回。
双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。
ArrayList