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的例子
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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的例子
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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)
)
我使用下面的代码测试它们的性能:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
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);
|
输出如下:
1
2
3
4
5
6
|
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
相关推荐
ArrayList、LinkedList、Vector区别简介。
ArrayList Vector LinkedList 区别与用法.
比较ArrayList,LinkedList,Vector三者随机读取,插入,删除性能。
NULL 博文链接:https://lf6627926.iteye.com/blog/1297695
Java ArrayList Vector LinkedList map区别 各种集合的区别 写得非常详细
ArrayList、LinkedList、 Vector、Map 用法比较
ArrayList、Vector、LinkedList 的区别.docx
ArrayList vs. LinkedList vs. Vector HashSet 与 TreeSet 与 LinkedHashSet HashMap vs. TreeMap vs. HashTable vs. LinkedHashMap 按值排序地图 高效计数器 HashMap 常用方法。例如,按值排序 深入理解Arrays.sort...
对比Vector、ArrayList、LinkedList1
这是我从JDK中拿出的Arraylist,Vector,LinkedList源码,自己看源码的时候弄出来的,并写了一点自己的分析,仅供源码分析者使用
1. List概述List,就如图名字所示一样,是元素的有序列表 3. ArrayList示例[java] view plain copy public sta
Java容器集合(equals 和 hashCode+基础数据结构+ArrayList+Vector和LinkedList)
Java基础之集合List-ArrayList、LinkedList、Vector的底层实现和区别ArrayList底层实际是采用数组实现的(并且该数组的类型是
Vector,ArrayList, LinkedList的区别是什么? 答: 1. Vector、ArrayList都是以类似数组的形式存储在内存中,LinkedList则以链表的形 式进行存储。 2. List中的元素有序、允许有重复的元素,Set中的元素无序、不允许...
介绍),当处理的数据集比较小的时候,差距不明显,甚至还表现差一点;但是,当数据集增长到数万或百万以上时,提高就非常大了,具体还是取决于处理器和系统环境。排序算法
能学到什么:ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景...
《Vector、ArrayList、List使用深入剖析》-JAVA中文站(www_java-cn_com).htm
为什么ArrayList,Vector等都不支持循环中remove1 ...其实,在Vector,ArrayList,LinkedList中,删除有两种方式进行删除: 1.循环中删除 2.直接删除 1 Vector 直接删除 直接删除首先调用indexOf方法,得到目标元素
ArrayList,Vector底层是由数组实现,LinkedList底层是由双线链表实现,从底层的实现可以得出性能问题ArrayList,Vector插入速度较慢,查询速度较快,而LinkedList插入速度较快,而查询速度较慢。再者由于Vevtor使用了...
可以把接口的好处5体现出来,如果ArrayList()不满足需求,直接更换就可以。 接口的好处: 1.程序的耦合度降低 2.更自然的使用多态 3.设计与实现完全分离 4.更容易搭建程序框架 5.更容易更换具体实现 ArrayList: ...