Java集合之LinkedList源码解析

Love The Way You Lie 2021-09-18 14:56 447阅读 0赞

[原文地址][Link 1]

## LinkedList ##

*  在Java.util包下
 *  继承自AbstractSequentialList
 *  实现 List 接口，能对它进行队列操作。
 *  实现 Deque 接口，即能将LinkedList当作双端队列使用。
 *  实现了Cloneable接口，即覆盖了函数clone()，能克隆。
 *  实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
 *  允许包含null值
 *  迭代器可以快速报错
 *  非线程安全的，如果在多线程中使用（修改），需要在外部作同步处理。

LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。内部有三个变量，size表示链表中元素的个数， first指向链表头部，last指向链表尾部。 结构图如下图所示

![LinkedList.png][]

下面是LinkedList中Node节点的定义，Node类是LinkedList的静态内部类。

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

## 构造方法（Construction method） ##

LinkedList提供了两种种方式的构造器，构造一个空列表、以及构造一个包含指定collection的元素的列表，  
这些元素按照该collection的迭代器返回的顺序排列的。

public LinkedList() {
    }
    
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);   // 调用addAll方法，构建一个包含指定集合c的列表
    }

## 添加元素 ##

因为LinkedList即实现了List接口，又实现了Deque接口，所以LinkedList既可以添加将元素添加到尾部，也可以将元素添加到指定索引位置，还可以添加添加整个集合；另外既可以在头部添加，又可以在尾部添加。

//添加元素作为第一个元素
    public void addFirst(E e) {
        linkFirst(e);
    }
    //店家元素作为最后一个元素
    public void addLast(E e) {
        linkLast(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;     //如果之前首节点为空(size==0)，那么尾节点就是首节点
        else
            f.prev = newNode;   //如果之前首节点不为空，之前的首节点的前一个节点为当前首节点
        size++;                 //长度+1
        modCount++;             //修改次数+1
    }
    //使用对应参数作为尾节点
    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;    //如果之前尾节点为空(size==0)，首节点即尾节点
        else
            l.next = newNode;   //如果之前尾节点不为空，之前的尾节点的后一个就是当前的尾节点
        size++;
        modCount++;
    }
    
    //在非空节点succ之前插入元素E。
    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;//如果前一个节点为null，新的节点就是首节点
        else
            pred.next = newNode;//如果存在前节点，那么前节点的向后指向新节点
        size++;
        modCount++;
    }
    
    //添加指定集合的元素到列表，默认从最后开始添加
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);//size表示最后一个位置
    }
    
    /*
    从指定位置（而不是下标！下标即索引从0开始，位置可以看做从1开始，其实也是0）后面添加指定集合的元素到列表中，只要有至少一次添加就会返回true
    index换成position应该会更好理解，所以也就是从索引为index(position)的元素的前面索引为index-1的后面添加！
    当然位置可以为0啊，为0的时候就是从位置0(虽然它不存在)后面开始添加嘛，所以理所当然就是添加到第一个位置（位置1的前面）的前面
    
    比如列表：0 1 2 3，如果此处index=4(实际索引为3)，就是在元素3后面添加；如果index=3(实际索引为2)，就在元素2后面添加。
    */
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);  //检查索引是否正确（0<=index<=size）
        Object[] a = c.toArray();   //得到元素数组
        int numNew = a.length;      //得到元素个数
        if (numNew == 0)            //若没有元素要添加，直接返回false
            return false;
        Node<E> pred, succ;
        if (index == size) {    //如果是在末尾开始添加，当前节点后一个节点初始化为null，前一个节点为尾节点
            succ = null;        //这里可以看做node(index)，不过index=size了（index最大只能是size-1），所以这里的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;    //若当前节点为null，则新加的节点为首节点
            else
                pred.next = newNode;//如果存在前节点，前节点会向后指向新加的节点
            pred = newNode;         //新加的节点成为前一个节点
        }
        if (succ == null) {
            //pred.next = null  //加上这句也可以更好的理解
            last = pred;        //如果是从最后开始添加的，则最后添加的节点成为尾节点
        } else {
            pred.next = succ;   //如果不是从最后开始添加的，则最后添加的节点向后指向之前得到的后续第一个节点
            succ.prev = pred;   //当前，后续的第一个节点也应改为向前指向最后一个添加的节点
        }
        size += numNew;
        modCount++;
        return true;
    }
    
    //将指定的元素(E element)插入到列表的指定位置(index)
    public void add(int index, E element) {
        checkPositionIndex(index); //index >= 0 && index <= size
    
        if (index == size) 
            linkLast(element); //尾插入
        else
            linkBefore(element, node(index));  //中间插入
    }

