GVKun编程网logo

LinkedList实现原理（JDK1.8）（java linkedlist原理）

21

以上就是给各位分享LinkedList实现原理，其中也会对JDK1.8进行解释，同时本文还将给你拓展0004--jcf(jdk1.7)-LinkedList源码、ArrayList与LinkedLis

以上就是给各位分享LinkedList实现原理，其中也会对JDK1.8进行解释，同时本文还将给你拓展0004--jcf (jdk1.7)-LinkedList 源码、ArrayList与LinkedList的区别以及JDK11中的底层实现、ArrayList和LinkedList底层实现原理、ArrayList实现原理（JDK1.8）等相关知识，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

LinkedList实现原理（JDK1.8）（java linkedlist原理）

LinkedList实现原理（JDK1.8）（java linkedlist原理）

LinkedList实现原理（JDK1.8）

LinkedList底层采用双向链表，如果对链表这种结构比较熟悉的话，那LinkedList的实现原理看明白就相当容易。

链表通过“指针”将一组零散的内存块串联起来使用，每一个元素（节点）通过指针指向它的下一个元素，最后一个节点的下一个指向为null，而双向链表就是除头节点的每一个元素都有指针同时再指向它的上一个元素。链表不同于数组，由于其地址的不连续，且元素占用大小的不确定，所以没法根据地址直接取值，获取元素时需要遍历访问，而双向链表相比于单向链表，一定程度上占用了额外的内存，但支持了双向遍历，加快了元素索取。

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList继承于AbstractSequentialList抽象类，AbstractSequentialList又继承于AbstractList，最终实现了List的接口，所以LinkedList支持List集合的一些常规操作，但同时LinkedList又实现了Queue接口，所以LinkedList也支持队列的一些使用，例如peek、pop等。

1.成员变量

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

LinkedList的主要成员变量就3个，大小size、头结点first、尾节点last，这也符合双向链表的特点，根据头或者尾部节点就可以遍历整个链表。至于节点类型，则是内部类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;
        }
    }

Node类就简简单单三个属性，也即双向链表节点必须的3个要素，当前节点数据item，下一节点next和上一节点prev。

2.构造方法

    public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        // 添加所有元素
        addAll(c);
    }

LinkedList主要就两个构造方法，一个无参的构造，什么也没做，另一个接受集合的构造，该方法初始化了LinkedList对象并添加了所有集合c的元素。

至于addAll方法，我们后面再看。

LinkedList因为基于链表，所以不需要提前申请内存大小，也就不存在初始化指定容量大小，因而LinkedList是没有初始化指定size的构造方法的。

3.添加元素

3.1.尾部添加

LinkedList的添加方法有很多，首先最简单也是最常用的尾部添加。

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

主要逻辑就是linkLast(E e) 了。

    void linkLast(E e) {
        final Node<E> l = last;
        // 构造新的节点，上一节点指向原来的last
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        // 操作数自增
        modCount++;
    }

尾部添加，就是构造新的节点newNode，并将改节点的上一节点prev指向原来的last，同时改节点为新的last节点。l == null判断是否当前是第一次添加，如果 l 为 null，则newNode同时也是头结点，当前集合中仅有newNode一个元素，不为null时，因为双向链表，所有 l 的下一个节点next指向了newNode。

最后就是大小size自增与操作计数modCount的自增，尾部添加元素就完成了。

尾部操作除了add，还有个addLast(E e) 方法，两者除了返回值不一样，没有任何差别了，都是调用的linkLast方法。

    public void addLast(E e) {
        linkLast(e);
    }
3.2.中间添加
    public void add(int index, E element) {
        // 范围检查
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

对于中间添加，需要首先进行范围检查，即保证插入位置index在[0, size]之间，否则抛出数组越界异常IndexOutOfBoundsException，呃……数组越界……

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

如果index == size，其实就是尾部插入，所以调用了linkLast，这个刚刚尾部插入已经说过。

如果index < size，中间插入的时候，需要分两步：

  1. node(int index)方法获取到index位置的元素succ
  2. linkBefore(E e, Node<E> succ)将需要插入的元素element连接到succ后面

node方法是一个频繁被调用的方法，LinkedList 的很多操作都依赖于该方法查找到对应的元素。根据索引 index 获取元素时，因为双向链表的支持前后遍历，所以进行了位置判断，index < (size >> 1)，与中间位置比较，靠前则前序遍历，否则后序遍历。

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

遍历逻辑很简单，循环到index上一个节点（后序则是下一个）位置，获取next（后序使用prev）返回index位置对应的节点Node对象succ。

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        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++;
    }

linkBefore和linkLast几乎完全一样，除了一个是添加到 last 节点后，一个是添加到 succ 节点后。

对于中间插入，如果index为0时，其实就是头部插入，这个时候比不用调用node方法去查找元素了，所以LinkedList也提供了一个addFirst(E e)方法。

    public void addFirst(E e) {
        linkFirst(e);
    }

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

LinkedList提供尾部批量插入和中间批量插入，但内部实现其实都是调用的addAll(int index, Collection<? extends E> c)。

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, 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;
        // succ是index位置元素，pred是index的前一个元素
        Node<E> pred, succ;
        if (index == size) { // 尾部插入
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
		// 循环插入
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        // 衔接处理
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        
        size += numNew;
        modCount++;
        return true;
    }

addAll(int index, Collection<? extends E> c)方法初一看，好像有些复杂，但明白其原理后，就变得清晰多了。链表插入就如同接水管，先从某一个位置断开水管，然后用接口连接上需要接入的部分。这个方法里，关键的是两个Node对象pred, 和 succ，succ 是index位置元素，pred是index的前一个元素（变动）。

特殊情况 index == size 时，即尾部插入，所以succ 就是null了，而 pred则为尾部节点last。

然后就是循环赋值了，在循环中构造node节点，类似于linkLast。

最后的是衔接处理，如果尾部插入的话，那pred就是尾部节点了（循环赋值时有pred = newNode处理），所以只需要指定last = pred。而中间插入，指明 pred.next = succ、succ.prev = pred即将index位置与新的前一个元素绑定到一起。

4.查找元素

LinkedList 除了提供通用的 get，因为其属性中含有 first 和 last 节点，也提供了 getFirst 和 getLast 方法。

    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

对于getFirst 和 getLast，因为是成员变量，省去了查找的过程，直接返回其节点 item 即可。

    public E get(int index) {
        // 范围校验
        checkElementIndex(index);
        // node方法获取节点
        return node(index).item;
    }

而通过指针的获取，主要就是调用node方法找对index对应的节点，node方法前面已经讲过，不再累述。

5.修改元素

对于LinkedList集合中元素的修改，需要先查找到该元素，然后更改其Node节点数据item即可。

    public E set(int index, E element) {
        // 范围检查
        checkElementIndex(index);
        // 获取index对应位置的Node对象
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

6.删除元素

LinkedList提供了很多种删除元素的方法，但是内部实现逻辑基本都相同，即找到对应的Node节点，然后将指向该节点的指向替换。

6.1.根据索引移除

我们先来看看根据索引的remove(int index)方法。

    public E remove(int index) {
        // 范围检查
        checkElementIndex(index);
        // 解除节点指针连接
        return unlink(node(index));
    }

删除时的范围检查就不说了，node方法也不再多提，删除的主要逻辑就是unlink(Node<E> 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;
		// 前一节点prev存在则将prev的下一节点指向next，不存在则当前移除节点其实就是头结点，next就是新的first
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
		// 下一节点next存在，则将next上一节点指向prev，不存在则说明当前移除的是未节点
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
		// 触发GC工作
        x.item = null;
        size--;
        // 操作计数器自增
        modCount++;
        return element;
    }

整个unlink方法就是个标准的双向链表删除操作，三个节点prev，x，next，删除x 其实就是将 prev指向next，并next指向prev，只是其中多了一些特殊的判断。

看了按索引删除的remove，再来看另外两个特例removeFirst 和 removeLast。

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        // 操作计数器自增
        modCount++;
        return element;
    }

