LinkedList源码解析（基于JDK1.7）

分手后的思念是犯贱 2022-06-09 00:27 239阅读 0赞

## 一、LinkedList简介 ##

LinkedList的内部实现是双向链表，它继承了AbstractSequentialList，实现了List, Deque, Cloneable, Java.io.Serializable接口，因此LinkdeList本身支持就支持双端队列操作。LinkedList可以存储所有元素（包括 null）。LinkedList可以用作堆栈、队列或双端队列的实现。其内部链表的实现原理如下：  
![这里写图片描述][20160412125800880]  
可以看到这是一个双向链表的结构，而在JDK1.6中，其实现如下：  
![这里写图片描述][20160412130036633]  
可以看到在1.6中，存在环形结构，自然在代码中的也会有部分的改变。本次分析基于JDK1.7。  
LinkedList与ArrayList一样实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。  
LinkedList的实现不是同步的。如果在多线程环境下，应该使用 `Collections.synchronizedListxxx` 方法来“包装”LinkedList。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList的 iterator 和 listIterator 方法返回的迭代器是快速失败 的：在迭代器创建之后，如果从结构上对列表进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，这是通过LinkedList的modCount属性实现的。

## 二、源码分析 ##

### 1、定义 ###

LinkedList的定义如下：

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

*  Serializable：  
    序列化接口没有方法或字段，仅用于标识可序列化的语义
 *  Iterable：  
    实现这个接口允许对象成为 “foreach” 语句的目标。
 *  Cloneable：  
    此类实现了 Cloneable 接口，以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制。
 *  AbstractSequentialList  
    此类提供了 List 接口的骨干实现，从而最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作。对于随机访问数据（如数组），应该优先使用 AbstractList，而不是先使用此类。
 *  Deque  
    一个线性 collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

### 2、关键属性 ###

transient int size = 0;//链表元素个数  
        transient Node<E> first;//链表头结点 
        transient Node<E> last;//链表尾结点

和ArrayList类似，在类内部同样出现了transient关键字，这在ArrayList中已经解释过了，在这里不做过多的解释了。  
LinkedList内部通过Node来抽象一个节点，结点包括值和前向指针和后向指针。Node的定义是在LinkedList内部，作为静态内部类存在。

private static class Node<E> {  
            E item;//结点的值  
            Node<E> next;//结点的后向指针  
            Node<E> prev;//结点的前向指针   
            //构造函数中已完成Node成员的赋值 
            Node(Node<E> prev, E element, Node<E> next) {  
                this.item = element;//结点的值赋值为element  
                this.next = next;//后向指针赋值  
                this.prev = prev;//前向指针赋值  
            }  
    }

### 3、构造方法 ###

LinkedList构造方法有两个，一个是无参构造，一个是传入Collection对象的构造。源码如下：

// 什么都没做，是一个空实现
        public LinkedList() {
        }
    
        //传入一个集合类
        public LinkedList(Collection<? extends E> c) {
            this();//就是上面的空实现
            addAll(c);
        }
    
        public boolean addAll(Collection<? extends E> c) {
            return addAll(size, c);
        }
    
        public boolean addAll(int index, Collection<? extends E> c) {
            // 检查传入的索引值是否在合理范围内
            checkPositionIndex(index);
            // 将给定的Collection对象转为Object数组
            Object[] a = c.toArray();
            int numNew = a.length;
            // 数组为空的话，直接返回false
            if (numNew == 0)
                return false;
            // 数组不为空
            Node<E> pred, succ;
            if (index == size) {
                // 构造方法调用的时候，index = size = 0，进入这个条件。
                succ = null;
                pred = last;
            } else {
                // 链表非空时调用，node方法返回给定索引位置的节点对象
                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; // 将当前链表最后一个节点赋值给last
            } else {
                // 链表非空时，将断开的部分连接上
                pred.next = succ;
                succ.prev = pred;
            }
            // 记录当前节点个数
            size += numNew;
            modCount++;
            return true;
        }

