本文基于 JDK 1.8.0_191

1. 源码对比

  • 实现接口类对比
  • 扩容机制对比
  • 线程安全

1.1 实现接口类对比

ArraryList、LinkList和Vector的区别 - 图1

  1. public class ArrayList<E> extends AbstractList<E>
  2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  4. public class LinkedList<E>
  5.     extends AbstractSequentialList<E>
  6.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable    
  8. public class Vector<E>
  9.     extends AbstractList<E>
  10.     implements List<E>, RandomAccess, Cloneable, java.io.Serializable

  • 它们都实现 List 接口，说明具备列表的增加、删除、遍历元素等特性。

  • ArrayList、Vector 额外实现 RandomAccess 接口，说明他们能在常量时间复杂度内快速随机访问元素。

  • LinkedList 额外实现 Queue 接口，具备队列的入队、出队等特性。

1.2 扩容机制对比

ArrayList

  1. private static final int DEFAULT_CAPACITY = 10;  // 定义初始大小
  3. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  // 定义列表存储元素数量最大值 
  5. private void grow(int minCapacity) {
  6.     // overflow-conscious code
  7.     int oldCapacity = elementData.length;   // 现有元素数量 
  8.     int newCapacity = oldCapacity + (oldCapacity >> 1);  // 增加后元素的数量 = 1 + 0.5 
  9.     if (newCapacity - minCapacity < 0)    // 增加后的元素数量 < 现有的空间，不扩容
  10.         newCapacity = minCapacity;
  11.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  12.         newCapacity = hugeCapacity(minCapacity);  // 增加后的元素数量 > 大于最大值，尝试分配 Integer.MAX_VALUE 个元素，可能会抛出 OutOfMemoryError  
  13.     // minCapacity is usually close to size, so this is a win:
  14.     elementData = Arrays.copyOf(elementData, newCapacity);
  15. }

Vector

  1. public Vector() {
  2.     this(10);
  3. }
  5. protected int capacityIncrement;  // 扩容数量值，Vector 初始化不指定时默认为 0
  7. private void grow(int minCapacity) {
  8.     // overflow-conscious code
  9.     int oldCapacity = elementData.length;
  10.     int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); // 当扩容数量值小于 0，那么扩容比例为原来的两倍；否则扩容的数量为这个值。
  11.     if (newCapacity - minCapacity < 0)
  12.         newCapacity = minCapacity;
  13.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  14.         newCapacity = hugeCapacity(minCapacity);
  15.     elementData = Arrays.copyOf(elementData, newCapacity);
  16. }

LinkList

  1. transient int size = 0;
  • 初始大小：ArrayList、Vector 默认为 10，LinkList 不指定默认为 0
  • 扩容比例：ArrayList 以 1.5 倍进行扩容；Vector 不指定扩容比例时默认为 2 倍进行扩容

1.3 线程安全性

ArrayList

  1. protected transient int modCount = 0;
  3. public boolean add(E e) {
  4.     ensureCapacityInternal(size + 1);  // Increments modCount!!
  5.     elementData[size++] = e;
  6.     return true;
  7. }

Vector

  1. protected transient int modCount = 0;
  3. public synchronized void addElement(E obj) {
  4.     modCount++;
  5.     ensureCapacityHelper(elementCount + 1);
  6.     elementData[elementCount++] = obj;
  7. }

Vector add() 方法上增加了 synchronized 关键字，使得 Vector 支持多线程环境下的元素增加删除修改操作。

2. 增删改性能对比

根据数据结构中知识:

顺序表查找元素时间复杂度为 O(1)，适用于随机查找元素的场景。

链表增减元素时间复杂度为 O(1)，适用于增减元素比较多的场景。

  1. public static void main(String[] args) {
  3.     ArrayList arrayList = new ArrayList();
  4.     LinkedList linkedList = new LinkedList();
  5.     Vector vector = new Vector();
  6.     long t1, t2;
  8.     t1 = System.nanoTime();
  9.     for (int i = 0; i < 10000; i++) {
  10.         arrayList.add(i);
  11.     }
  12.     t2 = System.nanoTime();
  13.     System.out.println("ArrayList add:" + (t2 - t1));
  15.     t1 = System.nanoTime();
  16.     for (int i = 0; i < 10000; i++) {
  17.         linkedList.add(i);
  18.     }
  19.     t2 = System.nanoTime();
  20.     System.out.println("linkedList add:" + (t2 - t1));
  22.     t1 = System.nanoTime();
  23.     for (int i = 0; i < 10000; i++) {
  24.         vector.add(i);
  25.     }
  26.     t2 = System.nanoTime();
  27.     System.out.println("vector add:" + (t2 - t1));
  28. }
  30. ArrayList add:6810212
  31. linkedList add:3463194
  32. vector add:4442985

添加元素，ArrayList 花费时间比 LinkList 时间长。

  1. public static void main(String[] args) {
  3.     ArrayList arrayList = new ArrayList();
  4.     LinkedList linkedList = new LinkedList();
  5.     Vector vector = new Vector();
  6.     long t1, t2;
  8.     for (int i = 0; i < 100000; i++) {
  9.         arrayList.add(i);
  10.         linkedList.add(i);
  11.         vector.add(i);
  12.     }
  14.     t1 = System.nanoTime();
  15.     for (int i = 0; i < 10000; i++) {
  16.         arrayList.get(i);
  17.     }
  18.     t2 = System.nanoTime();
  19.     System.out.println("ArrayList get:" + (t2 - t1));
  21.     t1 = System.nanoTime();
  22.     for (int i = 0; i < 10000; i++) {
  23.         linkedList.get(i);
  24.     }
  25.     t2 = System.nanoTime();
  26.     System.out.println("linkedList get:" + (t2 - t1));
  28.     t1 = System.nanoTime();
  29.     for (int i = 0; i < 10000; i++) {
  30.         vector.get(i);
  31.     }
  32.     t2 = System.nanoTime();
  33.     System.out.println("vector get:" + (t2 - t1));
  34. }
  36. ArrayList get:72482
  37. linkedList get:107975370
  38. vector get:242634

查找元素上，ArrayList 最快

3. 总结

将 ArrayList、LinkList 和 Vetor 进行了简单对比，总体来说：

  • 在查找元素比较频繁的场合，推荐使用 ArrayList；在修改元素比较频繁的场合，推荐使用 LinkList。
  • Vetor 与 ArrayList 类似，区别在于扩容比例、线程安全方面。
  • 性能对比测试结果可能存在添加元素 ArrayList 花费时间比 LinkList 多的情况， 这个原因

参考：

ArrayList vs LinkedList vs Vector 区别