JAVA基础篇-深入比较ArrayList和LinkedList

引言

List是我们能开发中最场用到的一种集合容器,也是第三方框架中最常用到的集合容器,用到的频率屈居老二,除了老大String。
其API简单上手,使用起来也很方便，我们平时很多时候都是不假思索就用起来了，我们有没有想过是不是所有场景都该用List,是不是所有场景都该用ArrayList,是不是有的场景该选择使用LinkedList呢，是否可以选择Set?

预备知识

1.两者都是Collection的子类，都实现了List接口。
2.两者都实现了Coloneable和Serializable接口,支持克隆和序列化操作。
3.两者都是AbstractList的子类。
4.使用时我们一般都是用List<TypeReference>泛型形式来构造一个集合对象。
5.两者容器大小都是静态固定的，如果下表越界的话都会抛出IndexOutOfBoundsException异常。

注意:LinkedList的首个元素没有前驱节点而末元素是没有后继节点，首尾并不相连。我们不要误以为它是循环链表。

$\color{red}{上面的阐述我们可以通过他们俩的类的结构图能看出来 }$

ArrayList类图.png

LinkedList类图.png

不同点
$\color{red}{LinkedList}$ 本质上是一个既是一个双端队列,也是一个双向链表， $\color{red}{ArrayList}$ 本质上是一个数组(链表)，只不过其可以动态扩容。

$\color{red}{LinkedList}$ 比 $\color{red}{ArrayList}$ 更耗内存。理由是 $\color{red}{LinkedList}$ 除了数据块之外，还有前驱Node和后继Node,因为需要对象存储所以更耗内存。

$\color{red}{LinkedList}$ 更适合随机插入和添加数据,只需改变前驱后继节点指向即可。

$\color{red}{ArrayList}$ 在随机访问效率比 $\color{red}{LinkedList}$ 效率更快，直接数组通过index索引定位到元素（RandomAccess有详细说明 for each runs faster than iterator），而 $\color{red}{LinkedList}$ 随机取值时,需要循环指针迭代。
我们来说明一下 $\color{red}{ArrayList}$ 的扩容机制，扩容对象其实就是 $\color{red}{ArrayList}$ 中的 $\color{red}{ElementData}$ 数组的容量动态大小。

扩容算法描述:当没有初始化的情况下，第一次扩容为默认10个大小,往后当size超过这个容量的时候就进行n+n/2的方式进行扩容,当有足够容量的时候，每次添加的时候就不会扩容,这样大大增加了往尾部添加元素的效率。初始化大小为10的扩容数列是:{10，15，22，33，49.........}，依次类推即可。动态数组默认的最大容量是MAX_VALUE = 0x7fffffff=2^31-1,如果在添加数据的情况下出现内存溢出也会抛出内存溢出异常。

优缺点说明

$\color{red}{ArrayList}$ 是个可动态扩容的数组,是带有下表索引数组的一个容器，适合用来检索数据.

$\color{red}{LinkedList}$ 是一个双端链表,并且每个数据都包含了Node节点，每个Node都包含了Prev(前驱结点)与Next(后继节点)以及item(数据节点).适合随机添加与插入和删除操作,LinkedList不需要动态扩容。

性能对比:

$\color{red}{ArrayList}$ 在尾部添加大量元素时的效率反而要高于 $\color{red}{LinkedList}$ 。原因是：前者在容量足够的情况下时不需要扩容的,而LinkedList需要构造一个Node节点出来。

//ArrayList向尾部添加元素
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

//LinkedList向尾部添加元素
 public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * Links e as last element。
    *空时将first的后继节点指向新添入的节点，非空时将 
    * Last的next指向新的节点
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

$\color{red}{ArrayList}$ 指定位置设置元素的时间上的性能明显高于 $\color{red}{LinkedList}$ .
$\color{red}{ArrayList}$ 的时间复杂度时O(1),而 $\color{red}{LinkedList}$ 的时间复杂度时O(n).

