LinkedList源码最全面的分析

   //构造一个空的集合，一般我们创建一个集合，创建一个类的时候就会直接使用new关键字创建一个对象
    public LinkedList() {
    }

 public boolean add(E e) {
     //默认添加到集合的末尾，这里具体看下第二步的操作
        linkLast(e);
        return true;
    }
//第二步操作
    void linkLast(E e) {
        //首先将最后一个节点的引用赋值给局部临时变量l
        final Node<E> l = last;
        //创建一个新节点newNode，我们看下第三步操作看下newNode的过程
        final Node<E> newNode = new Node<>(l, e, null);
        //将新节点newNode赋值给最后一个节点引用last
        last = newNode;
        //这里是理解的关键一步，所以这里就多说点，首先判断我们的l节点引用是否为null
        //此时你可能会有点疑惑，或许没有，有可能第一次使用add()方法时，此时集合有可能为空
        //所以此时l一定为null，所以newNode必然是第一个节点，此时赋值给第一个节点引用first即可
        //想必看到这，你就明白了吧
        if (l == null)
            first = newNode;
        else
        //走到这里说明集合里一定不为空，此时直接将新节点挂载到最后一个节点的后面就可以了
        //即l.next=newNode，想象一下链表就像自行车的链条一样，是不是有点形象呢
            l.next = newNode;
        //集合的成员变量size加一，此时整个方法算是分析完了，想必你可以理解具体的实现逻辑了吧
        size++;
        modCount++;
    }
//第三步操作，构造一个静态内部类
 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 int size() {
        //上面的add()方法，我们已经知道了表示集合元素个数的成员变量size
        //当我们需要知道集合的元素个数大小时，返回size即可，是不是很简单呢？
        return size;
    }

public E get(int index) {
    //首先，我们需要检查index是否合法，是不是有点类似我们应用开发时，先检查参数是否有效，学到了吧
        checkElementIndex(index);
    //然后当参数校验且满足校验规则后，就去获取元素了，是不是类似我们的数据库查询数据的操作，学到了吧
    //当然了，我们看下第四步具体的实现过程
        return node(index).item;
    }
//第二步操作
 private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            //如果参数不合法，直接抛出索引越界的异常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
//第三步操作
private boolean isElementIndex(int index) {
    // index必须大于等于0，并且小于集合元素个数size
        return index >= 0 && index < size;
    }
//第四步操作
    Node<E> node(int index) {
        //这里size>>1操作，即size大小减半操作
        //这里分为了从前向后找和从后向前找两步操作，主要是为了提高查找的效率
        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，是找链表的前一个结点
                //x是结点引用，里面即包含着元素项，也包含着前后指针引用
                x = x.prev;
            return x;
        }
    }

public E getFirst() {
    //将第一个节点引用first赋值给临时局部变量f
        final Node<E> f = first;
    //判断f是否为null，若为null，则抛出元素不存在的异常给上层调用者
        if (f == null)
            throw new NoSuchElementException();
    //返回节点引用对应的元素项，即f.item
        return f.item;
    }

 public E getLast() {
     //将最后一个节点引用赋值给局部临时变量l
     //这里的局部临时局部变量的写法是编程中很常用的一种写法
     //局部临时变量用完之后，就会被释放掉了
        final Node<E> l = last;
     //判断l是否为null，若为null，则抛出元素不存在的异常
        if (l == null)
            throw new NoSuchElementException();
     //若不为null，则返回节点引用l的元素项，即l.item
        return l.item;
    }

 public void addFirst(E e) {
     //添加到集合的第一个位置,因为LinkedList实现了队列 Deque<E>，所以这里算是队列方法
     //也是LinkedList的方法，这里就一起分析了
        linkFirst(e);
    }
//第二步操作
    private void linkFirst(E e) {
        //首先，我们先把第一个节点引用first赋值给临时局部连梁f
        final Node<E> f = first;
        //然后，我们构造一个新节点newNode，具体的构造实现在上面已经分析过了，这里你应该掌握了
        final Node<E> newNode = new Node<>(null, e, f);
        //这里将新节点newNode赋值给first，将其成为第一个新节点
        first = newNode;
        //首先我们还是要判断f是否等于null的
        //因为此时集合有可能为null，这里就需要将newNode赋值给最后一个节点引用last
        if (f == null)
            last = newNode;
        else
           //此时局部变量f节点引用的prev指针指向就是newNode，想象一下，链表结构就可以明白了
            f.prev = newNode;
        //集合元素的个数增加1
        size++;
        modCount++;
    }

public void addLast(E e) {
    //将元素e挂载到集合的末尾
        linkLast(e);
    }