unlinkFirst就是个简化版的unlink方法，因为只用处理头结点，下一个节点next存在就将next作为新的first。

同理removeLast也是类似，这里各位看官自行进行体会。

    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

而LinkedList还有个无参的remove，这个是Deque接口定义的，实现也就是调用的removeFirst。

    public E remove() {
        return removeFirst();
    }
6.2.根据元素移除

根据元素移除其实和根据索引移除没有太大差别，只不过找到对应节点的方式发生了变化。

    public boolean remove(Object o) {
        // 判断元素是否为null，因为LinkedList支持添加null
        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;
    }

可以看到，无论元素是否为null，都是先找到该节点，然后调用了unlink方法。

因为支持双向遍历的特性，LinkedList很人性的提供了前序删除和后序删除的方法，即removeFirstOccurrence与removeLastOccurrence。

    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            // 后序遍历
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            // 后序遍历
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

这两个方法没什么玄幻的，removeLastOccurrence只是反序遍历了集合。

6.3.批量删除

在LinkedList类中，并没有removeAll方法，因为他未对其进行重写，而是使用了父类AbstractCollection的

    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        // 使用迭代器
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

removeAll的实现原理其实就是迭代删除，迭代器的获取方法iterator()在AbstractCollection类中只是个抽象方法，AbstractList类有其实现，但AbstractSequentialList类中覆写该方法。

    public Iterator<E> iterator() {
        return listIterator();
    }

iterator方法会调用listIterator()，这个方法实现在AbstractList类中，他调用了listIterator(int index)方法，但LinkedList重写了该方法，所以兜兜转转最终还是回到了LinkedList中。

    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

这里ListItr对象是LinkedList的内部类。

    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        // 期待计数器
        private int expectedModCount = modCount;

ListItr在初始化的时候，会将操作计数器modCount赋值给expectedModCount，而之后的每次remove方法，都会校验expectedModCount与modCount是否相等，否则会抛出异常。

ListItr的remove方法，每次调用后，都将expectedModCount自增，已达到和unlink中modCount++的同步，从而使得modCount == expectedModCount 一直成立，这也是为什么我们循环删除LinkedList元素时需要使用其迭代器的remove方法。

        public void remove() {
            // 校验modCount
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            // unlink删除节点逻辑，该方法中有modCount++;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            // expectedModCount自增
            expectedModCount++;
        }

        final void checkForComodification() {
            // expectedModCount与modCount必须相等
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

原文出处：https://www.cnblogs.com/imyanger/p/11980409.html

0004--jcf (jdk1.7)-LinkedList 源码

0004--jcf (jdk1.7)-LinkedList 源码

1.     LinkedList 的定义
内部是一个链式结构的实现。它还实现了 Deque 接口。可以当作一个队列，堆栈或双端队列使用。其类定义如下：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

关于 AbstractSequentialList，它对 List 的这些接口进行了实现。

get(int): E
set(int, E): E
add(int, E): void
remove(int): E
addAll(int, Collection<? extends E>): boolean

如果我们需要自己实现一个 List，可以扩展此类，我们只需要实现 listIterator () 和 size () 方法即可。我们也可以基于此类，实现可修改和不可修改的 List。如果想实现一个不修改的列表，只需要我们实现 list iterator 的 hasNext,next,hasPrevious,previous 以及 index 方法。而实现一个可以修改的列表，需要实现 list iterator 的 set 方法。如果要实现可变大小的列表，还应该提供 list iterator 的 remove 方法。

了解一下双向链表的结构


2.    LinkedList 的实现

它有三个属性：

transient int size;    --存储的元素个数
transient Node<E> first;--头节点
transient Node<E> last;--尾节点

关于 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;
    }
}

提供了两个构造函数：

public LinkedList() {
}

//以指定列表元素创建一个LinkedList列表
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(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;

    // 定义两个临时变量pred前一个节点，succ下一个节点。用来存储index处的前后节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;    // 这里succ有可能为null
    }

    //    以pred节点为起点，构造了一个双向链表
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;//此时pred指向了这个链表的最后节点
    }

    // 将index处的节点与上面的链表链接
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

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

第一个构造函数就什么也没做，它的 first 与 last 都是为 null。

第二个构造函数，用指定列表构造了一个双链表。

index 是从 0 开始的，当 index==size 的时候，表示是从之前列表的末节点开始插入元素。

3. LinkedList 列表元素的操作

1).    增加

有如下向列表添加元素的方法：

add(E): boolean
add(int, E): boolean
addAll(Collection<? extends E>): boolean
addAll(int, Collection<? extends E>): boolean

其中 addAll (int, Collection<? extends E>) 已经在上面构造函数里提过。看下其它几个方法。

  • add(E)

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

  • add(int, E)

public void add(int index, E element) {
    checkPositionIndex(index);
    // 当是在列表末尾添加元素
    if (index == size)
        linkLast(element);
    else    // 在指定位置插入元素
        linkBefore(element, node(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;
    }
}

void linkLast(E e) {
    final Node<E> l = last;
    // 构造插入的节点
    final Node<E> newNode = new Node<>(l, e, null);    
    //更新最后节点为当前节点
    last = newNode;    
    // 更新之前那个最后节点的next指向这个新加入的节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // succ的前一个节点
    final Node<E> pred = succ.prev;    
    // 构造插入的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将节点链接到succ的prev指向处
    succ.prev = newNode;
    // 将succ的最开始prev指向的节点指向新增节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

  • addFirst(E)

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    // 构造新增节点
    final Node<E> newNode = new Node<>(null, e, f);
    // 将新增节点指向first节点
    first = newNode;
    // 更新之前头结点指向新增节点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

  • addLast(E)

public void addLast(E e) {
    linkLast(e);
}

2).    查询

查询接口有如下几个方法：

get(int): E
indexOf(Object): int
lastIndexOf(Object): int

  • get(int)

public E get(int index) {
    // index范围判定
    checkElementIndex(index);
    return node(index).item;
}

  • indexOf (object) 查找元素第一次出现的位置，未找到则返回 - 1

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

  • lastIndexOf (Object) 查找元素最后一次出现的位置，未找到则返回 - 1

public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

3).    修改

提供的修改接口有：

set(int, E): E

  • set (int, E) 源码如下：

public E set(int index, E element) {
    checkElementIndex(index);   // 位置判定，会抛出异常IndexOutOfBoundsException
    Node<E> x = node(index);    // 查找指定位置元素，并替换
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

4).    删除

remove(int): E
remove(Object): boolean
clear()

  • remove(int)

public E remove(int index) {
    checkElementIndex(index);    //会抛出IndexOutOfBoundsException
    return unlink(node(index));
}

// 将删除元素的前后节点都更改
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;

    // 删除的是首节点，那么x节点的下一个节点将成为首节点
    if (prev == null) {
        first = next;
    } else ｛
        // 将x节点的前一个节点链接到x的下一个节点
        prev.next = next;
        // 释放x节点的前节点的指向
        x.prev = null;
    }

    // 如果删除的是尾节点，那么x节点的前一个节点将是末节点
    if (next == null) {
        last = prev;
    } else {
        // 将x节点的后节点指向x的前一个节点
        next.prev = prev;
        // 释放x节点的后节点指向
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    // 返回被删除的元素
    return element;
}

  • remove (Object)，此方法返回的是 boolean 值

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

  • clear()

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

4.    LinkedList 的其它方法

clone()
toArray(): Object[]
toArray(T[]): T[]
subList(int, int)

  • clone (): 浅复制

public Object clone() {
    LinkedList<E> clone = superClone();

    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // Initialize clone with our elements
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}
private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError();
    }
}

  • toArray()

// 数组大小为列表拥有的元素个数
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

  • toArray(T[])

//
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;

    if (a.length > size)
        a[size] = null;

    return a;
}

  • subList(int, int)

