JDK1.8源码分析：LinkedList

接口和数据结构

• LinkedList，实现了List和Deque接口，其中Deque是双向队列，即可以在队列头部和尾部进行插入或删除数据节点。LinkedList也不是线程安全的。

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

• LinkedList为了实现以上功能，在内部使用了双向链表这种数据结构。数据结构定义如下：

  // 链表长度
  transient int size = 0;
      /**
   * Pointer to first node.
   * Invariant: (first == null && last == null) ||
   *            (first.prev == null && first.item != null)
   */
  transient Node<E> first;
  
  /**
   * Pointer to last node.
   * Invariant: (first == null && last == null) ||
   *            (last.next == null && last.item != null)
   */
  transient Node<E> last;
  
  private static class Node<E> {
      E item;
      Node<E> next;
      Node<E> prev;
  
      Node(Node<E> prev, E element, Node<E> next) {
          this.item = element;
          this.next = next;
          this.prev = prev;
      }
  }
  

  Node为链表节点，item为进行数据存放，类型为泛型E；pref和next分别为当前链表节点的前后节点。

链表指定位置操作

• 对链表指定位置操作，是通过指定某个索引，类似于数组下标，来获取指定位置的数据。核心实现为提供了一个node(index)的方法来查找index对应的链表节点，如get，set为例：

  public E get(int index) {
      checkElementIndex(index);
      return node(index).item;
  }
  /**
   * Replaces the element at the specified position in this list with the
   * specified element.
   *
   * @param index index of the element to replace
   * @param element element to be stored at the specified position
   * @return the element previously at the specified position
   * @throws IndexOutOfBoundsException {@inheritDoc}
   */
  public E set(int index, E element) {
      checkElementIndex(index);
      Node<E> x = node(index);
      E oldVal = x.item;
      x.item = element;
      return oldVal;
  }
  
  
  /**
   * Returns the (non-null) Node at the specified element index.
   */
  Node<E> node(int index) {
      // assert isElementIndex(index);
  
      // index在前半部分，则从头开始查找
      if (index < (size >> 1)) {
          Node<E> x = first;
          for (int i = 0; i < index; i++)
              x = x.next;
          return x;
      // index在后半部分，则从尾部开始查找
      } else {
          Node<E> x = last;
          for (int i = size - 1; i > index; i--)
              x = x.prev;
          return x;
      }
  }
  

  node方法主要利用了头部，尾部指针和链表长度size，对于给定的index，如果在链表前半部分，则直接头部开始查找，如果在链表后半部分，则从尾部指针往前查找，从而可以减少遍历次数，提高性能。

链表头部操作

• 链表头部操作是指相对于内部的双向链表的头结点进行操作，具体为增删查改。

  public E getFirst() {
      final Node<E> f = first;
      if (f == null)
          throw new NoSuchElementException();
      return f.item;
  }
  
  public E removeFirst() {
      final Node<E> f = first;
      if (f == null)
          throw new NoSuchElementException();
      return unlinkFirst(f);
  }
  // 删除链表头部节点
  /**
   * Unlinks non-null first node f.
   */
  private E unlinkFirst(Node<E> f) {
      // assert f == first && f != null;
      final E element = f.item;
      final Node<E> next = f.next;
      f.item = null;
      f.next = null; // help GC
      first = next;
      if (next == null)
          last = null;
      else
          next.prev = null;
      size--;
      modCount++;
      return element;
  }
  
  public void addFirst(E e) {
      linkFirst(e);
  }   
  
  // 在链表头部插入节点
  /**
   * Links e as first element.
   */
  private void linkFirst(E e) {
      final Node<E> f = first;
      final Node<E> newNode = new Node<>(null, e, f);
      first = newNode;
      if (f == null)
          last = newNode;
      else
          f.prev = newNode;
      size++;
      modCount++;
  }
  
  // 获取头部节点
  public E peek() {
      final Node<E> f = first;
      return (f == null) ? null : f.item;
  }
  // poll和remove都是获取并删除头部节点
  // 还有pollFirst，pollLast版本的方法
  public E poll() {
      final Node<E> f = first;
      return (f == null) ? null : unlinkFirst(f);
  }
  public E remove() {
      return removeFirst();
  }
  
  public void push(E e) {
      addFirst(e);
  }
  public E pop() {
      return removeFirst();
  }
  

链表尾部操作

• 链表尾部操作是指相对于内部的双向链表的尾部结点进行操作，具体为增删查改。

  public E getLast() {
      final Node<E> l = last;
      if (l == null)
          throw new NoSuchElementException();
      return l.item;
  }
  
  public E removeLast() {
      final Node<E> l = last;
      if (l == null)
          throw new NoSuchElementException();
      return unlinkLast(l);
  }
    
  // add和addLast都是在链表尾部添加元素  
  public void addLast(E e) {
      linkLast(e);
  } 
  public boolean add(E e) {
      linkLast(e);
      return true;
  }
  
  // 在链表尾插入节点
  /**
   * Links e as last element.
   */
  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++;
  }
  
  // 在尾部添加节点
  // 还有offerFirst，offerLast版本的方法
  public boolean offer(E e) {
      return add(e);
  }
  

链表长度size

• 在LinkedList中也使用了一个size来维护当前链表的长度，在添加或删除链表节点时，同步更新该size的值，从而可以直接返回该size变量来获取该链表当前存在多少元素。

  public int size() {
      return size;
  }
  

清空链表

• 将链表内所有节点置null，头部和尾部节点置null，从而可以让GC回收。

  public void clear() {
      // Clearing all of the links between nodes is "unnecessary", but:
      // - helps a generational GC if the discarded nodes inhabit
      //   more than one generation
      // - is sure to free memory even if there is a reachable Iterator
      for (Node<E> x = first; x != null; ) {
          Node<E> next = x.next;
          x.item = null;
          x.next = null;
          x.prev = null;
          x = next;
      }
      first = last = null;
      size = 0;
      modCount++;
  }