数据结构系列（二） LinkedList

序言

• 数据结构对程序员至关重要，List出镜率也很高，本文将分析子类LinkedList的原理以及增删改查等方法。
• “LinkedList 是非线程安全的双向链表集合，具有快速删除增加等优点”，这句话大家经常看到，但具体LinkedList是怎么实现的。
• 分析流程 => 由上而下，依次分析。

LinkedList

• 继承关系

 java.lang.Object  
         ↳     java.util.AbstractCollection<E>  
           ↳     java.util.AbstractList<E>  
             ↳     java.util.LinkedList<E>  

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

• 变量
  LinkedList中只会存首尾两个对象的指针，便于程序进行查询。（从效率考虑，如果是靠前的对象，建议按正序进行查询；反之则逆序查询）

      /**
       * 集合第一个Node节点。
       */
      transient Node<E> first;

      /**
       * 集合最后一个Node节点。
       */
      transient Node<E> last;

• 构造函数

      /**
       * 构造函数1：创建一个空的LinkedList。
       */
      public LinkedList() {
      }

      /**
        *构造函数2：将另外一个集合作为源数据传入。
        */
      public LinkedList(Collection<? extends E> c) {
        this();
        //通过遍历的方式将集合c，加入到LinkedList中。
        addAll(c); //在（增）模块里面分析代码，此处先不做分析。
      }

• 内部类-Node：LinkedList实现双向链表结构的关键类。提前介绍，下面会多次用到。

       private static class Node<E> {//通过保存三个引用实现双向链表结构。
        E item;//外部传入的元素。
        Node<E> next;//后一个Node节点。
        Node<E> prev;//前一个Node节点。

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

添加元素（增）

• 重点介绍add、addAll方法，其他原理类似。

      /**
       * 添加元素方法1：按照默认顺序添加元素。
       */
      public boolean add(E e) {
          linkLast(e); // 从末尾添加元素。
          return true;
      }
      /**
       * 将元素添加首位。
       */
      private void linkFirst(E e) {
        //首先获取集合的第一个元素。
        final Node<E> f = first;
        //生成Node节点，首位元素，Node.prev肯定为null，
        //Node.item为e元素本身，Node.next为 前first元素。
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)//如果第一个元素为null，说明集合为空，则first和last都是newNode。
            last = newNode;
        else//否则将f.prev指向newNode,f成为第二个元素，实现双向链表结构
            f.prev = newNode;
        size++;
        modCount++;
      }
      /**
       * 添加方法3：将集合c的全部元素添加到LinkedList的末尾处。
       */
      public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
      }

      /**
       * 添加方法4：将集合c的全部元素添加到LinkedList的index 指定位置处。
       */
      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) { //相等则直接从末尾添加。
            succ = null;
            pred = last;
        } else {
            succ = node(index); // 获取该位置的元素。
            pred = succ.prev;
        }
        //遍历数组o，将每个元素依次添加到index前面。
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);//将新元素与succ.prev相连。
            if (pred == null)
            //如果pred为null，说明新元素要加的位置为首位。所以first设置为newNode.
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;//更新pred，让后面的元素依次添加在newNode后面。
        }

        if (succ == null) {
        //如果succ==null，说明添加位置在末尾。所以last设置为a的最后一个元素。
            last = pred;
        } else {//否则将pred与succ的联系建立起来。
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew; // 增加集合长度。
        modCount++; 
        return true; //操作成功
      }

• 其他添加元素方法

      /**
       * 将元素e 添加到最后。原理与LinkFirst相同，不再做分析。
       */
      void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
      }
      /**
       *添加元素方法2：将元素element添加到指定位置。
       */
      public void add(int index, E element) {
        checkPositionIndex(index);
        //判断index是否大于零，小于size，若不是则抛出IndexOutOfBoundsException异常。

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));//node(index)：通过遍历获取指定位置的元素。
      }
      /**
       * 将元素e 放到元素succ前面。
       */
      void linkBefore(E e, Node<E> succ) {
        
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
      }

      /**
       * 添加元素方法5：调用add（e），与add方法不同之处是具有返回值。
       * Java 1.5后添加的新方法。
       * @since 1.5
       */
      public boolean offer(E e) {
        return add(e);
      }

      /**
       * 添加元素方法6：调用addFirst（e）
       * @since 1.6
       */
      public boolean offerFirst(E e) {
        addFirst(e);
        return true;
      }

      /**
       * 添加元素方法7：调用addLast（e）
       * @since 1.6
       */
      public boolean offerLast(E e) {
        addLast(e);
        return true;
      }
      /**
       * 添加元素方法8：在首位添加元素e。
       * @since 1.6
      */
      public void push(E e) {
        addFirst(e);
      }