// LinkedList没有重写subList方法，所以它默认是继承AbstractList的subList方法

public List<E> subList(int fromIndex, int toIndex) {
    return new SubList<>(this, fromIndex, toIndex);
}
class SubList<E> extends AbstractList<E> {
    private final AbstractList<E> l;
    private final int offset;
    private int size;

    SubList(AbstractList<E> list, int fromIndex, int toIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        this.modCount = l.modCount;
    }

5.    内部类 ListItr 迭代

获取 ListItr 迭代器：(这两个方法都是 List 中接口的，其中 ListIterator<E> () 接口是在 AbstractList 中实现的。

ListIterator<E> (){
return listIterator(0);
}

ListIterator<E> (index) {
    checkPositionIndex(index)ListItr(index)}

ListIterator 是基于 fail-fast 机制的：当 list iterator 被创建之后，任何对 list 的结构性修改（remove,add) 将会抛出 ConcurrentModificationException。(但是我在跑以下代码的时候，没有抛出异常)

// 这段代码在jdk1.6上面跑，会抛出ConcurrentModificationException. 但jdk1.7没有异常
        List<Integer> mLinkedList = new LinkedList<Integer>();
        mLinkedList.add(2);
        mLinkedList.add(3);
        Iterator<Integer> mItrLinkedList = mLinkedList.iterator();
        while (mItrLinkedList.hasNext()) { 
            Integer mInteger = mItrLinkedList.next(); // index++
            mLinkedList.remove(mInteger); //size--
//            mItrLinkedList.remove();
        }
        System.out.println(mLinkedList);
// 输出结果
[3]

// 下面这段代码回抛出异常ConcurrentModificationException（jdk1.6和jdk1.7都会）
List<Integer> mArrayList = new ArrayList<Integer>();
mArrayList.add(2);
Iterator<Integer> mItrArrayList = mArrayList.iterator();
while (mItrArrayList.hasNext()) {
    Integer mInteger = mItrArrayList.next();
    mArrayList.remove(mInteger);
}

/*
原因：jdk1.7中ListItr迭代器里面hasNext()方法是retrun nextIndex < size;
当调用list的remove(Object)时候，size--。迭代时nextIndex++，不满足nextIndex<size了，所以jdk1.7已经不会进入下一次next()了，就没有抛出异常。
jdk1.6中hasNext()方法是return nextIndex != size;但是即便如此，如果LinkedList中含有两个元素，在jdk1.6中也不会抛出这个异常，因为index++ == size--了。
*/

ListItr 的属性以及构造函数

private class ListItr implements ListIterator<E> {
    // 迭代过程中，存储当前的元素
    private Node<E> lastReturned = null;
    // 游标元素，构造的时候是index处的节点
    private Node<E> next;
    // 构造的时候是当前index值
    private int nextIndex;
    private int expectedModCount = modCount;
    
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
}

ListIterator 阔咱了 Iterator 接口，增加了访问前一个元素的功能

public boolean hasPrevious() {
    return nextIndex > 0;
}

public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();

    //返回前一节点，这里判定next==null的情况：ListItr的构造函数里面，当index==size的时候，next被赋值为null
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}
public void remove() {
    checkForComodification();
    if (lastReturned == null)
        throw new IllegalStateException();

    // lastReturned保存了上次返回的那个元素
    Node<E> lastNext = lastReturned.next;
    unlink(lastReturned);    //删除上次那个元素
    if (next == lastReturned)
        next = lastNext;
    else
        nextIndex--;
    lastReturned = null;
    expectedModCount++;
}

public void set(E e) {
    if (lastReturned == null)
        throw new IllegalStateException();
    checkForComodification();
    lastReturned.item = e;
}

public void add(E e) {
    checkForComodification();
    lastReturned = null;
    if (next == null)
        linkLast(e);
    else
        linkBefore(e, next);
    nextIndex++;
    expectedModCount++;
}



6.     LinkedList 提供关于队列的操作方法

getFirst(): E // 返回第一个元素，当list为空会抛出NoSuchElementException
getLast(): E  // 返回列表最后一个元素，当list为空会抛出NoSuchElementException

removeFirst(): E // 删除并返回第一个元素，当list为空会抛出NoSuchElementException
removeLast(): E  // 删除并返回列表最后一个元素，当list为空会抛出NoSuchElementException

addFirst(E): void   // 向list列表头添加元素
addLast(E): void    // 向列表尾添加元素

peek(): E // 获取列表头元素，当元素列表为空的时候，会返回null
element(): E // 获取列表头元素，当元素列表为空的时候，会抛出异常NoSuchElementException
poll(): E    // 获取并删除头元素，当元素列表为空的时候，会返回null
offer(): boolean    // 添加元素至列表尾
offerFirst(): boolean    // 添加元素在列表头
offerLast(): boolean    // 添加元素至列表尾

peekFirst(): E // 获取列表头元素，当元素列表为空的时候，返回null
peekLast(): E  // 返回列表尾元素，当元素列表为空的时候，返回null
pollFirst(): E // 获取并删除头元素，当列表为空，返回null
pollLast(): E  // 获取并删除尾元素，当列表为空，返回null
push(E): void  // 向栈顶置入元素
pop(): E        // 出栈
removeFirstOccurrence(Object): boolean
removeLastOccurrence(Object): boolean

  • removeFirst()

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    // 将first.next作为first
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    // 返回被删除的头节点元素
    return element;
}

  • removeLast()

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    // 将last.prev作为末节点
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}









ArrayList与LinkedList的区别以及JDK11中的底层实现

ArrayList与LinkedList的区别以及JDK11中的底层实现

1 概述

本文主要讲述了ArrayList与LinkedList的相同以及不同之处，以及两者的底层实现（环境OpenJDK 11.0.12）。

2 两者区别

在详细介绍两者的底层实现之前，先来简单看一下两者的异同。

2.1 相同点

  • 两者都实现了List接口，都继承了AbstractList（LinkedList间接继承，ArrayList直接继承）
  • 都是线程不安全的，两者都是不同步的
  • 都具有增删查改方法

2.2 不同点

  • 底层数据结构不同：ArrayList基于Object[]数组，LinkedList基于LinkedList.Node双向链表
  • 随机访问效率不同：ArrayList随机访问能做到O(1)（实现 RandomAccess），因为可以直接通过下标找到元素，而LinkedList需要从头指针开始遍历，时间O(n)
  • 初始化操作不同：ArrayList无参初始化时初始化为一个空数组，而LinkedList不需要
  • 扩容：ArrayList当长度不足以容纳新元素的时候，会进行扩容，而LinkedList不会
  • 内存空间占用：ArrayList的内存空间占用主要体现在数组结尾会预留一定容量空间，而LinkedList空间花费主要体现在每一个元素都需要消耗比ArrayList更多的空间

3 ArrayList底层

3.1 基本结构

底层使用Object[]数组实现，成员变量如下：

private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = 2147483639;

默认的初始化容量为10，接下来是两个空数组，供默认构造方法以及带初始化容量的构造方法使用：

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

        this.elementData = EMPTY_ELEMENTDATA;
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

下面再来看一些重要方法，包括：

  • add()
  • remove()
  • indexOf()/lastIndexOf()/contains()

3.2 add()

add()方法有四个：

  • add(E e)
  • add(int index,E e)
  • addAll(Collection<? extends E> c)
  • addAll(int index, Collection<? extends E> c

3.2.1 单一元素add()

先来看一下add(E e)以及add(int index,E eelment)：

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) {
        elementData = this.grow();
    }

    elementData[s] = e;
    this.size = s + 1;
}

public boolean add(E e) {
    ++this.modCount;
    this.add(e, this.elementData, this.size);
    return true;
}

public void add(int index, E element) {
    this.rangeCheckForAdd(index);
    ++this.modCount;
    int s;
    Object[] elementData;
    if ((s = this.size) == (elementData = this.elementData).length) {
        elementData = this.grow();
    }

    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    this.size = s + 1;
}

