首页  |  数字信息资讯  |  数字信息化  |  数字信息平台  |  数字信息技术  |  数字信息发展  |  数字信息查询 

 
当前位置: 数字信息查询网 > 数字信息查询 > 正文

 一、介绍

先回顾一下List的框架图

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

由图中的继承关系,可以知道,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进行详细的分析。

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

得到的结果如下

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

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

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

读取:ArrayList > Vector > Stack > LinkedList

插入:LinkedList > Vector > ArrayList > Stack

删除:LinkedList > Vector > ArrayList > Stack

三、插入的分析

LinkedList

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

从中,我们可以看出:通过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

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

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

四、查找的分析

LinkedList

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

从中,我们可以看出:通过get(int index)获取LinkedList第index个元素时。先是在双向链表中找到要index位置的元素;找到之后再返回。

双向链表查找index位置的节点时,有一个加速动作:若index < 双向链表长度的1/2,则从前向后查找; 否则,从后向前查找。

ArrayList

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

我们可以看到ArrayList直接返回数组中index位置的元素,而不需要像LinkedList一样进行查找。

通过源码发现Vector和Stack的操作方式和ArrayList一样,这里就不详细分析了。

五、删除的分析

LinkedList

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

交给gc完成资源回收,删除操作结束。

与ArrayList比较而言,LinkedList的删除动作不需要“移动”很多数据,从而效率更高。

ArrayList

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

恩,又是调用了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(实现动态数组),都慢,被ArrayList替代。长度任意延长。线程安全(同步的类,函数都是synchronized)

Stack(实现堆栈)继承于Vector,先进后出。

所以,快速访问ArrayList,快速增删LinkedList,单线程都可以用,多线程只能用同步类Vector


关闭窗口
· Java中ArrayList、LinkedList、 11-07
· 灾难恢复测试策略是成功 11-07
· RPA大本事:已成BPA策略落 11-07
· 支付勒索软件前需要回答 11-01
· Java高可用集群架构与微 11-01
· 在技术团队里,如何达成 11-01
· 不吹不黑,这个算法,你 11-01
· 线程、多线程和线程池, 11-01
· 来吧,说说你眼中的微服 11-01
· 这个坑,你在研发管理的 10-29
本站文章点击TOP
· 数字21点技 2015-12-14
· 政府定制版 2016-03-30
· Forrester:发 2016-06-01
· 699元手机也 2016-06-19
· 践行大众创 2017-01-01
· 2016网智会 2017-01-10

辽ICP备11011476号-8 版权所有
ICP备案号:辽ICP备11011476号-8