ArrayList LinkedList Vector 区别

喜欢ヅ旅行 2022-08-08 20:30 265阅读 0赞

### 这两天看到了一些好的文章收获很大，正好趁着中秋节有时间，就把他们翻译下，加深理解。 ###

### List概述    ###

List是由有序元素组成的序列，当我们谈到List的时候往往会想到set，set是由没有重复无序的元素组成的。下边这是collections的类图，从这个类图中，你可以对java 的 collections有一个大致的了解。

![Center][]

### ArrayList、LinkedList和Vector比较    ###

从上边这个类图中，我们可以看到，这三者都实现了List接口，他们使用起来非常接近。他们主要的区别是各自的实现方式的不同导致了操作性能的不同。  
ArrayList是可变大小数组的实现，随着加入到ArrayList中的元素越来越多，它的长度是动态增加的。由于ArrayList是数组，所以可以通过get和set方法来对元素进行直接的访问。  
LinkedList是双向链表的实现，，在remove和add方法上它的性能优于ArrayList，但是在get和set方法上它的性能又劣于ArrayList。  
Vector和ArrayList是相似的，但是vector是同步的。  
如果你的程序是线程安全的那么ArrayList是更好的选择。Vector和ArrayList都需要比存储的元素更大的空间，Vector每次都要比现在的空间扩大一倍，但是ArrayList每次只需要比现在的空间扩大50%。但是，LinkedList也实现了queue接口，这就比ArrayList和Vector增加了更多的方法，比如：offer()，peek()，poll()等等。  
注：ArrayList的初始容量很小，利用ArrayList构建一个较高的初始容量是一个好的习惯，因为这样可以避免调整的代价。

### ArrayList 例子    ###

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

### LinkedList 例子 ###

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

从上边这两个例子可以看出，他们的用法非常接近，他们真正的区别是他们内在的实现和操作的复杂性。

### Vector ###

Vector和ArrayList几乎相同，不同的是Vector是synchronized（同步的），真因为如此他的开销要比ArrayList大。通常情况下，程序员们使用ArrayList代替Vector，因为他们自己可以明确的对程序进行同步处理。

### ArrayList和LinkedList和性能比较 ###

时间复杂度的比较如下：

![Center 1][]

表中的add()指的是add(E e)，remove指的是remove(int index)。对于任意一个元素的add和remove，ArrayList具有O(n)的时间复杂度，但是对于最后一个元素它具有O(1)的时间复杂度。对于任意一个元素的add和remove，LinkedList具有O(n)的时间复杂度，但是对于list的头和尾只具有O(1)复杂度。  
我使用下面的代码来测试他们的性能：

ArrayList<Integer> arrayList = new ArrayList<Integer>();
    LinkedList<Integer> linkedList = new LinkedList<Integer>();
     
    // 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

![Center 2][]  
他们的性能差异是很明显的，LinkedList在add和remove方法上是快于ArrayList的，但是在get方面比ArrayList慢。基于复杂性表和测试结果来看，我们可以得出一个结论：当可以选择使用ArrayList或者LinkedList的时候，在下边这两种情况出现的时候，首选LinkedList。  
1、没有大量的随机访问的数据。  
2、有大量的remove和add操作。  
  
小弟第二次翻译，如有不正确之处，还请大家指出。  
  
这是原文：http://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/  
大家也可以参考文章：http://www.programcreek.com/2013/09/top-10-questions-for-java-collections/

[Center]: /images/20220731/6acd988a7bec424baca693c026ca6153.png
[Center 1]: /images/20220731/dae6351834f644fda8004548802ec2c6.png
[Center 2]: /images/20220731/dc4eba4112ac40f6bf466f18be08adb2.png