add(E e)实际调用的是一个私有方法，判断是否需要扩容之后，直接添加到末尾。而add(int index,E element)会首先检查下标是否合法，合法的话，再判断是否需要扩容，之后调用System.arraycopy对数组进行复制，最后进行赋值并将长度加1。

关于System.arraycopy，官方文档如下：

在这里插入图片描述

一共有5个参数：

  • 第一个参数：原数组
  • 第二个参数：原数组需要开始复制的位置
  • 第三个参数：目标数组
  • 第四个参数：复制到目标数组的开始位置
  • 第五个参数：需要复制的数目

也就是说：

System.arraycopy(elementData, index, elementData, index + 1, s - index);

的作用是将原数组在index后面的元素“往后挪”，空出一个位置让index进行插入。

3.2.2 addAll()

下面来看一下两个addAll()：

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    ++this.modCount;
    int numNew = a.length;
    if (numNew == 0) {
        return false;
    } else {
        Object[] elementData;
        int s;
        if (numNew > (elementData = this.elementData).length - (s = this.size)) {
            elementData = this.grow(s + numNew);
        }

        System.arraycopy(a, 0, elementData, s, numNew);
        this.size = s + numNew;
        return true;
    }
}

public boolean addAll(int index, Collection<? extends E> c) {
    this.rangeCheckForAdd(index);
    Object[] a = c.toArray();
    ++this.modCount;
    int numNew = a.length;
    if (numNew == 0) {
        return false;
    } else {
        Object[] elementData;
        int s;
        if (numNew > (elementData = this.elementData).length - (s = this.size)) {
            elementData = this.grow(s + numNew);
        }

        int numMoved = s - index;
        if (numMoved > 0) {
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        }

        System.arraycopy(a, 0, elementData, index, numNew);
        this.size = s + numNew;
        return true;
    }
}

在第一个addAll中，首先判断是否需要扩容，接着也是直接调用目标集合添加到尾部。而在第二个addAll中，由于多了一个下标参数，处理步骤稍微多了一点：

  • 首先判断下标是否合法
  • 接着判断是否需要扩容
  • 再计算是否需要把原来的数组元素“往后挪”，也就是if里面的System.arraycopy
  • 最后把目标数组复制到指定的index位置

3.2.3 扩容

上面的add()方法都涉及到了扩容，也就是grow方法，下面来看一下：

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
}

private Object[] grow() {
    return this.grow(this.size + 1);
}

private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        } else if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) {
        throw new OutOfMemoryError();
    } else {
        return minCapacity > 2147483639 ? 2147483647 : 2147483639;
    }
}

grow()首先通过newCapacity计算需要扩容的容量，接着调用Arrays.copyOf将旧元素复制过去，并将返回值覆盖到原来的数组。而在newCapacity中，有两个变量：

  • newCapacity：新的容量，默认是旧容量的1.5倍，也就是默认扩容1.5倍
  • minCapacity：最低需要的容量

如果最低容量大于等于新容量，则是如下情况之一：

  • 通过默认构造初始化的数组：返回minCapacity与10的最大值
  • 溢出：直接抛OOM
  • 否则返回最小容量值

如果不是，则判断新容量是否达到最大值（这里有点好奇为什么不用MAX_ARRAY_SIZE，猜测是反编译的问题），如果没有到达最大值，则返回新容量，如果到达了最大值，调用hugeCapacity。

hugeCapacity同样会首先判断最小容量是否小于0，小于则抛OOM，否则将其与最大值（MAX_ARRAY_SIZE）判断，如果大于返回Integer.MAX_VALUE，否则返回MAX_ARRAY_SIZE。

3.3 remove()

remove()包含四个方法：

  • remove(int index)
  • remove(Object o)
  • removeAll()
  • removeIf()

3.3.1 单一元素remove()

也就是remove(int index)以及remove(Object o)：

public E remove(int index) {
    Objects.checkIndex(index, this.size);
    Object[] es = this.elementData;
    E oldValue = es[index];
    this.fastRemove(es, index);
    return oldValue;
}

public boolean remove(Object o) {
    Object[] es = this.elementData;
    int size = this.size;
    int i = 0;
    if (o == null) {
        while(true) {
            if (i >= size) {
                return false;
            }

            if (es[i] == null) {
                break;
            }

            ++i;
        }
    } else {
        while(true) {
            if (i >= size) {
                return false;
            }

            if (o.equals(es[i])) {
                break;
            }

            ++i;
        }
    }

    this.fastRemove(es, i);
    return true;
}

其中remove(int index)的逻辑比较简单，先检查下标合法性，然后保存需要remove的值，并调用fastRemove()进行移除，而在remove(Object o)中，直接对数组进行遍历，并判断是否存在对应的元素，如果不存在直接返回false，如果存在，调用fastRemove()，并返回true。

下面看一下fastRemove()：

private void fastRemove(Object[] es, int i) {
    ++this.modCount;
    int newSize;
    if ((newSize = this.size - 1) > i) {
        System.arraycopy(es, i + 1, es, i, newSize - i);
    }

    es[this.size = newSize] = null;
}

首先修改次数加1，然后将数组长度减1，并判断新长度是否是最后一个，如果是最后一个则不需要移动，如果不是，调用System.arraycopy将数组向前“挪”1位，最后将末尾多出来的一个值置为null。

3.3.2 removeAll()

public boolean removeAll(Collection<?> c) {
    return this.batchRemove(c, false, 0, this.size);
}

boolean batchRemove(Collection<?> c, boolean complement, int from, int end) {
    Objects.requireNonNull(c);
    Object[] es = this.elementData;

    for(int r = from; r != end; ++r) {
        if (c.contains(es[r]) != complement) {
            int w = r++;

            try {
                for(; r < end; ++r) {
                    Object e;
                    if (c.contains(e = es[r]) == complement) {
                        es[w++] = e;
                    }
                }
            } catch (Throwable var12) {
                System.arraycopy(es, r, es, w, end - r);
                w += end - r;
                throw var12;
            } finally {
                this.modCount += end - w;
                this.shiftTailOverGap(es, w, end);
            }

            return true;
        }
    }

    return false;
}

removeAll实际上调用的是batchRemove()，在batchRemove()中，有四个参数，含义如下：

  • Collection<?> c：目标集合
  • boolean complement：如果取值true，表示保留数组中包含在目标集合c中的元素，如果为false，表示删除数组中包含在目标集合c中的元素
  • from/end：区间范围，左闭右开

所以传递的(c,false,0,this.size)表示删除数组里面在目标集合c中的元素。下面简单说一下执行步骤：

  • 首先进行判空操作
  • 接着找到第一符合要求的元素（这里是找到第一个需要删除的元素）
  • 找到后从该元素开始继续向后查找，同时记录删除后的数组中最后一个元素的下标w
  • try/catch是一种保护性行为，因为contains()在AbstractCollection的实现中，会使用Iterator，这里catch异常后仍然调用System.arraycopy，使得已经处理的元素“挪到”前面
  • 最后会增加修改的次数，并调用shiftTailOverGap，该方法在后面会详解

3.3.3 removeIf()

public boolean removeIf(Predicate<? super E> filter) {
    return this.removeIf(filter, 0, this.size);
}

boolean removeIf(Predicate<? super E> filter, int i, int end) {
    Objects.requireNonNull(filter);
    int expectedModCount = this.modCount;

    Object[] es;
    for(es = this.elementData; i < end && !filter.test(elementAt(es, i)); ++i) {
    }

    if (i < end) {
        int beg = i;
        long[] deathRow = nBits(end - i);
        deathRow[0] = 1L;
        ++i;

        for(; i < end; ++i) {
            if (filter.test(elementAt(es, i))) {
                setBit(deathRow, i - beg);
            }
        }

        if (this.modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        } else {
            ++this.modCount;
            int w = beg;

            for(i = beg; i < end; ++i) {
                if (isClear(deathRow, i - beg)) {
                    es[w++] = es[i];
                }
            }

            this.shiftTailOverGap(es, w, end);
            return true;
        }
    } else if (this.modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    } else {
        return false;
    }
}