移除元素（删）

• 主要介绍 remove(Object o)、remove(int index)方法。

      /**
       * 删除方法3：移除指定元素。返回true或者false作为结果。
       */
      public boolean remove(Object o) {
      //正序遍历集合，找到指定元素，再去除o元素与其他元素的联系。
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);//去除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;
      }
        /**
        * 删除方法5：移除指定位置元素。（LinkedList没有脚标，无论有没有index，都需要遍历集合）
        */
      public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
      }

      /**
       * 删除方法：清除集合中的全部元素。
       */
      public void clear() {
            for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null; // 指针全部置为null，以便gc回收。
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;// 长度归零。
        modCount++;
      }

• 以下方法原理类似。可根据兴趣决定是否观看。

      /**
       * 删除方法1：移除首位元素。
       */
      public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);//原理参照LinkFirst。
      }

      /**
       * 删除方法2：移除末位元素。
       */
      public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
      }
     
      /**
       * 删除方法4：默认是删除首位元素。
       * @since 1.5
       */
      public E remove() {
        return removeFirst();
      }

      /**
       * 删除方法6：移除首位元素。
       * @since 1.6
       */
      public E pop() {
        return removeFirst();
      }     

      /**
       * 删除方法6：正常顺序查找并删除元素o.
       * @since 1.6
       */
      public boolean removeFirstOccurrence(Object o) {
        return remove(o);
      }

      /**
       * 删除方法7：逆序顺序查找并删除元素o.
       * @since 1.6
       */
      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 E set(int index, E element) {
    checkElementIndex(index); // 检验index是否合法。
    Node<E> x = node(index); // 找出指定位置元素。
    E oldVal = x.item; 
    x.item = element; // 改为新元素。
    return oldVal; // 返回老元素。
  }

查找元素（查）

  /**
   * 查找方法1：获取指定位置元素。
   */
  public E get(int index) {
      checkElementIndex(index);
      return node(index).item;
  }
  /**
   * 查找方法2：正序查找元素，返回元素位置。
   */
  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;
  }

  /**
   * 查找方法3：逆序查找元素。
   */
  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;
  }
  /**
   * 查找方法4：获取首位元素。和element的区别是不会抛出异常。
   * @since 1.5
   */
  public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
  }

  /**
   * 查找方法5：获取首位元素。
   * @since 1.5
   */
  public E element() {
    return getFirst();
  }

  /**
   * 查找方法6：获取并移除首位元素。
   * @since 1.5
   */
  public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
  }
  /**
   *  查找方法7：获取不并移除首位元素。peek相关 都不会报异常。
   *
   * @since 1.6
   */
  public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
   }

  /**
   * 查找方法8：获取不移除末位元素。peek相关 都不会报异常。
   * @since 1.6
   */
  public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
  }

  /**
   * 查找方法9：获取并移除首位元素。
   * @since 1.6
   */
  public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
  }

  /**
   *  查找方法10：获取并移除末位元素。
   * @since 1.6
   */
  public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
  }

使用建议

• LinkedList 整体是双向链表结构，所以适合元素需要频繁增删。
• LinkedList 没有脚标，查找元素都是通过遍历实现，建议巧用查找方法。例如靠后的元素查找就用lastIndexOf，靠前就是indexOf；删除元素对应的则有removeFirstOccurrence、removeLastOccurrence。
• 遍历元素时，强烈建议使用迭代器ListIterator，而不是普通for循环，然后get(index)；
• 删除元素时，如果是在遍历时删除，使用迭代器ListIterator；