//第二步操作
    void linkLast(E e) {
        //首先我们获取最后一个节点引用last，赋值给局部变量l
        final Node<E> l = last;
        //此时我们构造一个元素项为e的信节点newNode
        final Node<E> newNode = new Node<>(l, e, null);
        //将新节点newNode赋值给最后一个节点引用last
        last = newNode;
        //此时，我们依然需要判断最后一个节点是否为null的
        //因为l为null，说明集合还是空的，我们需要将新节点newNode赋值给第一个节点引用first
        if (l == null)
            first = newNode;
        else
        //此时，说明集合不为空，将新节点newNode挂载到最后一个节点的后面，即l.next=newNode
            l.next = newNode;
        //集合的元素个数增加1
        size++;
        modCount++;
    } 

public boolean contains(Object o) {
    //其实contains这个方法还是比较有意思的，接下来，我们看下它的具体实现过程吧
    //调用下面的方法，判断是否等于-1，若等于-1说明元素o不存在
        return indexOf(o) != -1;
    }
//第二步操作
public int indexOf(Object o) {
        int index = 0;
    //其实，这里我们是分两步进行操作的
    //第一步是判断元素o是否为null，若为null，则走下面的逻辑判断
        if (o == null) {
     //循环判断链表集合的每个元素是否等于元素o，若相等则直接返回对应的index值
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
     //若元素o，不为null，则走下面的逻辑判断
     //循环判断链表集合的每个元素是否等于元素o，若相等则直接返回对应的index值
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
    //若上述两种情况都找不到，说明元素o不再链表集合中存在，此时返回-1即可
        return -1;
    }

 public boolean remove(Object o) {
     //首先，我们需要知道是，集合里面是可以放null值的，所以在判断contains()方法
     //以及这里的remove()方法时，都需要分两种情况来进行判断的
     //若待移除的元素o为null，则走下面的逻辑处理
        if (o == null) {
      //从链表的头结点开始循环判断链表集合的每个元素是否等于元素o，若相等则释放这个结点
      //等下，看下unlink方法的具体实现了，此时的时间复杂度为O(n)
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
       //若待移除的元素o不为null，则走下面的逻辑处理
      //从链表的头结点开始循环判断链表集合的每个元素是否等于元素o，若相等则释放这个结点
      //等下，看下unlink方法的具体实现了，此时的时间复杂度为O(n)
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    //第二步操作
    E unlink(Node<E> x) {
        //此时获取结点x的元素值为element
        final E element = x.item;
        //由于下面的逻辑判断需要用到待删除节点x的下一个节点和x的前一个节点
        //所以这里暂时先获取并赋值给局部临时变量，下面就可以用了
        
        //获取结点x的下一个节点x.next赋值给临时局部变量next
        final Node<E> next = x.next;
        //获取结点x的前一个结点x.prev赋值给临时局部变量prev
        final Node<E> prev = x.prev;
         
        //首先判断prev是否等于null，若等于null，说明删除了第一个节点
        //此时需要将next节点赋值给第一个节点first引用
        if (prev == null) {
            first = next;
        } else {
            //若不为null，x的前一个节点的"prev"的下一个节点就是next，即prev.next=next赋值操作
            //这里是有点绕的，建议你这里画下图，理解一下，不太懂的可以在看下链表结构
            prev.next = next;
            //x.prev要置为null，然后jvm就会在某个时刻触发gc机制进行垃圾回收操作
            x.prev = null;
        }
        //判断next是否等于null，则last变为了x.prev即last=prev
        if (next == null) {
            last = prev;
        } else {
            //若next不等于null，将之前获取的prev赋值给next.prev
            next.prev = prev;
            //此时的x.next要置为null
            x.next = null;
        }
       //将x.item置为null，等待jvm在某个时刻进行垃圾回收，对jvm垃圾回收不了解的可以查找一下对应的文章看下
        x.item = null;
        //集合的元素个数减一
        size--;
        modCount++;
        //返回待删除的元素element
        return element;
    }

  public E peek() {
      //由于LinkedList集合实现了Deque队列，所以它这里也有队列里提供的方法
      //所以下面就一起把对应的方法分析了
      //首先获取第一个节点引用first赋值给局部变量f，编程里这种手法很常用，你学会了吗?
        final Node<E> f = first;
      //若first==null说明集合为空，返回null即可，若不为空，返回f的元素项，即f.item
        return (f == null) ? null : f.item;
    }

public E element() {
    //调用已经封装好的获取第一个元素的方法
        return getFirst();
 }

public E getFirst() {
        final Node<E> f = first;
    //可能你们比较好奇或者疑惑的点是这里，f==null的操作
    //因为这里是Deque队列提供的方法，有的队列是不允许添加null值的，所以自然而然不会出现null
    //这里也相当于做了一个前置校验，抛给上层调用者进行处理
        if (f == null)
            throw new NoSuchElementException();
    //直接返回第一个节点引用的元素项即可
        return f.item;
    }

 public E poll() {
     //获取第一个元素结点引用赋值给局部变量f
        final Node<E> f = first;
     //这里的poll操作是元素出队列，具体看下unlinkFirst()实现吧
        return (f == null) ? null : unlinkFirst(f);
    }
//第二步操作
private E unlinkFirst(Node<E> f) {
       //首先先把第一个节点f的元素值赋值给局部变量element，后面返回这个局部变量即可
        final E element = f.item;
    //获取第一个节点f的下一个节点，下面会用到
        final Node<E> next = f.next;
    //将出队列的元素置为null
        f.item = null;
    //将出队列的下一个节点置为null，因为上面已经获取了next，这里不需要了，一定要释放
    //这里当jvm在某个时刻就会触发垃圾回收机制进行垃圾对象的回收
        f.next = null; // help GC
    //将下一个节点next赋值给first成为队列的队首节点
        first = next;
    //若next等于null说明队列里没有元素了，last置为null即可
        if (next == null)
            last = null;
    //若next不为null，由于每个节点node都包含着prev,next这样的指针结构
    //所以这样需要将next.prev置为null，因为此时的next是队首元素，队首元素的prev一定为null
        else
            next.prev = null;
    //元素个数减一
        size--;
        modCount++;
    //返回最开始获取的队首元素element即可
        return element;
    }

public E peekFirst() {
    //获取队列队首的节点引用赋值给局部变量f
        final Node<E> f = first;
    //若f==null，则返回null，否则返回队首节点的元素项
        return (f == null) ? null : f.item;
     }

public E peekLast() {
    //这里已经多次提到了，编程中这样写的好处，先将最后一个节点last赋值给临时局部变量l
        final Node<E> l = last;
    //若节点l为null，则返回null，否则返回节点应用l的元素项
        return (l == null) ? null : l.item;
    }

 public E pollLast() {
     //获取最后一个节点引用赋值给临时局部变量l，然后对l进行处理
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }
//第二步操作
private E unlinkLast(Node<E> l) {
       //获取待出队列的元素element
        final E element = l.item;
    //由于是从队尾出队列的，所以需要获取队尾元素的前一个节点
    //即需要操作l.prev才能获取到
        final Node<E> prev = l.prev;
    //将出队列的元素item置为null,l.prev由于已经获取到了，此时也需要置为null，等待gc机制进行处理
        l.item = null;
        l.prev = null; // help GC
        last = prev;
    //这里要对prev进行判断，如果prev为null，说明队列里面已经没了元素
    //将队首元素引用置为null即可
        if (prev == null)
            first = null;
        else
     //prev已经是队尾元素了，此时prev.next置为null，因为队尾元素的next是为null
            prev.next = null;
    //队列的元素个数减一
        size--;
        modCount++;
        return element;
    }

public void push(E e) {
        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 = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

 public E pop() {
     //第一步操作
        return removeFirst();
    }
//第二步操作
public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
//第三步操作
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)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

 public boolean removeFirstOccurrence(Object o) {
     //这里可以看到，大师写的代码方法名是可以见名知意的，是不是就是我们学习借鉴的地方
     //remove()方法在上面分析过了，这里就不过多分析了
        return remove(o);
    }

 public boolean removeLastOccurrence(Object o) {
     //从方法名，我们就可以知道这个方法的含义，移除最后一次出现的元素o
     //那么移除也是要区分元素o是否为null的
     //若元素o为null，则走下面的逻辑实现
        if (o == null) {
     //这里的查找元素时间复杂度为O(n)
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    //若元素找到了，则直接走unlink()处理元素x
                    unlink(x);
                    return true;
                }
            }
        } else {
      //若元素o不为null，则走下面的逻辑实现
      //这里的查找元素的时间复杂度为O(n)
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                     //若元素找到了，则直接走unlink()处理元素x
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
//第二步操作
E unlink(Node<E> x) {
    //获取元素element
        final E element = x.item;
    // 获取待移除元素的下一个，即x.next赋值给临时局部变量next
        final Node<E> next = x.next;
    //获取待移除元素的前一个,即x.prev赋值给临时局部变量prev
        final Node<E> prev = x.prev;
    // 首先，我们要对prev进行判空操作
    //若prev为null，说明删除的是第一个节点
    //此时需要将x.next赋值给first成为第一个节点，即first=next
        if (prev == null) {
            first = next;
        } else {
            //若prev不为null，则prev.next直接指向next，即next赋值给prev.next
            prev.next = next;
            //这里的x.prev已经没有用了，需要释放掉，等待gc机制在某个时刻触发
            x.prev = null;
        }
   //若next==null，说明x是队尾元素，此时x.prev就变成队尾元素了，即prev要赋值给最后一个节点引用next
        if (next == null) {
            last = prev;
        } else {
            //此时，说明删除的是中间节点，即需要将x节点的前一个结点赋值给next.prev
            next.prev = prev;
            //x.next置为null是必要的，可以结合上面的图片内容自已分析一下撒
            x.next = null;
        }
    //此时将待删除节点x的元素项置为null，此时也是为了垃圾回收的
        x.item = null;
    //元素个数减1
        size--;
        modCount++;
        return element;
    }