• 欢迎访问天天编码网站,Java技术、技术书单、开发工具,欢迎加入天天编码
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏天天编码吧
  • 我们的淘宝店铺已经开张了哦,传送门:https://shop145764801.taobao.com/

Java中ArrayList、LinkedList和Vector的联系与区别

Java基础 tiantian 2461次浏览 2个评论 扫描二维码

毫无疑问,List是一种非常基础的数据结构,翻译过来就是列表。正如它的名字所示,List表示的是一个有序(插入顺序)的元素序列。在Java的集合框架中,List是作为顶级接口Collection的直接子类接口存在,因此,List分支是集合框架中最简单、最常用的分支。

List概述

List分支作为集合框架中最简单、最常用的分支,其在集合框架中的位置可以直接参看下图:

Java中ArrayList、LinkedList和Vector的联系与区别

仔细观察和分析此图,你会发现JDK中对于List接口的实现由三种类型:ArrayList、Vector 和 LinkedList。当我们谈论List的时候,我们可以用它与Set来做比较,集合框架中的Set代表一群无序和唯一的元素集合。

ArrayList vs LinkedList vs Vector

仔细观察上图可知,集合框架中的List接口具有多达三个实现类。由继承机制可知,它们在很多方面都是非常相似的,比如有序、用法等。它们之间最大的区别是它们的内部实现方式和细节,不同的实现方式和细节造就了它们之间巨大的性能差异和用法差异。

ArrayList 是Java语言对于动态数组的一个实现。当不断地添加新的元素到ArrayList集合中时,该集合的底层数组的长度就会动态的增长,以便能容纳新添加的元素。至于ArrayList的底层数组长度的动态增长策略,在不同的JDK实现和版本中是不同的,最常见的策略是新增 %50,具体请参看源码。正因为ArrayList的底层实现是数组,其带来的一个特性是:它的元素可以通过 getter(index) 和 setter(index) 方法直接访问,而且性能特别好。

emsp;LinkedList 的底层实现是基于 双向队列(double linked list)。熟悉数据结构的读者应该可以猜到:LinkedList 对于新增和删除元素的操作在性能上远远优于 ArrayList。但是,它的缺点在于:其 getter(index) 方法和 setter(index) 方法的性能很差,时间复杂度是 O(n)。

Vector 与 ArrayList 唯一的区别是:其是 同步的(synchronized),线程安全。

性能对比

基于我们对Arraylist和LinkdedList的分析,我们可以总结出如下的一个表格:

ArrayList LinkedList
get() O(1) O(n)
add() O(1) O(1)
remove() O(n) O(n)

注意:add() 是指 add(E e), remove()是指 remove(int index);
1. 对于ArrayList,add/remove的时间复杂度是 O(n);但在尾部操作是 O(1) 。
2. 对于LinkedList,add/remove的时间复杂度是 O(n);但在尾部和头部操作的是 O(1) 。

性能测试

为了实际测验三种List的add、get和remove的性能,我们可以使用如下的代码片段:

ArrayList arrayList = new ArrayList();
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("duration : " + duration);

此处只给出测验ArrayList的add操作的代码,但是测验LinkedList和其他操作的代码是类似,读者可自行修改代码进行测验。测验的结果表明:
在add和remove操作时,LinkedList的性能远优于ArrayList。在get操作时,ArrayList的性能优于LinkedList。经过性能对比和性能的测试,我们可以总结出如何在它们之间做出选择。通常使用ArrayList,但是LinkedList在如下场景时更合适:
1. 随机访问集合元素的次数不是很频繁。
2. 对集合有大量的add/remove操作需求。

总结

对比Vector和ArrayList,如果程序本身就是线程安全的,为了更好的性能,应该选择ArrayList。当添加新的元素到集合时,Vector和ArrayList都需要更多的空间来存储新元素,但是它们的增长策略是不一样的:Vector的增长幅度是 100%;ArrayList的增长幅度是 50%。对于LinkdedList而言,其不仅实现了List接口,还实现了Queue接口,这个Queue接口给LinkdedList带来了更多的访问和操作元素的方法,比如 offer(), peek(), poll() 等。

对于ArrayList而言,如果使用不含参数的构造函数新建一个ArrayList对象,该对象的起始大小是比较小的,只有10。我们都知道对象的动态增长导致的底层数组重写分配和复制是一个非常耗时的操作。所以,对于可以预估ArrayList大小的应用场景,应该指定ArrayList对象的初始大小,从而提供性能。


天天编码 , 版权所有丨本文标题:Java中ArrayList、LinkedList和Vector的联系与区别
转载请保留页面地址:http://www.tiantianbianma.com/java-arraylist-linkedlist-vector.html/
喜欢 (1)
支付宝[多谢打赏]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(2)个小伙伴在吐槽
  1. 对于LinkedList,add/remove的时间复杂度是 O(n);但在尾部和头部操作的是 O(1) 写反了吧!
    匿名2017-08-13 14:46 回复 Windows 10 | Chrome 60.0.3112.90
    • 是的,写反了
      匿名2017-10-16 17:32 回复 Windows 7 | Chrome 53.0.2785.104