ArrayList、LinkedList、Vector 三者差异比较

一、ArrayList、LinkedList、Vector的区别

（1）底层结构

ArrayList 的底层是基于动态数组来实现的，LinkedList 的底层是基于拥有头尾指针的双向链表来实现的。

（2）继承关系

ArrayList 继承于 AbstractList 抽象类，实现了 Serializable、Cloneable、RandomAccess接口，这里 RandomAccess接口只是为了允许随机访问而不是提高随机访问的效率；

LinkedList 继承于 AbstractList 抽象类，实现了 Seriablizable、Cloneable 接口，不支持随机访问。因为它的随机访问效率很低，它的 get() 方法是通过折半法然后指针顺序移动来实现的。

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
//LinkedList get() 方法
    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        checkElementIndex(index);  //检查是否越界，和队列长度size比较
        return node(index).item;
    }


    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {   //这里进行了折半比较
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

（3）随机访问

对于随机访问 get() 和 set()操作，ArrayList 优于 LinkedList，因为 LinkedList 需要移动指针；

对于插入和删除，LinkedList 优于 ArrayList，因为 ArrayList 涉及到数组元素的移动和复制。

ArrayList 和 LinkedList 都不是线程安全的，它们需要进行加锁。可以使用 Collections.SynchronizedList 来构建线程安全的队列。

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
//ArrayList 的 add() 方法
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,    //这里将数组往后复制
                         size - index);
        elementData[index] = element;
        size++;
    }

//ArrayList 的 remove()方法
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,   //这里将数组往前复制
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

（4）Vector 与 ArrayList的异同

相同点：

1. 底层都是基于可动态变化的数组来实现的；
   2. 都是实现了 Serilizable、Cloneable、RandomAccess接口，支持随机访问。

不同点：

  1. 线程安全方面： Vector是线程安全的，而 ArrayList 是线程不安全的。因此 Vector 比 ArrayList 的花费更高，访问比 ArrayList 慢。
  2. 扩容方面： Vector扩容操作是将容量扩大为原来的2倍，而ArrayList 是将容量扩大为 1.5倍。因此ArrayList 更加节约空间。
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
//ArrayList 的 grow()方法
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //这里是扩大为原来的 1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

//Vector 的 grow() 方法
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?  //这里是扩大为原来的 2倍
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

二、ArrayList 的扩容机制

① 确定最小扩容容量：首先取当前集合元素个数+1 作为最小扩容容量。然后判断集合元素是否为空，如果是空的话，比较最小扩容容量和默认容量(10) ，然后取最大值作为最小扩容容量；如果集合不为空则不变；

② 比较是否需要扩容：将 modCount++(用来保证迭代器遍历数组时不会有其它线程对数组进行修改)。将数组大小和最小扩容容量进行比较，如果当前数组小了就执行 grow( ) 方法进行扩容操作。

③ 扩容操作：比较最小扩容容量和当前数组长度1.5倍，取较大值作为最小扩容容量；但是这个容量不是无限大的，还要接着比较最小扩容容量和ArrayList默认的最大容量(Integer.MAX_VALUE - 8)，如果大于最大容量则取 Integer.MAX_VALUE，否则取默认的最大容量(这里不会进来)。最后就是数组的复制 Arrays.copyOf(xxx)。

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
//ArrayList的 add() 方法
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 这里进行扩容操作
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    //先计算最小扩容容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  //如果集合中的数为空   
            return Math.max(DEFAULT_CAPACITY, minCapacity);    //比较默认容量(10)和传入的参数
        }
        return minCapacity;
    }

    //判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)  //容量不够
            grow(minCapacity);  //真正的扩容操作
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //数组长度1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)    //如果超出了默认最大容量
            newCapacity = hugeCapacity(minCapacity);   //hugeCapacity()方法判断
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

三、Collections.sort 和 Arrays.sort 的实现原理

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
//Collections.sort 方法
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }

    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);    //这里说明 Collections的排序实际上调用Arrays的排序
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }


//Arrays.sort 方法
    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {   //判断是否使用了比较器
            sort(a);
        } else {    //使用了就判断LegacyMergeSort(JDK1.6中使用) 是否开启
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else    //使用了比较器用 TimSort(是一种归并排序)
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

    //没有使用比较器,用优化了的 ComparableTimSort
    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }