ArrayList与LinkedList源码分析-从源码角度分析

ArrayList与LinkedList都是线性表，是可以储存具有相同特性的数据元素的有限序列。但它们内部实现是截然不同的，分别代表了数组和链表的两种实现，这也注定了它们算法的时间复杂度与空间复杂度是不一样的，需要择优使用在不同的场景。接下来将源码（JDK1.8）细节去分析它们的差异。

---

ArrayList源码分析

• 无参构造函数

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

elementData是一个Object数组，使用transient关键字修饰,transient关键字与Serializable接口配合使用，使用transient关键字修饰的变量不会被序列化。

• int参数构造

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);
        }
    }

当传入的initialCapacity大于0时，初始化一个长度为initialCapacity的Object数组

• Collection参数构造

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

public interface Collection<E> extends Iterable<E> {
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

Collection是一个接口，List、Set、Queue接口继承自Collection接口，所以这里的参数c可以是List、Set、Queue的实现类。toArray()方法有两个，分别返回Object数组和泛型数组。如果toArray()是泛型数组，则拷贝一份到Object数组中并返回。

---

• add(E e)方法

    public boolean add(E e) {
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }

    private static final int DEFAULT_CAPACITY = 10;
    private void ensureCapacityInternal(int minCapacity) {
        //如果实际存储数组 是空数组，则最小需要容量就是默认容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//结构改变次数

        //如果数组（elementData)的长度小于最小需要的容量（minCapacity）就扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ArrayList在没指定initialCapacity时就是相当于会使用延迟分配对象数组空间，当第一次插入元素时才分配10（默认）个对象空间。假如有20个数据需要添加，那么会分别在第一次的时候，将ArrayList的容量变为10；之后扩容增加数组的size>>1的长度,也就是会按照 1.5倍增长。也就是当添加第11个数据的时候，Arraylist继续扩容变为10*1.5=15；当添加第16个数据时，继续扩容变为15 * 1.5 =22个。

• add(int index, E element)

    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // 扩容，和add(E e)一样
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

System.arraycopy()方法是一个原生的静态方法，用于从源数组拷贝元素到目标数组中
System.arraycopy() 方法如下:

public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,
int length);

src: 源数组 .
srcPos: 源数组中开始拷贝的索引值
dest: 目标数组
destPos: 拷贝到目标数组开始的索引值
length: 拷贝元素的个数
add(int index, E element)就是将index后面的数组copy了一份，并将索引值加1，然后将数组index索引赋值。

---

• E get(int index)

    public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }

• E set(int index, E element)

    public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

---

• E remove(int index)

    public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

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

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null;

        return oldValue;
    }

numMoved表示要左移的元素，是否是大于0，大于0则将index后的元素左移一个位置，并将最后一个索引的最后一个元素置空。如果等于0，说明是index最后一个元素的索引，不需要左移，直接将最后一个索引置空。

• boolean remove(Object o)

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null;
    }

判断要移除的object是否为空，为空则移除第一个为null的元素。不为空时则用equals进行比较，如果元素没有重写equals方法，就比较内存地址，有重写就比较定义的equals规则，移除第一个内存地址相同或equals规则相同的元素。

ArrayList总结

• 1.底层数组实现，使用默认构造方法初始化出来的容量是10
• 2.扩容的长度是在原长度基础上加上>>1
• 3.底层是数组，get获取元素性能很好
• 4.线程不安全，所有的方法均不是同步方法也没有加锁，因此多线程下慎用
• 5.添加删除和插入需要复制数组 性能较低

---

LinkedList源码分析

• 无参构造

    public LinkedList() {
    }

• Collection参数构造

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

        //将c中的元素都添加到链表中
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);//添加到链表尾部
    }

    //在序号为index处，添加c中所有的元素到当前链表中（后向添加）
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);//检查索引是否合法

        Object[] a = c.toArray();//将集合转换为数组
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {//构造方法会走这里，如果index为元素个数，即index个结点为尾结点
            succ = null;
            pred = last;//前指向指向尾结点，构造方法last这里是null
        } else {
            succ = node(index); 
            pred = succ.prev;   
        }

        //for循环结束后，数组a里面的元素都添加到当前链表里面，后向添加
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //新生成一个结点，结点的前向指针指向pred,后向指针为null
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                //如果pred为null，则succ为当前头结点,构造方法会走这里
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;//pred移动到新结点
        }

        if (succ == null) {
            last = pred;//succ为null，这表示index为尾结点之后，构造方法会走这里
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;//元素个数+num
        modCount++;//修改次数+1
        return true;
    }

Collection参数的构造方法将Collection转成数组，并循环遍历数组长度创建Node节点，并将双向链表前后指针赋值。

---

• add(E e) 、offer(E e)

   public boolean offer(E e) {
        return add(e);
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    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++;
    }

add(E e)调用linkLast(E e)方法把元素添加到尾部，添加到尾部时创建新的节点，prev指针指向最后一个节点，next指针指向null。当最后一个节点为空，说明当前linkedlist元素为空，把新节点作为第一个节点。否则将原来的最后节点的next指针指向新节点。

• add(int index, E element)

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

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    Node<E> node(int 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;
        }
    }

    void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

当add(int index, E element)传入索引==size,调用linkLast(element)添加到后面，在add(E e)中已经分析。不等于size,调用linkBefore(element, node(index))添加到中间或最前面，node(index)方法获取原Node节点，因为采用双向链表的设计，获取原Node节点只需遍历一半，将时间复杂度O(n)变成了O(n/2)，这也是双向链表比单向链表的优点。继续回到linkBefore(E e, Node<E> succ)分析，首先获取原索引Node节点的prev指针，创建新节点，新节点的prev指向原Node的prev，next指针指向原Node。当原节点不为空，将原Node的next指针指向新Node，如果原节点为空，首节点赋值为新Node。

---

• E remove(int index)

    public E remove(int index) {
        checkElementIndex(index);//检查索引是否合法
        return unlink(node(index));
    }

    E unlink(Node<E> x) {
        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;//前一个节点的next指针指向后一个节点
            x.prev = null;//移除原节点的prev指针指向
        }

        if (next == null) {//如果移除的是最后一个节点
            last = prev;//将最后的last赋值为前一个节点
        } else {
            next.prev = prev;//将后一个节点的prev指针指向前一个节点
            x.next = null;//移除原节点的next指针指向
        }

        x.item = null;//置空原节点
        size--;
        modCount++;
        return element;
    }

E remove(int index)调用E unlink(Node<E> x)方法，获取索引Node的item，和前后节点，将前后节点的prev和next指针对应指向，并断开了原节点prev和next指向，并置空原索引节点，返回原节点item。

• boolean remove(Object o)

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

boolean remove(Object o)比E remove(int index)多了一步，需要先遍历获取索引，然后再调用unlink(Node<E> x)方法，，其他和E remove(int index)一样。

---

LinkedList总结

• 1.LinkedList的实现是基于双向链表的，且头结点中不存放数据。
• 2.无参构造方法直接建立一个仅包含head节点的空链表；包含Collection的构造方法，先调用无参构造方法建立一个空链表，而后将Collection中的数据加入到链表的尾部后面 。
• 3.在查找和删除某元素时，源码中都划分为该元素为null和不为null两种情况来处理，LinkedList中允许元素为null。
• 4.LinkedList是基于链表实现的，不存在容量不足的问题，所以没有扩容的方法。
• 5.Node node(int index)方法。该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index<(size<<1)，就只从位置0往后遍历到位置index处，而如果index>(size<<1)，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历，从而提高一定的效率。
• 6.LinkedList是基于链表实现的，插入删除效率高，查找效率低。