关于java:LinkedList-添加元素源码解析

jdk版本：1.8

LinkedList增加元素有两个办法：add(E e)和add(int index,E e)。

add(E e)

/**
*  Appends the specified element to the end of this list.
*  在列表最初增加指定元素
*/
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

add(E e)是间接在队尾增加元素。再看一下linkLast(E e)办法，源码如下。

    void linkLast(E e) {
        //找到链表的最初一个节点，赋值给l，
        final Node<E> l = last;
        //创立节点，这个节点的上一个节点就是下面last节点
        final Node<E> newNode = new Node<>(l, e, null);
       //将新的节点赋值给最初节点
        last = newNode;
        if (l == null)
            //如果没有最初节点，示意增加链表为空，赋值给首节点。
            first = newNode;
        else
            //有最初一个节点，将最初节点的next指针指向新建的节点
            l.next = newNode;
        size++;
        modCount++;
    }

1. LinkedList会记录链表的最初一个节点last，
2. 首先创立新的节点，新节点的pre就是队列的最初一个节点last，新节点的next为null，
3. 如果last为空示意这个链表为空，新节点就是首节点first。

4. 如果last不为空示意链表不为空，将last节点的next指针指向新节点。

   add(int index,E e)

   add(int index,E e)是依据元素插入到指定地位上，index示意链表的地位

   /**
     * Inserts the specified element at the specified position in this list.
     * 插入指定的元素到列表指定地位上
     */
    public void add(int index, E element) {
        //查看地位是否越界
        checkPositionIndex(index);
        //如果插入的下标等于链表的大小，间接就是增加到队尾，
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

5. 首先查看index是否超过链表大小，即index 是否会大于链表的size。
6. 如果index等于链表的大小，增加元素就是在链表队尾增加元素，和add(E e) 操作统一。

7. 如果不等会size大小就调用linkBefore办法，首先在该办法的第二个参数应用了node办法。node办法源码如下：

    Node<E> node(int index) {
       //size >>1 示意size右移，示意size的一半
      //如果index小于size一半，从首节点往后遍历
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
       //如果index大于size一半，从最初一个节点往前遍历
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

   node办法通过链表的地位找到链表的元素。这里用到了一个size的右移运算，size>>1示意size/2。首先判断index是在链表的前一半还是后一半，因为linkedList是双链表，能够往前和往后进行遍历。如果在前半部分就从首节点往后遍历，如果在后半局部就从最初一个节点往前遍历，这样最多遍历size的一半，防止遍历整个链表。
   找到index对应的元素后执行linkedBefore办法

    /**
     * Inserts element e before non-null Node succ.
    *   往succ节点后面插入元素
     */
    void linkBefore(E e, Node<E> succ) {
        //succ的前一个节点
        final Node<E> pred = succ.prev;
       //创立新节点，新节点的pre就是succ的pre节点，新节点的next就是succ节点
        final Node<E> newNode = new Node<>(pred, e, succ);
       //succ.pre指向新节点
        succ.prev = newNode;
        //如果succ前节点为空，示意succ就是首节点，新节点即为首节点
        if (pred == null)
            first = newNode;
        else
        //succ的上一节点的next指向新节点
            pred.next = newNode;
        size++;
        modCount++;
    }
   

8. 新建节点，节点pre就是succ的pre，节点的next就是succ。
9. 将succ.pre指向新节点。
10. succ的pre为null，succ即为首节点，将first赋值给首节点
11. succ的pre不为空，则把succ的上一节点的next指向新节点

总结

1. LinkedList，只有两种增加形式，一种是在列表最初增加(linkLast)，一种是在列表某个元素后面增加 (linkBefore)。
2. LinkLast，首先创立一个新节点，节点pre指向最初一个节点，最初一个节点的next指向新节点。

3. LinkBefore，首先依据index下标获取到元素的地位，新建新节点，新节点的pre就是元素的pre，新节点的next就是该元素。元素的pre的next指向新元素。

   为何Linked要用双链表而不是单链表

   LinkedList为何是双链表，链表次要毛病是查问速度很慢，增加或者删除都要找到要增加和删除的节点，而应用双链表，每次遍历循环前，都会判断一下索引是在链表的前半部分还是后半局部。如果是前半部分的话，从首部遍历到两头。如果是后半局部，从尾部遍历到两头。