先回顾一下List的框架图
由图中的继承关系,可以知道,ArrayList、LinkedList、Vector、Stack都是List的四个实现类。
在对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
在这里面有一个非常耗时的操作
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
我们可以看到ArrayList直接返回数组中index位置的元素,而不需要像LinkedList一样进行查找。
通过源码发现Vector和Stack的操作方式和ArrayList一样,这里就不详细分析了。
LinkedList
由于删除了某一节点因此调整相应节点的前后指针信息,如下:
e.previous.next = e.next;//预删除节点的前一节点的后指针指向预删除节点的后一个节点。 e.next.previous = e.previous;//预删除节点的后一节点的前指针指向预删除节点的前一个节点。
清空预删除节点:
e.next = e.previous = null; e.element = null;
交给gc完成资源回收,删除操作结束。
与ArrayList比较而言,LinkedList的删除动作不需要“移动”很多数据,从而效率更高。
ArrayList
恩,又是调用了System.arraycopy。
操作ArrayListLinkedListVectorStack读取O(1)O(n)O(1)O(1)插入O(n)O(1)O(n)O(n)删除O(n)O(1)O(n)O(n)
所以,快速访问ArrayList,快速增删LinkedList,单线程都可以用,多线程只能用同步类Vector