从JDK8源码中看ArrayList和LinkedList的区别

文章目录

前言
一、数据结构
二、ArrayList源码
三、LinkedList源码
总结

前言

ArrayList和LinkedList的区别是面试中经常会被问到的一点，但是如果只看八股文去背诵着两者的区别，就不会有深刻的认识。本篇文章从数据结构以及JDK8源码的角度来分析这两者的区别，希望给读者带来更多的思考。

一、数据结构

在看ArrayList和LinkedList的区别之前我们先来看一下数据结构的相关知识。
线性表是最常用的一种数据结构，简单来说线性表是n个数据元素的有限序列。线性表有两种实现方式，一种是顺序实现，一种是链式实现。

顺序实现是用一组地址连续的存储单元依次存储线性表的数据元素。
链式实现用一组任意的存储单元存储线性表的数据元素（这组存储单元可以连续，也可以不连续），包括数据域和指针域（指向下一个元素的位置）。

顺序实现基于数组，链式实现基于链表，两者的优缺点如下所示：

数组	链表（这里指单链表）
优点：随机访问特性，查找的时间复杂度为O(1)	优点：插入或者删除元素时，仅需要修改指针不需要移动元素
缺点：在作插入和删除操作时，需要大量移动元素，时间复杂度为O(n)	缺点：不具有随机访问特性，查找的时间复杂度为O(n)，同时插入和删除元素时也要找到前一个元素的位置，插入和删除的时间复杂度也为O(n)

ArrayList底层是基于数组实现的（具体实现有所不同，比如移动元素时使用复制完成），LinkedList底层是基于链表（这里用的是双向链表，包含两个指针，一个指向后继，一个指向前驱）实现的。由于底层数据结构不同，他们所适⽤的场景也不同，ArrayList更适合随机查找，LinkedList更适合删除和添加。

可以有人看到这里会产生疑惑，LinkedList虽然增删快（不需要移动元素），但需要遍历链表找到前驱的位置，这增删效率高在哪里?我们可以结合内存来看

ArrayList增删的时候涉及到内存的拷贝，这是很耗时操作，所以一般情况下讨论增删效率时忽略了查询的过程（查询只是访问内存，并不拷贝），即便不考虑扩容ArrayList也比LinkedList效率低。
从内存角度看，ArrayList需要一整段连续的内存空间，比较挑剔，数据量大的时候可能找不到那么大的连续内存空间。LinkedList得益于指针结构，只要有内存空间就能用，不挑剔。
另外从内存的利用率来看，ArrayList利用率=实际使用容量/申请的容量，利用率不确定，可能近乎1，也可能近乎0。而LinkedList利用率=数据/（数据+指针），这个利用率是固定的。
如果涉及到边遍历边需要增删的操作，例如含有大量随机整数的数字序列，需要删除小于0的数字，这时候LinkedList的性能会好很多。

小结：之前看到很多文章说无脑使用ArrayList就行，但我认为具体使用哪个还是要看具体的场景，ArrayList更适合随机查找，LinkedList更适合删除和添加，这个亘古不变的结论在一定程度上还是很有说服力的。

二、ArrayList源码

我们先来看一下ArrayList的常见用法，我们在创建ArrayList时，可以选择无参的构造或者带初始容量的构造方法。

public class MyTest {
    public static void main(String[] args) {
        //无参的构造方法
        ArrayList arrayList1=new ArrayList();
        //有参的构造方法
        ArrayList arrayList2=new ArrayList(16);
        arrayList1.add(1);
        arrayList1.add(2);
    }
}

无参的构造方法，赋值一个空的数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA ），后续第一次往里面添加元素的时候，会把容量扩到10

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

有参的构造方法，容量大于0直接创建一个数组，等于0赋值一个空的数组（EMPTY_ELEMENTDATA），小于0直接抛异常

   private static final Object[] EMPTY_ELEMENTDATA = {};

   public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