在removeIf中，删除符合条件的元素，首先会进行判空操作，然后找到第一个符合条件的元素下标，如果找不到（i>=end），判断是否有并发操作问题，没有的话返回false，如果i<end，也就是正式进入删除流程：

  • 记录开始下标beg
  • deathRow是一个标记数组，长度为(end-i-1)>>6 + 1，从beg开始如果遇到符合条件的元素就对下标进行标记（调用setBit）
  • 标记后进行删除，所谓的删除其实就是把后面不符合条件的元素逐个移动到beg之后的位置上
  • 调用shiftTailOverGap处理末尾的元素
  • 返回true，表示存在符合条件的元素并进行了删除操作

3.3.4 shiftTailOverGap()

上面的removeAll()以及removeIf()都涉及到了shiftTailOverGap()，下面来看一下实现：

private void shiftTailOverGap(Object[] es, int lo, int hi) {
    System.arraycopy(es, hi, es, lo, this.size - hi);
    int to = this.size;

    for(int i = this.size -= hi - lo; i < to; ++i) {
        es[i] = null;
    }

}

该方法将es数组中的元素向前移动hi-lo位，并将移动之后的在末尾多出来的那部分元素置为null。

3.4 indexOf()系列

包括：

  • indexOf()
  • lastIndexOf()
  • contains()

3.4.1 indexOf

public int indexOf(Object o) {
    return this.indexOfRange(o, 0, this.size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = this.elementData;
    int i;
    if (o == null) {
        for(i = start; i < end; ++i) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for(i = start; i < end; ++i) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }

    return -1;
}

indexOf()实际上是一个包装好的方法，会调用内部的indexOfRange()进行查找，逻辑很简单，首先判断需要查找的值是否为空，如果不为空，使用equals()判断，否则使用==判断，找到就返回下标，否则返回-1。

3.4.2 contains()

contains()实际上是indexOf()的包装：

public boolean contains(Object o) {
    return this.indexOf(o) >= 0;
}

调用indexOf()方法，根据返回的下标判断是否大于等于0，如果是则返回存在，否则返回不存在。

3.4.3 lastIndexOf()

lastIndexOf()实现与indexOf()类似，只不过是从尾部开始遍历，内部调用的是lastIndexOfRange()：

public int lastIndexOf(Object o) {
    return this.lastIndexOfRange(o, 0, this.size);
}

int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = this.elementData;
    int i;
    if (o == null) {
        for(i = end - 1; i >= start; --i) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for(i = end - 1; i >= start; --i) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }

    return -1;
}

4 LinkedList底层

4.1 基本结构

首先来看一下里面的成员变量：

transient int size;
transient LinkedList.Node<E> first;
transient LinkedList.Node<E> last;
private static final long serialVersionUID = 876323262645176354L;

一个表示长度，一个头指针和一个尾指针。

其中LinkedList.Node实现如下：

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

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

可以看到LinkedList实际是基于双链表实现的。

下面再来看一些重要方法，包括：

  • add()
  • remove()
  • get()

4.2 add()

add()方法包括6个：

  • add(E e)
  • add(int index,E e)
  • addFirst(E e)
  • addLast(E e)
  • addAll(Collection<? extends E> c)
  • addAll(int index, Collection<? extends E> c)

4.2.1 linkFirst/linkLast/linkBefore实现的add()

先看一下比较简单的四个add()：

public void addFirst(E e) {
    this.linkFirst(e);
}

public void addLast(E e) {
    this.linkLast(e);
}

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

public void add(int index, E element) {
    this.checkPositionIndex(index);
    if (index == this.size) {
        this.linkLast(element);
    } else {
        this.linkBefore(element, this.node(index));
    }
}

可以看到，上面的四个add()不进行任何的添加元素操作，add()只是添加元素的封装，真正实现add操作的是linkLast()、linkFirst()和linkBefore()，这些方法顾名思义就是把元素链接到链表的末尾或者头部，或者链表某个节点的前面：

void linkLast(E e) {
    LinkedList.Node<E> l = this.last;
    LinkedList.Node<E> newNode = new LinkedList.Node(l, e, (LinkedList.Node)null);
    this.last = newNode;
    if (l == null) {
        this.first = newNode;
    } else {
        l.next = newNode;
    }

    ++this.size;
    ++this.modCount;
}

private void linkFirst(E e) {
    LinkedList.Node<E> f = this.first;
    LinkedList.Node<E> newNode = new LinkedList.Node((LinkedList.Node)null, e, f);
    this.first = newNode;
    if (f == null) {
        this.last = newNode;
    } else {
        f.prev = newNode;
    }

    ++this.size;
    ++this.modCount;
}

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

    ++this.size;
    ++this.modCount;
}

实现大体相同，一个是添加到尾部，一个是添加头部，一个是插入到前面。另外，三者在方法的最后都有如下操作：

++this.size;
++this.modCount;

第一个表示节点的个数加1，而第二个，则表示对链表的修改次数加1。

比如，在unlinkLast方法的最后，有如下代码：

--this.size;
++this.modCount;

unlinkLast操作就是移除最后一个节点，节点个数减1的同时，对链表的修改次数加1。

另一方面，通常来说链表插入操作需要找到链表的位置，但是在三个link方法里面，都看不到for循环找到插入位置的代码，这是为什么呢？

由于保存了头尾指针，linkFirst()以及linkLast()并不需要遍历找到插入的位置，但是对于linkBefore()来说，需要找到插入的位置，不过linkBefore()并没有类似“插入位置/插入下标”之类的参数，而是只有一个元素值以及一个后继节点。换句话说，这个后继节点就是通过循环得到的插入位置，比如，调用的代码如下：

this.linkBefore(element, this.node(index));

可以看到在this.node()中，传入了一个下标，并返回了一个后继节点，也就是遍历操作在该方法完成：

LinkedList.Node<E> node(int index) {
    LinkedList.Node x;
    int i;
    if (index < this.size >> 1) {
        x = this.first;

        for(i = 0; i < index; ++i) {
            x = x.next;
        }

        return x;
    } else {
        x = this.last;

        for(i = this.size - 1; i > index; --i) {
            x = x.prev;
        }

        return x;
    }
}

这里首先通过判断下标是位于“哪一边”，如果靠近头部，从头指针开始往后遍历，如果靠近尾部，从尾指针开始向后遍历。

4.2.2 遍历实现的addAll()