这两个构造方法概括起来就是：无参构造为空实现。有参构造传入Collection对象，将对象转为数组，并按遍历顺序将数组首尾相连，全局变量first和last分别指向这个链表的第一个和最后一个。  
对于addAll方法，其返回值为boolean类型，当插入的集合元素为空时，才返回false，其他情况下返回true。

### 4、addFirst和addLast方法源码 ###

addFirst的源码实现如下：

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;  //此时链表中只有一个节点，first和last都指向该节点
        else  //原本链表不为空
            f.prev = newNode;//维护双向链表的关系  
        size++;  //节点个数加1
        modCount++;  
    }

addFirst顾名思义，是在现在的链表的头部加一个节点。既然是头结点，那么头结点的前继必然为null，所以这也是`Node<E> newNode = new Node<>(null, e, f)`;这样写的原因。之后将first指向了当前链表的头结点，若在插入元素之前头结点为null，则当前加入的元素就是第一个节点，也就是头结点，所以当前的状况就是：头结点=刚刚加入的节点=尾节点。若在插入元素之前头结点不为null，则证明之前的链表是有值的，那么我们只需要来维护双向链表，即原头节点的前置节点为新插入的节点，而尾节点则没有发生变化。这样一来，原来的头结点就变成了第二个节点了。达到了我们的目的。

addLast方法在实现上是个addFirst是一致的，源码如下：

//添加到尾结点，结点值为e  
        public void addLast(E e) {  
            linkLast(e);//添加到尾部  
        }  
         //尾部增加结点，结点的值为e  
        private void linkLast(E e) {  
            final Node<E> l = last;//l指向尾结点  
            //生成一个新结点，结点的值为e，其前向指针为l，后向指针为null  
            final Node<E> newNode = new Node<>(l, e, null);
            //last指向新生成的结点,l保存着老的尾结点信息  
            last = newNode;
            if (l == null)  
                //如果l为null,则表示整个链表目前是空的，则头结点也指向新结点
                first = newNode;  
            else  
                //l(老的尾结点)的后向指针指向最新的结点信息
                l.next = newNode;  
            size++;//元素个数+1  
            modCount++;//修改次数+1  
        }

### 5、add(E e)和add(int index, E element)方法 ###

add(E e)将指定元素添加到此列表的结尾。此方法等效于 addLast(E)。其源码如下：

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

方法add(int index, E element)表示在此列表中指定的位置插入指定的元素。随机写入，也就是使用下标，都要进行循环链表找到对应的链表节点找到节点之后，写入很快，（不用向数组那样还需要移动n个元素的下标）。需要注意的是，这里检索下标是从0开始，其源码如下：

//在指定位置插入元素，如果该位置已经有了元素，则改变这个元素的前/后索引
        public void add(int index, E element) {
            checkPositionIndex(index); // 同样检查索引是否越界
            if (index == size) //如果下标等于此列表的大小，则相当于往列表末尾添加元素（下标从0开始）
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
       //非空结点succ之前插入新结点，新结点的值为e  
       private void linkBefore(E e, Node<E> succ) {  
            // assert succ != null;//外界调用需保证succ不为null,否则程序会抛出空指针异常  
            final Node<E> pred = succ.prev;//pred指向succ的前向结点  
            //生成一个新结点，结点的值为e,其前向指针指向pred，后向指针指向succ  
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;//succ的前向指针指向newNode  
            if (pred == null)  
                //如果pred为null，则表示succ为头结点，此时头结点指向最新生成的结点newNode  
                first = newNode;
            else  
                //pred的后向指针指向新生成的结点，此时已经完成了结点的插入操作
                pred.next = newNode;  
            size++;//元素个数+1  
            modCount++;//修改次数+1  
        }

### 6、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;
        }

很简单，不多说。

### 7、get(int index)方法 ###

