文档章节

ArrayList vs. LinkedList vs. Vector

crossbell
 crossbell
发布于 2014/06/03 19:40
字数 1102
阅读 16
收藏 0
点赞 0
评论 0
本文由  ImportNew  -  唐小娟  翻译自  Programcreek 。欢迎加入 Java小组 。转载请参见文章末尾的要求。

1. List概览

List,就像它的名字暗示的一样,是一组排列有序的元素。当我们讨论List的时候,很容易将它和Set作比较。Set是一组唯一的而且排列无序的元素。

下图是集合类的层次结构图。你可以总体上知道我们今天讨论的主题。

2. ArrayList vs. LinkedList vs. Vector

从上图可知,它们都实现了List接口。它们的用法差不多,主要的区别在于它们对于不同操作的操作速度不同。

ArrayList是可以改变大小的数组。当有元素添加到ArrayList中去时,它的大小动态的增加。元素可以直接通过get()和set()方法进行访问,因为ArrayList实际上是数组。LinkedList是个双向链表。它的add()和remove()方法比ArrayList快,但是get()和set()方法却比ArrayList慢。Vector和ArrayList类似,但是Vector是同步的。如果在线程安全的环境下,使用ArrayList是更好的选择。添加元素的时候,当超过初始容量的时候,Vector和ArrayList需要更多的空间:Vector需要将数组的大小增加一倍,而ArrayList需要增加50%。

LinkedList还实现了Queue接口,这样就比ArrayList和Vector多出了一些方法如offer(), peek(), poll()等。

注意:ArrayList的初始容量(initial capacity)很小。我们应该设置一个比较大的初始容量,这样可以避免重新改变大小。

3. ArrayList的例子

 ArrayList al = new ArrayList();
al.add(3);
al.add(2);      
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(6);
 
Iterator iter1 = al.iterator();
while(iter1.hasNext()){
    System.out.println(iter1.next());
}

4. LinkedList的例子

LinkedList ll = new LinkedList();
ll.add(3);
ll.add(2);      
ll.add(1);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(6);
 
Iterator iter2 = ll.iterator();
while(iter2.hasNext()){
    System.out.println(iter2.next());
}

由上可见,它们的用法相同,主要的区别在于它们内部的实现,以及操作的复杂度的不同。

5. Vector

Vector几乎和ArrayList相等,主要的区别在于Vector是同步的。正因为此,Vector比ArrayList的开销更大。通常大部分程序员都使用ArrayList,他们可以自己写代码进行同步。

6. ArrayList vs. LinkedList的性能比较

时间复杂度如下:

* 表中的add()指的是add(E e)(即是在列表末尾添加元素),remove()方法指的是remove(int index)。

ArrayList对于任意索引的插入/删除操作的时间复杂度是O(n),而在列表的尾部的操作时间为O(1)。

LinkedList对于任意索引的插入/删除操作的时间复杂度是O(n),而在列表的头部或尾部的操作时间为O(1)。

(译者注:这里原文解释的不是太清楚。对于任意索引的插入/删除操作

Arrays:

  • 找到插入/删除位置的时间复杂度是O(1)

  • 进行插入/删除操作的时间复杂度是O(n)

Linked Lists:

  • 找到插入/删除位置的时间复杂度是O(n)

  • 进行插入/删除操作的时间复杂度是O(1)

我使用下面的代码测试它们的性能:

ArrayList arrayList = new ArrayList();
LinkedList linkedList = new LinkedList();
 
// ArrayList add
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("ArrayList add:  " + duration);
 
// LinkedList add
startTime = System.nanoTime();
 
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);
 
// ArrayList get
startTime = System.nanoTime();
 
