详解Java 集合系列（三）—— LinkedList

/**

   * appends the specified element to the end of this list.

   *

   * <p>this method is equivalent to {@link #addlast}.

   *

   * @param e element to be appended to this list

   * @return {@code true} (as specified by {@link collection#add})

   */

  public boolean add(e e) {

   linklast(e);

   return true ;

  }

  /**

   * links e as last element.

   */

  void linklast(e e) {

   final node<e> l = last;        // 将当前最后一个元素寄存在 l

   final node<e> newnode = new node<>(l, e, null );  // new 一个新节点：pre的引用为l；存储元素为e；next的引用为null

   last = newnode;          // 将新节点引用覆盖成员变量 last

   if (l == null )         

    first = newnode;        // 若l为null，说明之前链表为空，此时新节点为首个元素

   else

    l.next = newnode;        // 否则，更新l的next引用

   size++;            // size+1

   modcount++;           // 非查询操作 modcount 都会 +1

  }

/**

   * inserts the specified element at the specified position in this list.

   * shifts the element currently at that position (if any) and any

   * subsequent elements to the right (adds one to their indices).

   *

   * @param index index at which the specified element is to be inserted

   * @param element element to be inserted

   * @throws indexoutofboundsexception {@inheritdoc}

   */

  public void add( int index, e element) {

   checkpositionindex(index); // 检查 index 是否大于 size

   if (index == size)

    linklast(element);  // 直接在链表末尾追加

   else

    linkbefore(element, node(index)); // 插入index 节点前面

  }

  // 检查 index 是否超出范围 超出则抛出 indexoutofboundsexception

  private void checkpositionindex( int index) {

   if (!ispositionindex(index))

    throw new indexoutofboundsexception(outofboundsmsg(index));

  }

  /**

   * tells if the argument is the index of a valid position for an

   * iterator or an add operation.

   */

  private boolean ispositionindex( int index) {

   return index >= 0 && index <= size;

  }

  /**

   * 根据 index 查找 node

   * 该方法利用了双向链表的特性，index 距离哪个链表头近就从哪边开始开始遍历

   * 时间复杂度为 o(n/2)；

   * 当 index 接近 size 的中间值时，效率最低

   * returns the (non-null) node at the specified element index.

   */

  node<e> node( int index) {

   // assert iselementindex(index);

   if (index < (size >> 1 )) {   // size 右移一位（除以2）

    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;

    return x;

   }

  }