數(shù)據(jù)結(jié)構(gòu)系列（二） LinkedList

序言

數(shù)據(jù)結(jié)構(gòu)對程序員至關(guān)重要采盒，List出鏡率也很高，本文將分析子類LinkedList的原理以及增刪改查等方法树姨。
“LinkedList 是非線程安全的雙向鏈表集合蹈集，具有快速刪除增加等優(yōu)點(diǎn)”，這句話大家經(jīng)诚睿看到驯击，但具體LinkedList是怎么實(shí)現(xiàn)的。
分析流程 => 由上而下耐亏，依次分析徊都。

LinkedList

繼承關(guān)系

 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中只會存首尾兩個對象的指針，便于程序進(jìn)行查詢广辰。（從效率考慮暇矫，如果是靠前的對象主之，建議按正序進(jìn)行查詢；反之則逆序查詢）

      /**
       * 集合第一個Node節(jié)點(diǎn)李根。
       */
      transient Node<E> first;

      /**
       * 集合最后一個Node節(jié)點(diǎn)槽奕。
       */
      transient Node<E> last;

構(gòu)造函數(shù)

      /**
       * 構(gòu)造函數(shù)1：創(chuàng)建一個空的LinkedList。
       */
      public LinkedList() {
      }

      /**
        *構(gòu)造函數(shù)2：將另外一個集合作為源數(shù)據(jù)傳入朱巨。
        */
      public LinkedList(Collection<? extends E> c) {
        this();
        //通過遍歷的方式將集合c史翘，加入到LinkedList中。
        addAll(c); //在（增）模塊里面分析代碼冀续，此處先不做分析琼讽。
      }

內(nèi)部類-Node：LinkedList實(shí)現(xiàn)雙向鏈表結(jié)構(gòu)的關(guān)鍵類。提前介紹洪唐，下面會多次用到钻蹬。

       private static class Node<E> {//通過保存三個引用實(shí)現(xiàn)雙向鏈表結(jié)構(gòu)。
        E item;//外部傳入的元素凭需。
        Node<E> next;//后一個Node節(jié)點(diǎn)问欠。
        Node<E> prev;//前一個Node節(jié)點(diǎn)。

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

添加元素（增）

重點(diǎn)介紹add粒蜈、addAll方法顺献，其他原理類似。

      /**
       * 添加元素方法1：按照默認(rèn)順序添加元素枯怖。
       */
      public boolean add(E e) {
          linkLast(e); // 從末尾添加元素注整。
          return true;
      }
      /**
       * 將元素添加首位。
       */
      private void linkFirst(E e) {
        //首先獲取集合的第一個元素度硝。
        final Node<E> f = first;
        //生成Node節(jié)點(diǎn)肿轨，首位元素，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成為第二個元素辨赐，實(shí)現(xiàn)雙向鏈表結(jié)構(gòu)
            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();//傳入集合轉(zhuǎn)換為數(shù)組兼吓。
        int numNew = a.length;
        if (numNew == 0) //傳入數(shù)組為空，添加失敗森枪。
            return false;

        Node<E> pred, succ;
        if (index == size) { //相等則直接從末尾添加视搏。
            succ = null;
            pred = last;
        } else {
            succ = node(index); // 獲取該位置的元素审孽。
            pred = succ.prev;
        }
        //遍歷數(shù)組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設(shè)置為newNode.
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;//更新pred打颤，讓后面的元素依次添加在newNode后面。
        }

        if (succ == null) {
        //如果succ==null漓滔，說明添加位置在末尾编饺。所以last設(shè)置為a的最后一個元素。
            last = pred;
        } else {//否則將pred與succ的聯(lián)系建立起來响驴。
            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：調(diào)用add（e），與add方法不同之處是具有返回值竖席。
       * Java 1.5后添加的新方法。
       * @since 1.5
       */
      public boolean offer(E e) {
        return add(e);
      }

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

      /**
       * 添加元素方法7：調(diào)用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作為結(jié)果憎亚。
       */
      public boolean remove(Object o) {
      //正序遍歷集合，找到指定元素弄慰，再去除o元素與其他元素的聯(lián)系第美。
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);//去除x元素在集合中的聯(lián)系。
                    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沒有腳標(biāo)什往，無論有沒有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++;
      }

以下方法原理類似省古≈嘧可根據(jù)興趣決定是否觀看。

      /**
       * 刪除方法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：默認(rèn)是刪除首位元素琳拭。
       * @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的區(qū)別是不會拋出異常。
   * @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相關(guān) 都不會報異常奄抽。
   *
   * @since 1.6
   */
  public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
   }

  /**
   * 查找方法8：獲取不移除末位元素蔼两。peek相關(guān) 都不會報異常。
   * @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 整體是雙向鏈表結(jié)構(gòu)，所以適合元素需要頻繁增刪档泽。
LinkedList 沒有腳標(biāo)俊戳，查找元素都是通過遍歷實(shí)現(xiàn)，建議巧用查找方法馆匿。例如靠后的元素查找就用lastIndexOf抑胎，靠前就是indexOf；刪除元素對應(yīng)的則有removeFirstOccurrence渐北、removeLastOccurrence阿逃。
遍歷元素時，強(qiáng)烈建議使用迭代器ListIterator，而不是普通for循環(huán)盆昙，然后get(index)羽历；
刪除元素時，如果是在遍歷時刪除淡喜，使用迭代器ListIterator秕磷；