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

26次阅读

共计 2347 个字符，预计需要花费 6 分钟才能阅读完成。

LinkedList 增加元素有两个办法：add(E e) 和 add(int index,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++;
    }

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

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

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

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

如果不等会 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++;
 }

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

LinkedList，只有两种增加形式，一种是在列表最初增加 (linkLast)，一种是在列表某个元素后面增加 (linkBefore)。
LinkLast，首先创立一个新节点，节点 pre 指向最初一个节点，最初一个节点的 next 指向新节点。
LinkBefore，首先依据 index 下标获取到元素的地位，新建新节点，新节点的 pre 就是元素的 pre，新节点的 next 就是该元素。元素的 pre 的 next 指向新元素。

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

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

正文完