for (int i = 0; i < 10000; i++) {
    arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get:  " + duration);
 
// LinkedList get
startTime = System.nanoTime();
 
for (int i = 0; i < 10000; i++) {     linkedList.get(i); } endTime = System.nanoTime(); duration = endTime - startTime; System.out.println("LinkedList get: " + duration); // ArrayList remove startTime = System.nanoTime(); for (int i = 9999; i >=0; i--) {
    arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove:  " + duration);
 
// LinkedList remove
startTime = System.nanoTime();
 
for (int i = 9999; i >=0; i--) {
    linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);

输出如下:

ArrayList add:  13265642
LinkedList add: 9550057
ArrayList get:  1543352
LinkedList get: 85085551
ArrayList remove:  199961301
LinkedList remove: 85768810

 

它们的性能的差别很显著。LinkedList对于add()和remove()相对于ArrayList要快,但是get()要慢些。按照复杂度以及测试结果来看,我们很容易知道什么时候该使用ArrayList,什么时候该使用LinkedList。简而言之,下面的情况该使用LinkedList:

  • 如果没有大量的随机访问

  • 如果有很多add/remove的操作

原文链接: Programcreek 翻译: ImportNew.com - 唐小娟
译文链接: http://www.importnew.com/8782.html
[ 转载请保留原文出处、译者和译文链接。]

本文转载自:http://www.importnew.com/8782.html

共有 人打赏支持
crossbell
粉丝 24
博文 172
码字总数 14545
作品 0
海淀
项目经理
ArrayList vs. LinkedList vs. Vector

List概览 List,就像它的名字暗示的一样,是一组排列有序的元素。当我们讨论List的时候,很容易将它和Set作比较。Set是一组唯一的而且排列无序的元素。 下图是集合类的层次结构图。你可以总体...

markGao
2014/01/21
0
0
ArrayList vs. LinkedList vs. Vector

List概览 List,就像它的名字暗示的一样,是一组排列有序的元素。当我们讨论List的时候,很容易将它和Set作比较。Set是一组唯一的而且排列无序的元素。 下图是集合类的层次结构图。你可以总体...

LCZ777
2014/07/30
0
0
ArrayList VS Vector VS LinkedList

ArrayList VS Vector 相同点:1>都是基于Object数组实现的。2>都允许添加null元素。 不同点:1>ArrayList不是线程安全的,Vector是线程安全的(方法是Synchronized的)。2>ArrayList扩容后容量...

A__17
03/05
0
0
java.util包中集合详解

本文只是集合的概述,介绍集合之间的关系,以及各种集合的异同,不会深入介绍具体的实现,具体实现的介绍,可以参见文中提供的链接。 java集合概述 java集合整体分为collection和map两种,接...

jacksu在简书
01/25
0
0
Java 容器 & 泛型:二、ArrayList 、LinkedList和Vector比较

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket 继续上一篇的容器文章认识容器,泥瓦匠慢慢带你们走进List的容器解说。今天泥瓦匠想说说 ArrayList 、LinkedList和Vecto...

泥沙砖瓦浆木匠
2015/03/19
0
10
Java 容器 & 泛型:一、认识容器

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket 容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道...

泥沙砖瓦浆木匠
2015/03/13
0
2
LinkedList VS ArrayList

List,根据名字我们知道是有序的元素集合。先贴一张集合的关系图。这里我们分析LinkedList与ArrayList。 Collection结构 LinkedList与ArrayList 它们都实现了List接口。但是内部实现上有些区...

Real_man
03/21
0
0
ArrayList VS LinkedList

java编程中我们用最多的几个类可以就是String,ArrayList,HashMap了.特别是ArrayList我们几乎无人不知,甚至有乱用的嫌疑了我们来看看ArrayList和LinkedList的区别.故名思意ArrayList是数组表,...

steven
2016/03/30
23
0
Arrylist、linkelist、vector之间的区别

ArrayList,LinkedList是不同步的,而Vector是同步的,Vector适合线程使用, ArrayList和Vector都是使用Objec的数组形式来存储的,当元素数目超出其长度时,Vector缺省情况下自动增长原来一倍...

刘谱_smile
2015/10/23
532
0
关于List接口中ArrayList,LinkedList和Vector的取值方法的一些性能测试

对于List接口下的ArrayList,LinkedList和Vector的取值的方式的测试: 对于ArrayList的取值方式的测试: package com.test.collections.list; import java.util.ArrayList;import java.util.I......

it_haha
2016/04/21
136
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

虚拟机怎么安装vmware tools

https://blog.csdn.net/tjcwt2011/article/details/72638977

AndyZhouX
11分钟前
0
0
There is no session with id[xxx]

参考网页 https://blog.csdn.net/caimengyuan/article/details/52526765 报错 2018-07-19 23:04:35,330 [http-nio-1008-exec-8] DEBUG [org.apache.shiro.web.servlet.SimpleCookie] - Found......

karma123
12分钟前
0
0
vue-router懒加载

1. vue-router懒加载定义 当路由被访问的时候才加载对应组件 2. vue-router懒加载作用 当构建的项目比较大的时候,懒加载可以分割代码块,提高页面的初始加载效率。 ###3. vue-router懒加载实...

不负好时光
19分钟前
0
0
庆祝法国队夺冠:用Python放一场烟花秀

天天敲代码的朋友,有没有想过代码也可以变得很酷炫又浪漫?今天就教大家用Python模拟出绽放的烟花庆祝昨晚法国队夺冠,工作之余也可以随时让程序为自己放一场烟花秀。 这个有趣的小项目并不...

猫咪编程
21分钟前
0
0
SpringBoot | 第七章:过滤器、监听器、拦截器

前言 在实际开发过程中,经常会碰见一些比如系统启动初始化信息、统计在线人数、在线用户数、过滤敏高词汇、访问权限控制(URL级别)等业务需求。这些对于业务来说一般上是无关的,业务方是无需...

oKong
34分钟前
5
0
存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储

存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储 存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。 顺序结构和链接结构适用在内存结构中。 顺序表每个单元都是按物理...

DannyCoder
45分钟前
1
0
Firefox 61已经为Ubuntu 提供支持

最新和最好的Mozilla Firefox 61 “Quantum”网络浏览器已经为Ubuntu Linux操作系统的用户提供了支持,现在可以通过官方软件库进行更新。 Mozilla于2018年6月26日发布了Firefox 61版本,该版...

六库科技
今天
0
0
Win10升级后执行系统封装(Sysprep)报错

开始封装 一年多以前开始给公司封装Win10系统,便于统一给公司电脑初始化携带各种软件的系统,致力于装完既可以开发的状态。那时候最新的版本是Win10 1703版本,自然就以他为母盘,然后结合V...

lyunweb
今天
40
0
php 性能优化

#什么情况下会遇到性能问题 PHP 语法使用的不恰当

to_be_better
今天
0
0
Jenkins 构建触发器操作详解

前言 跑自动化用例每次用手工点击jenkins出发自动化用例太麻烦了,我们希望能每天固定时间跑,这样就不用管了,坐等收测试报告结果就行。 一、定时构建语法 * * * * * (五颗星,中间用空格隔...

覃光林
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部