Java List 对比：ArrayList vs. LinkedList vs. Vector

悠悠 2024-03-27 09:25 115阅读 0赞

## Java List 对比：ArrayList vs. LinkedList vs. Vector ##

*本文译自：[ArrayList vs. LinkedList vs. Vector][]*

### 1. List概览 ###

List，顾名思义，是元素的有序序列。当我们谈论 List 时，最好将它与 Set 进行比较，Set 是一组唯一且无序的元素。下面是Collection的类层次结构图。从层次结构图中，您可以大致了解 Java 集合。

![在这里插入图片描述][33cee7ce90db4039bc4ffd8793d41e1e.jpeg_pic_center]

### 2. ArrayList vs. LinkedList vs. Vector ###

从层级图来看，都是实现列表界面。它们的使用非常相似。它们的主要区别在于它们的实现会导致不同操作的不同性能。

数组列表被实现为一个可调整大小的数组。随着更多元素添加到 ArrayList，其大小会动态增加。它的元素可以通过使用 get 和 set 方法直接访问，因为 ArrayList 本质上是一个数组。

LinkedList被实现为双LinkedList。它在 add 和 remove 上的性能优于 Arraylist，但在 get 和 set 方法上更差。

向量与 ArrayList 类似，但它是同步的。

如果您的程序是线程安全的，ArrayList 是更好的选择。随着添加更多元素，Vector 和 ArrayList 需要更多空间。Vector 每次都会将其数组大小加倍，而 ArrayList 每次都会增加其大小的 50%。然而，LinkedList 也实现了队列接口比 ArrayList 和 Vector 添加了更多的方法，例如 offer()、peek()、poll() 等。

注意：ArrayList 的默认初始容量非常小。构造具有较高初始容量的 ArrayList 是一个好习惯。这可以避免调整大小的成本。

### 3. 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());
    }

### 4. 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());
    }

如上面的示例所示，它们类似于使用。真正的区别在于它们的底层实现和操作复杂性。

### 5. Vector ###

Vector 和 ArrayList 几乎是一样的，不同的是 Vector 是同步的。正因为如此，它比 ArrayList 有开销。通常，大多数 Java 程序员使用 ArrayList 而不是 Vector，因为它们可以自己显式同步。

### 6. ArrayList 与 LinkedList 的性能 ###

时间复杂度对比如下：

![在这里插入图片描述][cb751a61f880483c967fd82ce13c6e04.png_pic_center]

*  表中的add()指的是add(E e)，remove()指的是remove(int index)

*  ArrayList 对于任意索引的添加/删除具有 O(n) 时间复杂度，但对于列表末尾的操作具有 O(1) 时间复杂度。
 *  LinkedList 对于添加/删除的任意索引具有 O(n) 时间复杂度，但对于列表末尾/开头的操作具有 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

![在这里插入图片描述][c7c7a1252209469c8ff217e984c04a2e.png_pic_center]

它们的性能差异是显而易见的。LinkedList 添加和删除速度更快，但获取速度更慢。根据复杂度表和测试结果，我们可以确定何时使用 ArrayList 或 LinkedList。简而言之，在以下情况下，应首选 LinkedList：

*  没有大量随机访问元素
 *  有大量的添加/删除操作

[ArrayList vs. LinkedList vs. Vector]: https://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/
[33cee7ce90db4039bc4ffd8793d41e1e.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3a538ad939e744489e4f68422f471ed2.png
[cb751a61f880483c967fd82ce13c6e04.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a49d4b11db46436ab75796cb85c534ea.png
[c7c7a1252209469c8ff217e984c04a2e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/79451742b28548e0975807743be0697b.png