**linkBefore的添加步骤：**

1.  创建newNode节点，将newNode的后继指针指向succ，前驱指针指向pred
2.  将succ的前驱指针指向newNode
3.  根据pred是否为null，进行不同操作。

*  如果pred为null，说明该节点插入在头节点之前，要重置first头节点
 *  如果pred不为null，那么直接将pred的后继指针指向newNode即可

**addAll的添加步骤：**

1.  检查index索引范围
2.  得到集合数据
3.  得到插入位置的前驱和后继节点
4.  遍历数据，将数据插入到指定位置

## 删除元素 ##

同样的LinkedList也提供了很多方法来删除元素

// 删除首节点并返回删除前首节点的值，内部使用 (f == first && f != null)
    private E unlinkFirst(Node<E> f) {
        final E element = f.item;      // 获取首节点的值 
        final Node<E> next = f.next;   // 获取首节点的后一个节点
        f.item = null;
        f.next = null; // help GC
        first = next;                 // 更新首节点
        if (next == null)             //如果不存在下一个节点，则首尾都为null
            last = null;
        else
            next.prev = null;        //如果存在下一个节点，那它的前指针为null
        size--;
        modCount++;
        return element;
    }
    
    // 删除尾节点，并返回尾节点的元素 （assert l == last && l != null）
    private E unlinkLast(Node<E> l) {
        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;   //如果前一个节点不存在，则首尾都为null
        else
            prev.next = null;//如果前一个节点存在，先后指向null
        size--;
        modCount++;
        return element;
    }
    
    // 删除指定节点x并返回节点的值（x != null）
    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;//如果前一个节点不为空，那么他先后指向当前的下一个节点
            x.prev = null;  //help  GC
        }
        if (next == null) {
            last = prev;    //如果后一个节点为空(如当前节点为尾节点)，当前节点前一个成为新的尾节点
        } else {
            next.prev = prev;//如果后一个节点不为空，后一个节点向前指向当前的前一个节点
            x.next = null;  //help  GC
        }
        x.item = null;   //help  GC
        size--;
        modCount++;
        return element;
    }
    
    //删除第一个元素并返回删除的元素
    public E removeFirst() {
        final Node<E> f = first;//得到第一个节点
        if (f == null)          //如果为空，抛出异常
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    //删除最后一个元素并返回删除的值
    public E removeLast() {
        final Node<E> l = last;//得到最后一个节点
        if (l == null)          //如果为空，抛出异常
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

## 序列化方法 ##

private static final long serialVersionUID = 876323262645176354L;
    
    //序列化：将linkedList的“大小，所有的元素值”都写入到输出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        s.defaultWriteObject();
        s.writeInt(size);
    
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }
    
    //反序列化：先将LinkedList的“大小”读出，然后将“所有的元素值”读出
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();
        int size = s.readInt();
    
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());  //以尾插入的方式
    }

## 队列操作 ##

//提供普通队列和双向队列的功能，当然，也可以实现栈，FIFO，FILO
    //出队（从前端），获得第一个元素，不存在会返回null，不会删除元素（节点）
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
    //出队（从前端），不删除元素，若为null会抛出异常而不是返回null
    public E element() {
        return getFirst();
    }
    //出队（从前端），如果不存在会返回null，存在的话会返回值并移除这个元素（节点）
    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    //出队（从前端），如果不存在会抛出异常而不是返回null，存在的话会返回值并移除这个元素（节点）
    public E remove() {
        return removeFirst();
    }
    //入队（从后端），始终返回true
    public boolean offer(E e) {
        return add(e);
    }
    //入队（从前端），始终返回true
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
    //入队（从后端），始终返回true
    public boolean offerLast(E e) {
        addLast(e);//linkLast(e)
        return true;
    }
    //出队（从前端），获得第一个元素，不存在会返回null，不会删除元素（节点）
    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }
    //出队（从后端），获得最后一个元素，不存在会返回null，不会删除元素（节点）
    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }
    //出队（从前端），获得第一个元素，不存在会返回null，会删除元素（节点）
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    //出队（从后端），获得最后一个元素，不存在会返回null，会删除元素（节点）
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }
    //入栈，从前面添加
    public void push(E e) {
        addFirst(e);
    }
    //出栈，返回栈顶元素，从前面移除（会删除）
    public E pop() {
        return removeFirst();
    }

## 迭代器 ##

//返回迭代器
    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }
    //迭代器
    private class DescendingIterator implements Iterator<E> {
        private final ListItr itr = new ListItr(size());
        public boolean hasNext() {
            return itr.hasPrevious();
        }
        public E next() {
            return itr.previous();
        }
        public void remove() {
            itr.remove();
        }
    }
    
    public ListIterator<E> listIterator(int index) {
            checkPositionIndex(index);
            return new ListItr(index);
    }
    
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;//保存当前modCount，确保fail-fast机制
    
        ListItr(int index) {
            next = (index == size) ? null : node(index);//得到当前索引指向的next节点
            nextIndex = index;
        }
    
        public boolean hasNext() {   // 判断后面是否还有元素
            return nextIndex < size;
        }
        
        public E next() {     //获取下一个节点
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
    
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
    
        public boolean hasPrevious() {
            return nextIndex > 0;
        }
    
        //获取前一个节点，将next节点向前移
        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();
    
            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }
    
        public int nextIndex() {
            return nextIndex;
        }
    
        public int previousIndex() {
            return nextIndex - 1;
        }
    
        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();
    
            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++;
        }
    
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }
    
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

在ListIterator的构造器中，得到了当前位置的节点，就是变量next。next()方法返回当前节点的值并将next指向其后继节点，previous()方法返回当前节点的前一个节点的值并将next节点指向其前驱节点。

由于Node是一个双向节点，所以这用了一个节点就可以实现从前向后迭代和从后向前迭代。另外在ListIterator初始时，exceptedModCount保存了当前的modCount，如果在迭代期间，有操作改变了链表的底层结构，那么再操作迭代器的方法时将会抛出ConcurrentModificationException。

### fail-fast ###

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

**快速失败（fail—fast）**

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

**原理：**迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。

**安全失败（fail—safe）**

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

**原理：**由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。

缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

## 其他方法 ##

//获取第一个元素
    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;
    }
    
    //检查是否包含某个元素，返回bool
    public boolean contains(Object o) {
        return indexOf(o) != -1;//返回指定元素的索引位置，不存在就返回-1，然后比较返回bool值
    }
    //返回列表长度
    public int size() {
        return size;
    }
    
    //清空表
    public void clear() {     // help GC
        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++;
    }
    //获取指定索引的节点的值
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    //修改指定索引的值并返回之前的值
    public E set(int index, E element) {
        checkElementIndex(index);    // 检查下标是否合法
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
    
    //获取指定位置的节点
    Node<E> node(int index) {
        if (index < (size >> 1)) {//如果位置索引小于列表长度的一半(或一半减一)，从前面开始遍历；
            Node<E> x = first;//index==0时不会循环，直接返回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;
        }
    }
    
    //获取指定元素从first开始的索引位置，不存在就返回-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;
    }
    //获取指定元素从first开始最后出现的索引，不存在就返回-1
    //但实际查找是从last开始的
    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;
    }
    
    //返回此 LinkedList实例的浅拷贝
    public Object clone() {
        LinkedList<E> clone = superClone();
    
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;
    
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);
    
        return clone;
    }
    
    //返回一个包含LinkedList中所有元素值的数组
    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;
    }
    
    //如果给定的参数数组长度足够，则将ArrayList中所有元素按序存放于参数数组中，并返回
    //如果给定的参数数组长度小于LinkedList的长度，则返回一个新分配的、长度等于LinkedList长度的、包含LinkedList中所有元素的新数组
    @SuppressWarnings("unchecked")
    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;
    }

[Link 1]: https://gyl-coder.top/LinkedListAnalysis/
[LinkedList.png]: /images/20210726/bd48e8e00fda47eebfba5ec65bfaadef.png