public E get(int index) {  
        // 校验给定的索引值是否在合理范围内  
        checkElementIndex(index);  
        return node(index).item;  
    }  
    
    Node<E> node(int index) {
            // 这个是断言的句子，在开发的时候应该打开，编写完该工具类，测试能上线之后，就注释掉该语句了。
            // assert isElementIndex(index);
            // 下面的查找还优化了一点，不是在任何情况下都从头开始查找
            // 有点类似部分二分查找法，先二分，然后判定是从头开始还是从尾巴开始
            if (index < (size >> 1)) {
                Node<E> x = first;
                // 从头开始遍历，当i = index的时候，那么也就找到了 下标对应的链表节点
                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;
            }
        }

这样就可以保证，不管链表长度有多大，搜索的时候最多只搜索链表长度的一半就可以找到，大大提升了效率。

### 8、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;//需确保f为头结点,且链表不为Null  
            final E element = f.item;//获得结点的值  
            final Node<E> next = f.next;//next指向f的后向结点  
            f.item = null;//释放数据结点  
            f.next = null;//释放f的后向指针  
            first = next;//first指向f的后向结点  
            if (next == null)  
                //如果next为null，则表示f为last结点，此时链表即为空链表 
                last = null; 
            else  
                //修改next的前向指针，因为first结点的前向指针为null 
                next.prev = null; 
            size--;//元素个数-1  
            modCount++;//修改次数+1  
            return element;  
        }  
        //移除尾结点  
        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;//需确保l为尾结点，且链表不为null  
            final E element = l.item;//获得结点的值  
            final Node<E> prev = l.prev;//prev执行l的前向结点  
            l.item = null;//释放l结点的值  
            l.prev = null; //释放l结点的前向指针  
            last = prev;//last结点指向l的前向结点  
            if (prev == null) 
                //如果prev为null，则表示l为first结点,此时链表即为空链表  
                first = null; 
            else  
                //修改prev的后向指针，因为last结点的后向指针为null 
                prev.next = null; 
            size--;//元素个数-1  
            modCount++;//修改次数+1  
            return element;  
        }

比较简单，不多说。

### 9、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 {
                //从头开始遍历链表，直到下一个元素为null则表示链表到末尾了
                for (Node<E> x = first; x != null; x = x.next) {
                    //找到与指定元素匹配的链表节点
                    if (o.equals(x.item)) {
                        unlink(x); //处理链表的链接：因为删除了一个节点，这个节点的前后节点需要链接起来
                        return true;
                    }
                }
            }
            return false;
        }

其中的关键操作unlink(x)的代码如下：