public boolean addAll(Collection<? extends E> c) {
    return this.addAll(this.size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    this.checkPositionIndex(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0) {
        return false;
    } else {
        LinkedList.Node pred;
        LinkedList.Node succ;
        if (index == this.size) {
            succ = null;
            pred = this.last;
        } else {
            succ = this.node(index);
            pred = succ.prev;
        }

        Object[] var7 = a;
        int var8 = a.length;

        for(int var9 = 0; var9 < var8; ++var9) {
            Object o = var7[var9];
            LinkedList.Node<E> newNode = new LinkedList.Node(pred, o, (LinkedList.Node)null);
            if (pred == null) {
                this.first = newNode;
            } else {
                pred.next = newNode;
            }

            pred = newNode;
        }

        if (succ == null) {
            this.last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        this.size += numNew;
        ++this.modCount;
        return true;
    }
}

首先可以看到两个addAll实际上调用的是同一个方法，步骤简述如下：

  • 首先通过checkPositionIndex判断下标是否合法
  • 接着把目标集合转为Object[]数组
  • 进行一些特判处理，判断index的范围是插入中间，还是在末尾插入
  • for循环遍历目标数组，并插入到链表中
  • 修改节点长度，并返回

4.3 remove()

与add()类似，remove包括：

  • remove()
  • remove(int index)
  • remove(Object o)
  • removeFirst()
  • removeLast()
  • removeFirstOccurrence(Object o)
  • removeLastOccurrence(Object o)

当然其实还有两个removeAll与removeIf，但实际上是父类的方法，这里就不分析了。

4.3.1 unlinkFirst()/unlinkLast()实现的remove()

remove()、removeFirst()、removeLast()实际上是通过调用unlinkFirst()/unlinkLast()进行删除的，其中remove()只是removeFirst()的一个别名：

public E remove() {
    return this.removeFirst();
}

public E removeFirst() {
    LinkedList.Node<E> f = this.first;
    if (f == null) {
        throw new NoSuchElementException();
    } else {
        return this.unlinkFirst(f);
    }
}

public E removeLast() {
    LinkedList.Node<E> l = this.last;
    if (l == null) {
        throw new NoSuchElementException();
    } else {
        return this.unlinkLast(l);
    }
}

逻辑很简单，判空之后，调用unlinkFirst()/unlinkLast()：

private E unlinkFirst(LinkedList.Node<E> f) {
    E element = f.item;
    LinkedList.Node<E> next = f.next;
    f.item = null;
    f.next = null;
    this.first = next;
    if (next == null) {
        this.last = null;
    } else {
        next.prev = null;
    }

    --this.size;
    ++this.modCount;
    return element;
}

private E unlinkLast(LinkedList.Node<E> l) {
    E element = l.item;
    LinkedList.Node<E> prev = l.prev;
    l.item = null;
    l.prev = null;
    this.last = prev;
    if (prev == null) {
        this.first = null;
    } else {
        prev.next = null;
    }

    --this.size;
    ++this.modCount;
    return element;
}

而在这两个unlink中，由于已经保存了头指针和尾指针的位置，因此两者可以直接在O(1)内进行移除操作，最后将节点长度减1，修改次数加1，并返回旧元素。

4.3.2 unlink()实现的remove()

再来看一下remove(int index)、remove(Object o)、removeFirstOccurrence(Object o)、removeLastOccurrence(Object o)：

public E remove(int index) {
    this.checkElementIndex(index);
    return this.unlink(this.node(index));
}

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

    return false;
}

public boolean removeFirstOccurrence(Object o) {
    return this.remove(o);
}

public boolean removeLastOccurrence(Object o) {
    LinkedList.Node x;
    if (o == null) {
        for(x = this.last; x != null; x = x.prev) {
            if (x.item == null) {
                this.unlink(x);
                return true;
            }
        }
    } else {
        for(x = this.last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                this.unlink(x);
                return true;
            }
        }
    }

    return false;
}

这几个方法实际上都是调用unlink去移除元素，其中removeFirstOccurrence(Object o)等价于remove(Object o)，先说一下remove(int index)，该方法逻辑比较简单，先检查下标合法性，再通过下标找到节点并进行unlnk。

而在remove(Object o)中，需要首先对元素的值是否为null进行判断，两个循环实际上效果等价，会移除遇到的第一个与目标值相同的元素。在removeLastOccurrence(Object o)中，代码大体一致，只是remove(Object o)从头指针开始遍历，而removeLastOccurrence(Object o)从尾指针开始遍历。

可以看到，这几个remove方法实际上是找到要删除的节点，最后调用unlink()进行删除，下面看一下unlink()：