现在我们来看一下ArrayList常用的方法源码，首先我们来看一下add方法（默认往数组末尾添加），调用add方法时首先会调用ensureCapacityInternal（确保再产能内部）

  public boolean add(E e) {
        //当前元素的个数+1就是需要的容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

在ensureCapacityInternal中会调用ensureExplicitCapacity判断是否要扩容，在ensureExplicitCapacity中又会调用calculateCapacity计算当前容量，这三个方法的源码如下所示。

    private void ensureCapacityInternal(int minCapacity) {
        //判断是否要扩容，需要调用calculateCapacity计算容量
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static final int DEFAULT_CAPACITY = 10;
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果用户调用的是无参的构造方法，第一次add数组还未初始化，返回默认容量10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //其他情况，返回minCapacity
        return minCapacity;
    }  
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 如果添加的时候发现内部容量不够了，就要调用grow去扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

解下来看到扩容的方法源码：

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //计算新容量扩容，为原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果还未初始化，newCapacity 算出来会是0，则新数组容量直接为minCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新数组容量超过了最大值（Integer.MAX_VALUE - 8 =2147483639），调用hugeCapacity方法
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win  翻译minCapacity通常接近大小，因此这是一场胜利：
        //调用copyOf，把旧数组的内容复制到新数组上去
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

在上面方法的源码中可以看到一个非常有意思的现象，使用无参的构造方法，赋值给数组的是（DEFAULTCAPACITY_EMPTY_ELEMENTDATA ），给定容量为0的时候赋值给数组的是（EMPTY_ELEMENTDATA）

public class MyTest {
    public static void main(String[] args) {
        //刚开始赋值给数组的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        ArrayList arrayList1=new ArrayList();
        //刚开始赋值给数组的是EMPTY_ELEMENTDATA
        ArrayList arrayList2=new ArrayList(0);
    }
}

其实结合calculateCapacity方法就能知道，无参构造基于默认初始化大小10扩容，依次是10,15,22,33这种1.5倍数扩容。
而new ArrayList(0)基于你设置的大小0开始扩容，依次是0，1 ，2，3 ，4， 6这种1.5倍数扩容。

ArrayList的源码并不难，但是由于它的方法比较分散可能比较难以阅读，现在用一段话来总结一下ArrayList添加元素的逻辑：

创建ArrayList的时候可以选择无参或者有参，选择无参就是基于默认初始化大小10扩容，选择有参就是基于你设置容量的扩容。
往里面添加元素的时候首先要容量是否够，如果容量不够则要进行扩容，新数组容量为旧数组的1.5倍，然后把调用Arrays.copyOf把旧数组的元素拷贝到新数组上去。
除非你刚开始创建ArrayList时就指定了大于0的容量，会直接创建一个数组，其他情况下数组都会在第一次添加元素时调用grow方法完成数组的初始化，所以grow方法的作用有两个： 1.初始化数组 2.扩容

讲完了ArrayList添加元素的整个逻辑之后，我们来看一下往指定位置添加元素以及删除元素的方法源码。

   public void add(int index, E element) {
        //检查index合理性
        rangeCheckForAdd(index);
        //判断容量是否够
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //把该位置以及后面的所有元素往后移一位，采用复制的方式
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //往该位置添加元素
        elementData[index] = element;
        size++;
    }

     public E remove(int index) {
        //检查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;
    }

从上面这两段代码中可以看出ArrayList在作插入和删除操作时（非尾部），需要大量移动元素，涉及到数据的拷贝，这是很耗时操作。同时ArrayList的优点也很明显，即查找的时间复杂度为O(1)

    public E get(int index) {
        //检查下标合理性
        rangeCheck(index);
        //直接返回该位置元素
        return elementData(index);
    }

三、LinkedList源码

上文中已经提到LinkedList的数据结构是双向链表，一个结点包含两个指针，一个next（指向后继），一个prev（指向前驱）。同时存在一个first和last指针，指向整个链表的头和尾，方便操作，如下图所示。

关于LinkedList的重要属性如下源码所示：

    
    transient Node first;

    
    transient Node last;
   
   
    private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

LinkedList的构造方法：

 public LinkedList() {
 }
 
 public LinkedList(Collection c) {
    //调用无参构造
        this();
    //添加集合中所有元素
        addAll(c);
  }

LinkedList添加元素：

public class MyTest {
    public static void main(String[] args) {
        LinkedList linkedList=new LinkedList();
        //默认往链表尾部添加元素
        linkedList.add(1);
        //往链表头部添加元素
        linkedList.addFirst(2);
        //往链表尾部添加元素
        linkedList.addLast(3);
        //往指定位置添加元素
        linkedList.add(1,4);
    }
}

关于往链表尾部添加元素的源码如下所示：

  //默认往链表尾部添加元素
  public boolean add(E e) {
        linkLast(e);
        return true;
   }
  //往链表尾部添加元素
  public void addLast(E e) {
        linkLast(e);
   }
   
  void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
  }