//断开当前元素的链接，把指定元素从链表中去掉，并处理断开之后的链接操作
        E unlink(Node<E> x) {
            // assert x != null; x绝对不等于null，记得这里是链表节点，并不是元素值，所以永远都不为null（需要在外部判断）；
            final E element = x.item; //获得元素值
            final Node<E> next = x.next; //下一个元素
            final Node<E> prev = x.prev; //上一个元素
            //结合下面的图分析跟容易理解
            if (prev == null) { //上一个节点为null，一般出现在，当前节点就是first
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
            if (next == null) { //下一个节点为null,一般是：当前节点就是最后一个节点last
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
            x.item = null; // 手动置为null，方便GC
            size--;
            modCount++;
            return element;
        }

![这里写图片描述][20170823104612269]

其实核心操作就两个步骤：

*  操作前一个节点跳过当前节点直接指向后一个节点，通过 `prev.next = next;`实现；同时断开当前节点指向前一个节点的连接，通过`x.prev = null;`实现。
 *  因为需要维护双向链表，所以相应的还有一个逆向操作，通过`next.prev = prev;` 和 `x.next = null;`实现。

可以看到删除指定元素，也是需要从头遍历匹配的。  
ArrayList和LinkedList的本方法都是通过循环遍历匹配首个出现的值；区别在于：  
ArrayList 删除元素需要操作删除元素后面所有的元素的下标；  
LinkedList直接改变受影响的 前后（首尾）的prev/next指向，就完成了 删除，相对来说，受影响的元素最多也只有（first/last变量、被删除元素的前/后元素），相对来说比ArrayList删除性能高。

### 10、remove(int index)方法 ###

该方法用于移除此列表中指定位置处的元素。

// 按指定索引删除元素
        // 链表按道理来说没有下标的，但是总有元素个数吧，而且还是有序的，从头遍历到尾巴，就相当于是下标了
        public E remove(int index) {
            //检查下标是否越界
            checkElementIndex(index);
            //这里调用了核心函数，断开此元素在链接，但是要先根据下标找到对应的链表节点
            return unlink(node(index));
        }
        private void checkElementIndex(int index) {
            if (!isElementIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        /**
         * Tells if the argument is the index of an existing element.
         */
        private boolean isElementIndex(int index) {
            //这里检查下标越界 比较完美一点，ArrayList里面都不检查是否为负数呢，不知道是为什么
            return index >= 0 && index < size;
        }

相同的含义的移除方法，相对于ArrayList来说，LinkedList的随机访问弱于 ArrayList（因为ArrayList是通过下标直接定位的）。

## 三、LinkedList关键源码整理 ##

//LinedList继承了AbstractSequentialList，支持泛型
    public class LinkedList<E>  
        extends AbstractSequentialList<E>  
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
    {  
        transient int size = 0;//链表元素个数  
        transient Node<E> first;//链表头结点 
        transient Node<E> last;//链表尾结点  
    
        //生成一个空的链表  
        public LinkedList() {  
        }  
    
        //按c里面的元素生成一个LinkedList  
        public LinkedList(Collection<? extends E> c) {  
            this();//调用空的构造函数  
            addAll(c);//将c里面的元素添加到空链表尾部  
        }  
        //首部增加结点，结点的值为e  
        private void linkFirst(E e) {  
            final Node<E> f = first;//f指向头结点  
            //生成一个新结点，结点的值为e,其前向指针为null，后向指针为f  
            final Node<E> newNode = new Node<>(null, e, f);
            //first指向新生成的结点，f保存着老的头结点信息  
            first = newNode;
            if (f == null)  
                //如果f为null，则表示整个链表目前是空的，则尾结点也指向新结点
                last = newNode;  
            else  
                //f(老的头结点)的前向指针指向最新的结点信息  
                f.prev = newNode;
            size++;//元素个数+1.  
            modCount++;//修改次数+1  
        }  
        //尾部增加结点，结点的值为e  
        void linkLast(E e) {  
            final Node<E> l = last;//l指向尾结点  
            //生成一个新结点，结点的值为e，其前向指针为l，后向指针为null  
            final Node<E> newNode = new Node<>(l, e, null);
            //last指向新生成的结点,l保存着老的尾结点信息  
            last = newNode;
            if (l == null)  
                //如果l为null,则表示整个链表目前是空的，则头结点也指向新结点
                first = newNode;  
            else  
                //l(老的尾结点)的后向指针指向最新的结点信息
                l.next = newNode;  
            size++;//元素个数+1  
            modCount++;//修改次数+1  
        }  
        //非空结点succ之前插入新结点，新结点的值为e  
        void linkBefore(E e, Node<E> succ) {  
            // assert succ != null;//外界调用需保证succ不为null,否则程序会抛出空指针异常  
            final Node<E> pred = succ.prev;//pred指向succ的前向结点  
            //生成一个新结点，结点的值为e,其前向指针指向pred，后向指针指向succ  
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;//succ的前向指针指向newNode  
            if (pred == null)  
                //如果pred为null，则表示succ为头结点，此时头结点指向最新生成的结点newNode  
                first = newNode;
            else  
                //pred的后向指针指向新生成的结点，此时已经完成了结点的插入操作
                pred.next = newNode;  
            size++;//元素个数+1  
            modCount++;//修改次数+1  
        }  
    
        //删除头结点，并返回该结点的值  
        private E unlinkFirst(Node<E> f) {  
            // assert f == first && f != null;//需确保f为头结点,且链表不为Null  
            final E element = f.item;//获得结点的值  
            final Node<E> next = f.next;//next指向f的后向结点  
            f.item = null;//释放数据结点  
            f.next = null;//释放f的后向指针  
            first = next;//first指向f的后向结点  
            if (next == null)  
                //如果next为null，则表示f为last结点，此时链表即为空链表 
                last = null; 
            else  
                //修改next的前向指针，因为first结点的前向指针为null 
                next.prev = null; 
            size--;//元素个数-1  
            modCount++;//修改次数+1  
            return element;  
        }  
        //删除尾结点，并返回尾结点的内容  
        private E unlinkLast(Node<E> l) {  
            // assert l == last && l != null;//需确保l为尾结点，且链表不为null  
            final E element = l.item;//获得结点的值  
            final Node<E> prev = l.prev;//prev执行l的前向结点  
            l.item = null;//释放l结点的值  
            l.prev = null; //释放l结点的前向指针  
            last = prev;//last结点指向l的前向结点  
            if (prev == null) 
                //如果prev为null，则表示l为first结点,此时链表即为空链表  
                first = null; 
            else  
                //修改prev的后向指针，因为last结点的后向指针为null 
                prev.next = null; 
            size--;//元素个数-1  
            modCount++;//修改次数+1  
            return element;  
        }  
        //删除结点x  
        E unlink(Node<E> x) {  
            // assert x != null;//需确保x不为null，否则后续操作会抛出空指针异常  
            final E element = x.item;//保存x结点的值  
            final Node<E> next = x.next;//next指向x的后向结点  
            final Node<E> prev = x.prev;//prev指向x的前向结点  
    
            if (prev == null) {  
                //如果prev为空，则x结点为first结点，此时first结点指向next结点（x的后向结点）  
                first = next;
            } else {  
                prev.next = next;//x的前向结点的后向指针指向x的后向结点  
                x.prev = null;//释放x的前向指针  
            }  
    
            if (next == null) {  
                //如果next结点为空，则x结点为尾部结点，此时last结点指向prev结点(x的前向结点)  
                last = prev;
            } else {  
                next.prev = prev;//x的后向结点的前向指针指向x的前向结点  
                x.next = null;//释放x的后向指针  
            }  
    
            x.item = null;//释放x的值节点,此时x节点可以完全被GC回收  
            size--;//元素个数-1  
            modCount++;//修改次数+1  
            return element;  
        }  
    
        //获得头结点的值  
        public E getFirst() {  
            final Node<E> f = first;//f指向first结点  
            if (f == null)//此时链表为空  
                throw new NoSuchElementException();  
            return f.item;//返回first结点的值  
        }  
    
        //获得尾结点的值  
        public E getLast() {  
            final Node<E> l = last;//l指向last结点  
            if (l == null)//此时链表为空  
                throw new NoSuchElementException();  
            return l.item;//返回last结点的值  
        }  
    
        //移除头结点  
        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);//摘除尾结点  
        }  
    
        //添加到头结点，结点的值为e  
        public void addFirst(E e) {  
            linkFirst(e);//添加到头部  
        }  
        //添加到尾结点，结点值为e  
        public void addLast(E e) {  
            linkLast(e);//添加到尾部  
        }  
    
        //判断元素（值为o）是o否在链表中  
        public boolean contains(Object o) {  
            return indexOf(o) != -1;//定位元素  
        }  
        //返回元素个数  
        public int size() {  
            return size;  
        }  
    
        //添加元素，元素值为e  
        public boolean add(E e) {  
            linkLast(e);//添加到链表尾部  
            return true;
        }  
        //移除值为o的元素，o可以为null,找到一个删除即返回  
        public boolean remove(Object o) {  
            if (o == null) {
       //元素为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;  
        }  
        //将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);//判断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;//指向为结点  
            } else {  
                succ = node(index);//succ指向第index个结点  
                pred = succ.prev;//pred指向succ的前向结点  
            }  
            //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)  
                    first = newNode;//如果pred为null，则succ为当前头结点，  
                else  
                    pred.next = newNode;//pred的后向指针指向新结点  
                pred = newNode;//pred移动到新结点  
            }  
    
            if (succ == null) {  
                last = pred;//succ为null，这表示index为尾结点之后  
            } else {  
                //pred表示所有元素添加之后的最后结点，此时pred的后向指针指向之前的记录的结点  
                pred.next = succ;
                succ.prev = pred;//之前记录的结点指向添加元素之后的最后结点  
            }  
    
            size += numNew;//元素个数+num  
            modCount++;//修改次数+1  
            return true;  
        }  
        //清除链表里面的所有元素  
        public void clear() {  
            for (Node<E> x = first; x != null; ) {  
                Node<E> next = x.next;  
                x.item = null;//释放值结点，便于GC回收  
                x.next = null;//释放前向指针  
                x.prev = null;//释放后向指针  
                x = next;//后向遍历  
            }  
            first = last = null;//释放头尾结点  
            size = 0;  
            modCount++;  
        }  
        //获得第index个结点的值  
        public E get(int index) {  
            checkElementIndex(index);  
            return node(index).item;//点位第index结点，返回值信息  
        }  
        //设置第index元素的值  
        public E set(int index, E element) {  
            checkElementIndex(index);  
            Node<E> x = node(index);//定位第index个结点  
            E oldVal = x.item;  
            x.item = element;  
            return oldVal;  
        }  
    
        //第index个结点之前添加结点  
        public void add(int index, E element) {  
            checkPositionIndex(index);  
    
            if (index == size)  
                linkLast(element);  
            else  
                linkBefore(element, node(index));  
        }  
        //删除第index个结点  
        public E remove(int index) {  
            checkElementIndex(index);  
            return unlink(node(index));  
        }  
        //判断index是否是链表中的元素的下标  
        private boolean isElementIndex(int index) {  
            return index >= 0 && index < size;  
        }  
        //判断index是否是链表中的元素的下标  
        private boolean isPositionIndex(int index) {  
            return index >= 0 && index <= size;  
        }  
    
        private String outOfBoundsMsg(int index) {  
            return "Index: "+index+", Size: "+size;  
        }  
    
        private void checkElementIndex(int index) {  
            if (!isElementIndex(index))  
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
        }  
    
        private void checkPositionIndex(int index) {  
            if (!isPositionIndex(index))  
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
        }  
    
        //定位链表中的第index个结点  
        Node<E> node(int index) {  
            // assert isElementIndex(index);//确保是合法的下标,即0<=index<=size  
            //index小于size的一半时，从头向后找  
            if (index < (size >> 1)) {  
                Node<E> x = first;  
                for (int i = 0; i < index; i++)  
                    x = x.next;  
                return x;  
            } else {
       //index大于size的一半时，从尾向前找  
                Node<E> x = last;  
                for (int i = size - 1; i > index; i--)  
                    x = x.prev;  
                return x;  
            }  
        }  
    
        //定位元素，首次出现的元素的值为o的结点序号  
        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;  
        }  
    
        //定位元素，最后一次出现的元素值为o的元素序号  
        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;  
        }  
    
        //实现队列操作，返回第一个元素的值  
        public E peek() {  
            final Node<E> f = first;  
            return (f == null) ? null : f.item;  
        }  
    
        //实现队列操作，返回第一个结点  
        public E element() {  
            return getFirst();  
        }  
        //实现队列操作，弹出第一个结点  
        public E poll() {  
            final Node<E> f = first;  
            return (f == null) ? null : unlinkFirst(f);  
        }  
        //删除结点  
        public E remove() {  
            return removeFirst();  
        }  
        //添加结点  
        public boolean offer(E e) {  
            return add(e);  
        }  
        //添加头结点  
        public boolean offerFirst(E e) {  
            addFirst(e);  
            return true;  
        }  
        //添加尾结点  
        public boolean offerLast(E e) {  
            addLast(e);  
            return true;  
        }  
    
        //返回头结点的值  
        public E peekFirst() {  
            final Node<E> f = first;  
            return (f == null) ? null : f.item;  
         }  
    
        //返回尾结点的值  
        public E peekLast() {  
            final Node<E> l = last;  
            return (l == null) ? null : l.item;  
        }  
    
        //弹出第一个结点  
        public E pollFirst() {  
            final Node<E> f = first;  
            return (f == null) ? null : unlinkFirst(f);  
        }  
    
        //弹出最后一个结点  
        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();  
        }  
    
        //删除值为o的结点  
        public boolean removeFirstOccurrence(Object o) {  
            return remove(o);  
        }  
    
        //删除值为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;  
        }  
    
        //返回双向迭代器  
        public ListIterator<E> listIterator(int index) {  
            checkPositionIndex(index);  
            return new ListItr(index);  
        }  
        //私有内部类，实现双向迭代器  
        private class ListItr implements ListIterator<E> {  
            private Node<E> lastReturned = null;//记录当前结点信息  
            private Node<E> next;//当前结点的后向结点  
            private int nextIndex;//当前结点的序号  
            private int expectedModCount = modCount;//修改次数  
            //初始化  
            ListItr(int index) {  
                next = (index == size) ? null : node(index);
                nextIndex = index;  
            }  
            //是否有结点  
            public boolean hasNext() {  
                return nextIndex < size;  
            }  
            //返回下一个结点  
            public E next() {  
                checkForComodification();  
                if (!hasNext())  
                    throw new NoSuchElementException();  
    
                lastReturned = next;//记录当前结点  
                next = next.next;//向后移动  
                nextIndex++;//结点序号+1  
                return lastReturned.item;  
            }  
            //是否有前向结点  
            public boolean hasPrevious() {  
                return nextIndex > 0;  
            }  
            //返回前向结点  
            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++;  
            }  
            //判断迭代期间是否被修改  
            final void checkForComodification() {  
                if (modCount != expectedModCount)  
                    throw new ConcurrentModificationException();  
            }  
        }  
    
        //返回前向迭代器  
        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();  
            }  
        }  
    
        @SuppressWarnings("unchecked")  
        private LinkedList<E> superClone() {  
            try {  
                return (LinkedList<E>) super.clone();  
            } catch (CloneNotSupportedException e) {  
                throw new InternalError();  
            }  
        }  
    
        //拷贝操作，执行浅拷贝，只复制引用，而没有复制引用指向的内存
        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;  
        }  
    
        //转换为数组  
        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;  
        }  
    
        //转换为数组  
        @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;  
        }  
    
        private static final long serialVersionUID = 876323262645176354L;  
    
        //序列化  
        private void writeObject(java.io.ObjectOutputStream s)  
            throws java.io.IOException {  
            // Write out any hidden serialization magic  
            s.defaultWriteObject();  
    
            // Write out size  
            s.writeInt(size);  
    
            // Write out all elements in the proper order.  
            for (Node<E> x = first; x != null; x = x.next)  
                s.writeObject(x.item);  
        }  
    
        //反序列化  
        @SuppressWarnings("unchecked")  
        private void readObject(java.io.ObjectInputStream s)  
            throws java.io.IOException, ClassNotFoundException {  
            // Read in any hidden serialization magic  
            s.defaultReadObject();  
    
            // Read in size  
            int size = s.readInt();  
    
            // Read in all elements in the proper order.  
            for (int i = 0; i < size; i++)  
                linkLast((E)s.readObject());  
        }  
    }

[20160412125800880]: /images/20220609/218ca9f2df404e2da9778db078332b47.png
[20160412130036633]: /images/20220609/691746580f0b418e9fefa59e03db6004.png
[20170823104612269]: /images/20220609/e089f919148c4cfdbcecbd951d3e1933.png