E unlink(LinkedList.Node<E> x) {
    E element = x.item;
    LinkedList.Node<E> next = x.next;
    LinkedList.Node<E> prev = x.prev;
    if (prev == null) {
        this.first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

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

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

实现逻辑与unlinkFirst()/unlinkLast()类似，在O(1)内进行删除，里面只是一些比较简单的特判操作，最后将节点长度减1，并将修改次数加1，最后返回旧值。

4.4 get()

get方法比较简单，对外提供了三个：

  • get(int index)
  • getFirst()
  • getLast()

其中getFirst()以及getLast()由于保存了头尾指针，特判后，直接O(1)返回：

public E getFirst() {
    LinkedList.Node<E> f = this.first;
    if (f == null) {
        throw new NoSuchElementException();
    } else {
        return f.item;
    }
}

public E getLast() {
    LinkedList.Node<E> l = this.last;
    if (l == null) {
        throw new NoSuchElementException();
    } else {
        return l.item;
    }
}

而get(int index)毫无疑问需要O(n)时间：

public E get(int index) {
    this.checkElementIndex(index);
    return this.node(index).item;
}

get(int index)判断下标后，实际上进行操作的是this.node()，由于该方法是通过下标找到对应的节点，源码前面也写上了，这里就不分析了，需要O(n)的时间。

5 总结

  • ArrayList基于Object[]实现，LinkedList基于双链表实现
  • ArrayList随机访问效率要高于LinkedList
  • LinkedList提供了比ArrayList更多的插入方法，而且头尾插入效率要高于ArrayList
  • 两者的删除元素方法并不完全相同，ArrayList提供了独有的removeIf()，而LinkedList提供了独有的removeFirstOccurrence()以及removeLastOccurrence()
  • ArrayList的get()方法始终为O(1)，而LinkedList只有getFirst()/getLast()为O(1)
  • ArrayList中的两个核心方法是grow()以及System.arraycopy，前者是扩容方法，默认为1.5倍扩容，后者是复制数组方法，是一个native方法，插入、删除等等操作都需要使用
  • LinkedList中很多方法需要对头尾进行特判，创建比ArrayList简单，无须初始化，不涉及扩容问题

6 附录：关于插入与删除的一个实验

关于插入与删除，通常认为LinkedList的效率要比ArrayList高，但实际上并不是这样，下面是一个测试插入与删除时间的小实验。

6.1 测试环境

  • JDK：OpenJDK 11.0.12
  • JMH：JMH 1.33
  • 系统：Manjaro 21.1.2
  • 测试数组长度：5w、50w、500w
  • 测试方法：List.add(int,E),list.remove(int)
  • 插入与删除下标：随机生成
  • 测试指标：平均时间
  • 带预热
  • 单线程

6.2 代码

package com.company;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.*;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;
import java.util.stream.Stream;

@BenchmarkMode(Mode.AverageTime)
@Fork(1)
@Warmup(iterations = 5)
@Measurement(iterations = 5)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Threads(1)
@State(Scope.Benchmark)
public class Main {
    private static final Random random = new Random();
    private static final List<Integer> data_50_000 = Stream.generate(random::nextInt).limit(50_000).collect(Collectors.toList());
    private static final List<Integer> data_500_000 = Stream.generate(random::nextInt).limit(500_000).collect(Collectors.toList());
    private static final List<Integer> data_5_000_000 = Stream.generate(random::nextInt).limit(5_000_000).collect(Collectors.toList());

    private static final String ARRAY_LIST_50_000 = "1";
    private static final String ARRAY_LIST_500_000 = "2";
    private static final String ARRAY_LIST_5_000_000 = "3";
    private static final String LINKED_LIST_50_000 = "4";
    private static final String LINKED_LIST_500_000 = "5";
    private static final String LINKED_LIST_5_000_000 = "6";

    @Param({ARRAY_LIST_50_000, ARRAY_LIST_500_000, ARRAY_LIST_5_000_000, LINKED_LIST_50_000, LINKED_LIST_500_000, LINKED_LIST_5_000_000})
    private String type;

    private List<Integer> list;
    private int size;

    @Setup
    public void setUp() {
        switch (type) {
            case ARRAY_LIST_50_000:
                list = new ArrayList<>(data_50_000);
                size = 50_000;
                break;
            case ARRAY_LIST_500_000:
                list = new ArrayList<>(data_500_000);
                size = 500_000;
                break;
            case ARRAY_LIST_5_000_000:
                list = new ArrayList<>(data_5_000_000);
                size = 5_000_000;
                break;
            case LINKED_LIST_50_000:
                list = new LinkedList<>(data_50_000);
                size = 50_000;
                break;
            case LINKED_LIST_500_000:
                list = new LinkedList<>(data_500_000);
                size = 500_000;
                break;
            case LINKED_LIST_5_000_000:
                list = new LinkedList<>(data_5_000_000);
                size = 5_000_000;
                break;
            default:
                throw new IllegalArgumentException("Illegal argument exception:" + type);
        }
    }

    @Benchmark
    public void add() {
        int index = random.nextInt(size);
        int element = random.nextInt();
        list.add(index, element);
    }

    @Benchmark
    public void remove() {
        int n = list.size();
        if (n > 0) {
            list.remove(random.nextInt(n));
        } else {
            switch (type) {
                case ARRAY_LIST_50_000:
                    list = new ArrayList<>(data_50_000);
                    break;
                case ARRAY_LIST_500_000:
                    list = new ArrayList<>(data_500_000);
                    break;
                case ARRAY_LIST_5_000_000:
                    list = new ArrayList<>(data_5_000_000);
                    break;
                case LINKED_LIST_50_000:
                    list = new LinkedList<>(data_50_000);
                    break;
                case LINKED_LIST_500_000:
                    list = new LinkedList<>(data_500_000);
                    break;
                default:
                    list = new LinkedList<>(data_5_000_000);
                    break;
            }
            list.remove(random.nextInt(list.size()));
        }
    }

    public static void main(String[] args) throws RunnerException {
        new Runner(new OptionsBuilder().include(Main.class.getSimpleName()).build()).run();
    }
}

测试结果：

Benchmark    (type)  Mode  Cnt  Score    Error  Units
Main.add          1  avgt    5  0.147 ±  0.083  ms/op
Main.add          2  avgt    5  0.159 ±  0.117  ms/op
Main.add          3  avgt    5  1.949 ±  0.102  ms/op
Main.add          4  avgt    5  0.274 ±  0.010  ms/op
Main.add          5  avgt    5  0.916 ±  0.507  ms/op
Main.add          6  avgt    5  4.199 ±  0.477  ms/op
Main.remove       1  avgt    5  0.001 ±  0.001  ms/op
Main.remove       2  avgt    5  0.010 ±  0.001  ms/op
Main.remove       3  avgt    5  1.844 ±  0.213  ms/op
Main.remove       4  avgt    5  0.010 ±  0.001  ms/op
Main.remove       5  avgt    5  0.107 ±  0.097  ms/op
Main.remove       6  avgt    5  3.934 ±  0.124  ms/o

其中type的1-6分别对应5w、50w、500w的ArrayList和LinkedList。

虽然这个实验有一定的局限性，但也是证明了ArrayList的插入以及删除性能并不会比LinkedList差。实际上，通过源码（看上面分析）可以知道，ArrayList插入以及删除的主要耗时在于System.arraycopy，而LinkedList主要耗时在于this.node()，实际上两者需要的都是O(n)时间。

至于为什么ArrayList的插入和删除速度要比LinkedList快，笔者猜测，是System.arraycopy的速度快于LinkedList中的for循环遍历速度，因为LinkedList中找到插入/删除的位置是通过this.node()，而该方法是使用简单的for循环实现的（当然底层是首先判断是位于哪一边，靠近头部的话从头部开始遍历，靠近尾部的话从尾部开始遍历）。相对于System.arraycopy的原生C++方法实现，可能会慢于C++，因此造成了速度上的差异。

ArrayList和LinkedList底层实现原理

ArrayList和LinkedList底层实现原理

1.说一下 ArrayList 底层实现方式？

①ArrayList 通过数组实现，一旦我们实例化 ArrayList 无参数构造函数默认为数组初始化长度为 10②add 方法底层实现如果增加的元素个数超过了 10 个，那么 ArrayList 底层会新生成一个数组，长度为原数组的 1.5 倍+1，然后将原数组的内容复制到新数组当中，并且后续增加的内容都会放到新数组当中。当新数组无法容纳增加的元素时，重复该过程。是一旦数组超出长度，就开始扩容数组。扩容数组调用的方法 Arrays.copyOf(objArr, objArr.length + 1);

2.说一下 LinkedList 底层实现方式？

LinkedList 底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：

ArrayList实现原理（JDK1.8）

ArrayList实现原理（JDK1.8）

ArrayList实现原理（JDK1.8）

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

ArrayList 继承于AbstractList，实现了List接口，其实AbstractList 已经实现过List接口，这里重复实现使得接口功能更加清晰，JDK中很多类都是如此。

其中Cloneable接口是克隆标记接口，Serializable序列化标记接口，需要clone和序列化功能必须实现这两个接口，而RandomAccess，单纯是一个标志接口 ，该接口表示该类支持快速随机访问，且在循环遍历时for循环的方式会优于用迭代器。

1.成员变量

 	// 默认初始容量
   private static final int DEFAULT_CAPACITY = 10;

   // 空数组实例，初始容量为0或者传入集合为空集合（不是null）时使用
   private static final Object[] EMPTY_ELEMENTDATA = {};
   
	// 空数组示例，无参构造时使用
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
   
	// ArrayList内部数据容器
   transient Object[] elementData; // non-private to simplify nested class access
   
	// 实际元素数量
   private int size;

在ArrayList中，主要有五个成员变量。DEFAULT_CAPACITY表示初始容量大小，即在我们初始化ArrayList时不指定容量大小， 默认容量将会是10，Object[] elementData 则是ArrayList内部实际存储对象的容易，也就是我们常说的ArrayList是数组实现的。

在1.8中，空数组分为了两类情况，EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，在标记空数组的时候区分了不同的情况。

2.构造方法

ArrayList有三个构造方法，指定容量的ArrayList(int initialCapacity) ，无参构造ArrayList() 以及传入集合的ArrayList(Collection<? extends E> c)。

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

最简单的莫过于无参构造，直接赋值为空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。其实对于常说的默认容量10，是在第一次添加元素调用add()方法时处理的，并不是构造方法中。

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

对于传入容量的构造方法，当传入参数 > 0时，直接初始化对应容量的数组，参数类型为int，也即ArrayList的最大初始容量不能超过Integer.MAX_VALUE，事实上ArrayList的最大容量也只能是Integer.MAX_VALUE。而初始容量传入0，会赋值为空数组EMPTY_ELEMENTDATA。如果 < 0，这个显然的不允许了，直接IllegalArgumentException

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

集合构造时，没有进行null校验，也就是说如果传入null，直接就会NPE异常。集合构造的逻辑也很简单，当传入集合不为空时，调用Arrays.copyOf进行复制，并且容量 size为传入大小，而传入集合为空，则赋值为空数组EMPTY_ELEMENTDATA。

3.添加元素

ArrayList在添加元素时，都会进行容量确认，可能会涉及到扩容，数组复制，所以效率相对较低。同时在添加元素时，ArrayList并未对元素本身进行校验，所以是允许集合中存在null的情况。

3.1.尾部添加元素
    public boolean add(E e) {
        // 确定容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 设值
        elementData[size++] = e;
        return true;
    }

在add()方法中，最主要的是确定容量ensureCapacityInternal(int minCapacity)方法。

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

首先会调用calculateCapacity(Object[] elementData, int minCapacity) 计算容量然后再ensureExplicitCapacity(int minCapacity)

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

这里仅仅判断了是否是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA（== 地址比较），如果前面还有印象的话，这个只会在无参构造时，才会初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这时候会取DEFAULT_CAPACITY（10）与传入minCapacity的较大值，常说的默认容量大小10也就是在这里诞生的。

而其他的情况，都直接但会minCapacity，也即 size + 1，如果首次添加，那就是1。

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

modCount是一个操作计数器，add与remove都会 + 1。当我们需要在循环中删除ArrayList元素时，需要使用迭代器Iterator的remove()方法，此时直接使用List的删除有针对modCount的校验，会抛出 ConcurrentModificationException异常。

如果minCapacity大于数组容量，则调用grow(int minCapacity)进行扩容。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 新容量增长 0.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0) // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

扩容时，新的容量为原容量 + 原容量的一半，也就是0.5倍增长。如果增长后的新容量比计算出来的容量minCapacity小，则赋值为minCapacity，如果大于MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)，则进入hugeCapacity(int minCapacity)方法。

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

