ArrayList 与 LinkedList 源码分析及比较

ArrayList 源码分析

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    /**
     * Default initial capacity.
     * 默认初始大小为10
     */
    private static final int DEFAULT_CAPACITY = 10;
    
    /**
    * ArrayList底层是Object数组
    */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     * @serial
     */
    private int size;
    
    /**
    * 带初始大小的构造方法
    */
    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);
        }
    }

    /**
    * 默认无参构造函数，此时数组大小初始化为10
    */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
    * 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量
    *
    * @param minCapacity 所需的最小容量
    */
    public void ensureCapacity(int minCapacity) {
        //如果是true，minExpand的值为0，如果是false,minExpand的值为10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
        //如果最小容量大于已有的最大容量
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

   
    // 根据给定的最小容量和当前数组元素来计算所需容量。
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果当前数组元素为空数组（初始情况），返回默认容量和最小容量中的较大值作为所需容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 否则直接返回最小容量
        return minCapacity;
    }

    // 确保内部容量达到指定的最小容量。
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    //判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }


    /**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        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);
    }

}

ArrayList 的默认构造函数时，初始赋值的 Object 数组是空数组，等到真正需要添加元素时，此时分配容量，数组的大小初始化为 10，如果数组容量达到上限触发扩容，容量会扩容至原来容量的 1.5 倍，根据 int newCapacity = oldCapacity + (oldCapacity >> 1) 。

LinkedList 源码分析

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * 头节点
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * 尾节点
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     * 默认构造函数，构造空链表
     */
    public LinkedList() {
    }


    /**
     * Returns the first element in this list.
     * 返回第一个节点元素
     * @return the first element in this list
     * @throws NoSuchElementException if this list is empty
     */
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    /**
     * Returns the last element in this list.
     * 返回末尾节点元素
     * @return the last element in this list
     * @throws NoSuchElementException if this list is empty
     */
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

     /**
     * Appends the specified element to the end of this list.
     * 将元素加入链表的末尾
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    
    /**
    * Links e as last element.
    * add函数中调用的方法，将e连接至链表末尾
    */
    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++;
    }

链表节点的 Node 类

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

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

LinkedList 是基于双向链表实现的类，一般场景下跟 ArrayList 相比，效率较差。

对比

• 底层数据结构：ArrayList 底层是 Object 数组；LinkedList 底层是双向链表。

• 访问的时间复杂度：ArrayList 访问的时间复杂度为 O(1)，可以通过下标直接访问；LinkedList 访问的时间复杂度为 O(n)，需要通过节点逐步遍历至所需要访问的节点。

• 插入/删除的时间复杂度：ArrayList 在尾部插入/删除的时间复杂度为 O(1)，在特定位置插入/删除的时间复杂度为 O(n)，需要将插入/删除元素之后的元素前移或后移；LinkedList 插入/删除的时间复杂度为 O(1)，只需要断开链表指针即可。

• 存储方式：ArrayList 以连续的内存空间存储；LinkedList 可分散存储在内存。

• 空间占用：ArrayList 相比 LinkedList 占用空间更少，ArrayList 需要预留一定的空间，而 LinkedList 是每个元素都要消耗比 ArrayList 更多的空间。

• 是否线程安全：ArrayList 和 LinkedList 都是不同步的，不保证线程安全。

• 缓存局部性：ArrayList 对局部更友好，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。具体表现在：

  • 占用空间：链表元素比数组元素占用空间更多，导致缓存中容纳的有效数据量更少。
  • 缓存行：链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。
  • 预取机制：数组比链表的数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。
  • 空间局部性：数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。

在《hello algorithm》中如此说：

缓存虽然在空间容量上远小于内存，但它比内存快得多，在程序执行速度上起着至关重要的作用。由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当 CPU 尝试访问的数据不在缓存中时，就会发生缓存未命中（cache miss），此时 CPU 不得不从速度较慢的内存中加载所需数据。

显然，“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好。

为了尽可能达到更高的效率，缓存会采取以下数据加载机制。

• 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行的传输形式更加高效。
• 预取机制：处理器会尝试预测数据访问模式（例如顺序访问、固定步长跳跃访问等），并根据特定模式将数据加载至缓存之中，从而提升命中率。
• 空间局部性：如果一个数据被访问，那么它附近的数据可能近期也会被访问。因此，缓存在加载某一数据时，也会加载其附近的数据，以提高命中率。
• 时间局部性：如果一个数据被访问，那么它在不久的将来很可能再次被访问。缓存利用这一原理，通过保留最近访问过的数据来提高命中率。