LinkedList（JDK1.8） 源码阅读记录

LinkedList

LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。

• LinkedList同样是非线程安全的，只在单线程下适合使用。

• LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。

---

先看LinkedList数据结构

/** 再看下这个节点吧
 *  LinkedList中的内部类
 */
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;
        }
    }

---

根据JDK版本的不同 ，构造方法也不同

/**
 * JDK1.8
 * Deque接口，Deque接口表示是一个双端队列，那么也意味着LinkedList是双端队列的一种实现，
 * 所以，实现了基于双端队列的所有操作。
 */
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    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;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

---

/**
 * 构造方法在1.6版本也不太一样
 *  默认构造函数：创建一个空的链表  
 */
 
public LinkedList() {  
    header.next = header.previous = header;  
}  
/**
 *  链表的表头，表头不包含任何数据。Entry是个链表类数据结构。 相当于1.8 Node
 */
private transient Entry<E> header = new Entry<E>(null, null, null); 
/**
 * 包含“集合”的构造函数:创建一个包含“集合”的LinkedList 
 */ 
public LinkedList(Collection<? extends E> c) {  
    this();  
    addAll(c);  
}

---

/** 
 * 因为数据结构不大一样 所以add方式也不一样 
 * remove方式 实现方式有一点不一样
 */
 /**
  * JDK1.8 节点Node
  * 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++;
 }
 /**
  * Unlinks non-null node x.
  */
  E unlink(Node<E> x) {
      // assert x != null;
      final E element = x.item;
      final Node<E> next = x.next;
      final Node<E> prev = x.prev;

      if (prev == null) {
          first = next;
      } else {
          prev.next = next;
          x.prev = null;
      }

      if (next == null) {
          last = prev;
      } else {
          next.prev = prev;
          x.next = null;
      }

      x.item = null;
      size--;
      modCount++;
      return element;
  }

 /**
  * JDK1.6 节点Entry
  * 将节点(节点数据是e)添加到entry节点之前。  
  */
  private Entry<E> addBefore(E e, Entry<E> entry) {  
      // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e  
      Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);  
      newEntry.previous.next = newEntry;  
      newEntry.next.previous = newEntry;  
      // 修改LinkedList大小  
      size++;  
      // 修改LinkedList的修改统计数：用来实现fail-fast机制。  
      modCount++;  
      return newEntry;  
  }
  /**
   * 将节点从链表中删除    
   */   
 private E remove(Entry<E> e) {  
      if (e == header)  
          throw new NoSuchElementException();  

      E result = e.element;  
      e.previous.next = e.next;  
      e.next.previous = e.previous;  
      e.next = e.previous = null;  
      e.element = null;  
      size--;  
      modCount++;  
      return result;  
  }

---

##Java 集合中常见 checkForComodification()方法的作用? modCount和expectedModCount作用?

---

Node的查找加速

/**
 * 源码中先将index与长度size的一半比较，if index < (size >> 1)，就只从位置0往后遍历到位置index处，
 * 而如果index > (size >> 1)，就只从位置size往前遍历到位置index处。 
 * 这样可以减少一部分不必要的遍历，从而提高一定的效率（实际上效率还是很低）。 
 * JDK1.8这里用的是位运算 ， 而JDK1.6 用的是判断index<size/2
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        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;
    }
}

每次看都有新发现，都会更新记录！