关于往链表头部添加元素的源码如下所示：

 public void addFirst(E e) {
        linkFirst(e);
 }
 
 private void linkFirst(E e) {
        final Node f = first;
        final Node newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
 }

关键，往链表指定位置添加元素的源码如下所示：需要调用node方法，找到指定位置的元素。

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    Node node(int index) {
        // assert isElementIndex(index);
        //计算该索引在链表的前半段还是后半段，如果在前半段，则从头结点开始遍历找，如果在后半段则从尾结点开始往前找
        //这样设计是为了提高查找效率，因为LinkedList是双向链表可以支持这样操作
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    
    void linkBefore(E e, Node succ) {
        // assert succ != null;
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

我们可以看出如果往LinkedList的头部或尾部添加元素，发现时间复杂度为O(1),如果要往指定位置插入元素，涉及到遍历，时间复杂度为O(n),同时LinkedList进行了一定的优化，不是直接从头开始遍历，而是判断离头近还是尾近，在进行遍历。

关于LinkedList删除元素的方法如下所示，其逻辑跟增加差不多，只不过增加默认往尾部，删除默认在头部删，如果要在指定位置删除元素，也要涉及到遍历。

public class MyTest {
    public static void main(String[] args) {
        LinkedList linkedList=new LinkedList();
        //默认移除链表的第一个元素
        linkedList.remove();
        //移除链表的第一个元素
        linkedList.removeFirst();
        //移除链表的最后一个元素
        linkedList.removeLast();
        //移除指定位置的元素
        linkedList.remove(3);
    }
}

我们可以看到LinkedList相比ArrayList的一大优势就是增删元素时不涉及到元素的拷贝，通过改变指针引用即可，所以速度较快。

关于LinkedList查找元素的方法如下所示，如果要查找第一个元素和最后一个元素还是很快的(因为有first和last指针），时间复杂度为0(1)，如果要查找其他位置的元素时间复杂度为0(n)，可以看出在查找方面，LinkedList没有ArrayList强。

   //查找第一个元素
   public E getFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
   //查找最后一个元素
     public E getLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
   //查找指定位置元素
    public E get(int index) {
        checkElementIndex(index);
        //遍历查找
        return node(index).item;
    }

另外ArrayList和LinkedList都实现了List接⼝，但是LinkedList还额外实现了Deque接⼝，所以 LinkedList还可以当做队列或栈来使⽤

Deque是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。

Deque有三种用途：

普通队列(一端进另一端出):
Queue queue = new LinkedList()或Deque deque = new LinkedList()
双端队列(两端都可进出)：
Deque deque = new LinkedList()
栈
Deque deque = new LinkedList()

Deque提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

总结

相信你看完这篇文章之后，对ArrayList和LinkedList的理解会产生更多的思考，同时对本章的内容总结如下：

⾸先，他们的底层数据结构不同，ArrayList底层是基于数组实现的，LinkedList底层是基于链表实现的
由于底层数据结构不同，他们所适⽤的场景也不同，ArrayList更适合随机查找，LinkedList更适合删除和添加
ArrayList和LinkedList都实现了List接⼝，但是LinkedList还额外实现了Deque接⼝，所以 LinkedList还可以当做队列或栈来使⽤

从JDK8源码中看ArrayList和LinkedList的区别

Java相关栏目本月热门文章