这里可以看到，当minCapacity < 0 时，会产生OutOfMemoryError，这是一个Error子类，这是需要避免的。什么时候minCapacity会小于0呢，当ArrayList大小为Integer.MAX_VALUE后，还需要扩容，则会发生错误。

这个方法，我们可以看出，当ArrayList需要的容量首次大于MAX_ARRAY_SIZE时，会设置为MAX_ARRAY_SIZE，然后再次扩容时会变成Integer.MAX_VALUE，如果还不够，那就会发生错误。

扩容的最后一步是调用Arrays.copyOf进行元素的复制，这个最终也是调用System.arraycopy进行操作的。同时size++，实际元素的数量也增加 1。

3.2.中间添加元素
    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++;
    }

在中间添加元素的逻辑和尾部添加元素基本一样。

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

添加元素前，首先要进行范围检查，添加的范围只能在[0，size]之间，index == size时，其实就是尾部插入。然后确认容量新的容量，这个方法尾部添加时已经讲过，接着数组复制，这步复制会跳过index位置的处理，最后再对index位置赋值，即完成了index位置的添加。

可以看到最后调用了size++，add(int index, E element)方法总是会添加元素，即使该index位置存在数据，只是会将原来的index位置数据往后挤动一位，并不会进行覆盖。

3.3.批量添加

ArrayList除了add()与add(int index, E element)，还有两个批量添加的方法。

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        // 确认容量
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        // 范围检查
        rangeCheckForAdd(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        // 确认容量
        ensureCapacityInternal(size + numNew);  // Increments modCount
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

有了前面单个元素的添加基础，批量添加就很好懂了，唯一的区别就是在数组复制时，是复制整个待添加的集合。对于index位置的批量添加，中间插入的话（numMoved > 0），第一次复制会腾出中间要添加集合长度的位置，第二次将添加的集合复制到index位置。

4.修改元素

对于ArrayList中元素的修改，如果是对象属性的修改，可以直接修改引用对象，但对于基本类型包装类或者String呢，并没有办法通过引用修改，亦或者我们要更换对象引用，这时候就需要调用set(int index, E element)。

    public E set(int index, E element) {
        // 范围检查
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

这个方法实现很容易，ArrayList的修改本质就是对数组的值进行更改。首先进行范围检查，防止数组越界，这个很好理解，ArrayList内部就是数组，然后对index位置的值进行替换即可。

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

elementData(int index)获取了原来的值，用于set返回值，elementData实现更加简单，就是数组取值。

5.移除元素

ArrayList中移除元素的方法有三个，按索引删除remove(int index)、按元素删除remove(Object o)以及批量删除removeAll(Collection<?> c)等。

5.1.索引删除
    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;
    }

由于移除元素，并不涉及内部数组大小变化，所以实现相对较简单。必须要的范围检查，这个已经丝毫不陌生了，然后判断是否是尾部删除，如果不是尾部删除，则进行System.arraycopy复制，复制的目的是将index后的元素向前挪动 1 位元素以覆盖要删除的index位置，然后size减 1。

在移除方法中，可以看到modCount进行增加。同时对移除后尾部的元素赋值为null了，让GC生效。

5.2.按元素删除
    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;
    }

按元素删除的时候，首先判断了元素是否为null，因为ArrayList中是可以添加null的，这里不同分支的逻辑是一样的，都是遍历集合比较是否和传入元素相同，只是比较一个是 == null 一个是 equals。如果相同则删除，然后return了，所以remove(Object o)方法只会删除集合第一个与传入对象相同的元素。

重点就是这个fastRemove了。

    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; // clear to let GC do its work
    }

看到这个方法第一感觉是什么？是不是似曾相识，没错，fastRemove和按指针删除基本上市一样的，只是少了范围校验和获取删除前的元素这两步。

5.3.批量删除
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

对于removeAll(Collection< ? > c)，校验非空后调用了batchRemove(Collection< ? > c, boolean complement)。

    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                // 找出不需要移除的元素，放在数组的前面
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r, elementData, w, size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

这个方法看着可能有一点点绕，但明白其原理后就很清晰了，首先遍历数组，找出在要移除数组中不包含的元素，从原数组头部开始放，这样的数有w个，即最终数组前w个元素都是在集合c中包含的，而剩下的位置的元素则不关心，最后就是讲w到size的元素赋值为null，以便GC工作。

6.循环删除

前面也提到了，ArrayList在循环删除时会报错，这个究竟是怎么回事呢？

如果我们想删除一个集合中全部的某一个元素，例如下面集合ss中的a元素。

        List<String> ss = new ArrayList<>();
        ss.add("a");
        ss.add("b");
        ss.add("a");
        ss.add("b");
        ss.add("c");

当我们需要删除一个时，我们可以调用remove方法删除，根据索引或者根据元素都用，但是多个时，我们不知道每一个元素的索引，而根据值也不知道有多少个a存在，所以我们需要遍历集合。

这时候就可能存在问题了。

        for (String s : ss) {
            if("a".equals(s)){
                ss.remove(s);
            }
        }

无论是fori的还是foreach的删除，都会抛出java.util.ConcurrentModificationException，这是因为Arraylist循环时每一次取值都会调用其内部类Itr.next()方法。

        public E next() {
            // 校验modCount
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

在该方法最开始的地方，有校验modCount的checkForComodification()方法，这个方法中比较了modCount和expectedModCount，不相等就会抛出ConcurrentModificationException异常。

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

那expectedModCount到底是什么，为什么和modCount不相等呢。

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

expectedModCount是Itr的成员变量，这个在进行循环时会初始化赋值为modCount，最开始的时候他们是相等的，经过前面的探究，我们已经知道在remove调用时modCount会自增，所以checkForComodification就会抛出异常。

而我们常使用的这个做法就是使用 Itr 的remove。

        Iterator<String> it = ss.iterator();
        while (it.hasNext()){
            if("a".equals(it.next())){
                it.remove();
            }
        }

这样删除时就没有任何问题了，这是因为 Itr 的remove中，对expectedModCount进行了重新赋值，使得每一次调用后值都相等。

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                // 调用ArrayList的删除
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                // expectedModCount重新赋值
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

7.其他方法

ArrayList中主要的就是构造方法、add和remove了，这几个方法看懂后，其他方法实现就比较清晰了。

比如get方法，其实就是根据索引获取了数组的元素。

    public E get(int index) {
        // 范围检查
        rangeCheck(index);
        // 从数组获取值，即 elementData[index]
        return elementData(index);
    }

例如size方法， 就是返回了size属性的值。

    public int size() {
        return size;
    }

而isEmpty方法，就是判断size是否为0.

    public boolean isEmpty() {
        return size == 0;
    }

在ArrayList中，有一个获取子集合的subList方法，这个方法返回的是一个内部类SubList，该类并没重新创建新的数组，依旧持有了ArrayList数组的元素的引用，所以当修改ArrayList元素的时候，SubList的元素也会跟着修改，这个在实际开发中一定要注意。

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }

我们今天的关于LinkedList实现原理和JDK1.8的分享就到这里，谢谢您的阅读，如果想了解更多关于0004--jcf (jdk1.7)-LinkedList 源码、ArrayList与LinkedList的区别以及JDK11中的底层实现、ArrayList和LinkedList底层实现原理、ArrayList实现原理（JDK1.8）的相关信息，可以在本站进行搜索。

本文标签：

上一篇ASP.NET Core 中的 ObjectPool 对象重用（二）（asp.net core 重定向）

下一篇第十一章 分页及 BaseController（分页实现原理）

相关文章