//这是ArrayList的指定位置修改函数
 public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
··································································
//这是 $\color{red}{LinkedList}$的修改指定位置的元素
public E set(int index, E element) {
        checkElementIndex(index);
        //这里折中法查找指定位置上的Node节点,双向循环队列必须这么做啊！
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

 Node<E> node(int index) {
        // assert isElementIndex(index);
      //
        if (index < (size >> 1)) {
           //如果是索引是前半段则从折中以first节点后继节点寻找
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
           //如果是索引是前半段则从折中以last前驱节点寻找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

3. $\color{red}{ArrayList}$ For 循环取值和迭代器取值要远远高于LinkedList的取值 $\color{red}{LinkedList}$ 。

只要对比他们的源码就可以直观地分析出来了。

//List通过索引取值时直接数组下标取值,相当于hash取值一样的效率，效率级别为O(1)
 public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

//而LinkedList 是没有数组下标的概念的，只有Node节点的概念，所以通过下表去找对象的时候只能通过节点去next或prev查找
    /**
     * 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;
        }
    }

4. $\color{red}{ArrayList}$ 根据索引移除元素在效率上要低于 $\color{red}{LinkedList}$ ,通过源代码分析可以确认这个结论。

 public E ArrayList.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;
    }


    /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

5. $\color{red}{ArrayList}$ 在迭代器中移除元素的效率同样也低于于 $\color{red}{LinkedList}$ ,亲测代码。

        Iterator arrayListIterator = arrayList.iterator();

        while (arrayListIterator.hasNext()) {
            arrayListIterator.next();
            arrayListIterator.remove();
        }
        long end = System.currentTimeMillis();

        System.out.println(String.format("ArrayList 迭代器 中删除元素耗时%s毫秒", end - start));

        start = System.currentTimeMillis();
        Iterator linkedIterator = linkedList.iterator();

        while (linkedIterator.hasNext()) {
            linkedIterator.next();
            linkedIterator.remove();
        }

        end = System.currentTimeMillis();
        System.out.println(String.format("LinkedList 迭代器 中删除元素耗时%s毫秒", end - start));

作用场景描述

1.我们在平时做查询接口的时候通常都选择ArrayList集合，相比LinkedList和其他Set集合的话,ArrayList的迭代效率更快更适合做协议上的流化输出，并且ArrayList在不需要频繁扩容的情况下往尾部添加数据的效率并不低。如果需要保证线程安全的话,用Collections.SynchronizedList(List)来设置一个有同步器的集合。

2.尽量减少ArrayList的扩容次数，提高性能,知道固定大小的情况下可以设置数组的初始大小,知道大概区间就设置上限初始的Capacity大小。

3.做根据下表去删除和在中间位插入元素时尽量选择LinkedList,原因是ArrayList需要做数组移位操作。而LinkedList只需要改变节点的前驱和后继节点的指向即可。

4.因为LinkedList有双端队列的特性，所以天生适合移除首尾元素，还有更适合添加头节点元素。

ArrayList删除动作.png

补充:ArrayList的数组移位压缩并不慢,做了哪些优化呢？因为用到了System.arrayCopy)(),这个方法是JNI接口。

//Linux copy的方法
 void _Copy_conjoint_jints_atomic(jint* from, jint* to, size_t count) {
    if (from > to) {
      jint *end = from + count;
      while (from < end)
        *(to++) = *(from++);
    }
    else if (from < to) {
      jint *end = from;
      from += count - 1;
      to   += count - 1;
      while (from >= end)
        *(to--) = *(from--);
    }
  }

//Windows

static void pd_conjoint_jints_atomic(jint* from, jint* to, size_t count) {
  if (from > to) {
    while (count-- > 0) {
      // Copy forwards
      *to++ = *from++;
    }
  } else {
    from += count - 1;
    to   += count - 1;
    while (count-- > 0) {
      // Copy backwards
      *to-- = *from--;
    }
  }
}