Java LinkedList源码剖析

   <h2>总体介绍</h2>    <p><em>LinkedList</em>同时实现了<em>List</em>接口和<em>Deque</em>接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（<em>Queue</em>），同时又可以看作一个栈（<em>Stack</em>）。这样看来，<em>LinkedList</em>简直就是个全能冠军。当你需要使用栈或者队列的时候，首先应该考虑的就是<em>LinkedList</em>。因为Java官方已经声明不建议使用<em>Stack</em>类，推荐使用<em>LinkedList</em>，更遗憾的是，Java里根本没有一个叫做<em>Queue</em>的类（它是个接口名字）。</p>    <p><img alt="Java LinkedList源码剖析" src="https://simg.open-open.com/show/5f44d2e5c0168afc3af84f345f39a7c7.png" width="800" height="499"></p>    <p><em>LinkedList</em>底层<strong>通过双向链表实现</strong>，本节将着重讲解插入和删除元素时双向链表的维护过程，也即是之间解跟<em>List</em>接口相关的函数，而将<em>Queue</em>和<em>Stack</em>以及<em>Deque</em>相关的知识放在下一节讲。双向链表的每个节点用内部类<em>Node</em>表示。<em>LinkedList</em>通过<code>first</code>和<code>last</code>引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候<code>first</code>和<code>last</code>都指向<code>null</code>。</p>    <pre>  <code class="language-java">//Node内部类  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;      }  }</code></pre>    <p><em>LinkedList</em>的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率<em>LinkedList</em>没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用<code>Collections.synchronizedList()</code>方法对其进行包装。</p>    <h2>方法剖析</h2>    <h3>add()</h3>    <p><em>add()</em>方法有两个版本，一个是<code>add(E e)</code>，该方法在<em>LinkedList</em>的末尾插入元素，因为有<code>last</code>指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是<code>add(int index, E element)</code>，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。</p>    <p><img alt="Java LinkedList源码剖析" src="https://simg.open-open.com/show/7971b8bdf34d125e7d58aae574f58091.png" width="800" height="436"></p>    <p>结合上图，可以看出<code>add(E e)</code>的逻辑非常简单。</p>    <pre>  <code class="language-java">//add(E e)  public boolean add(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++;      return true;  }</code></pre>    <p><br> <code>add(int index, E element)</code>的逻辑稍显复杂，可以分成两部，1.先根据index找到要插入的位置；2.修改引用，完成插入操作。</p>    <pre>  <code class="language-java">//add(int index, E element)  public void add(int index, E element) {      checkPositionIndex(index);//index >= 0 && index <= size;      if (index == size)//插入位置是末尾，包括列表为空的情况          add(element);      else{          Node<E> succ = node(index);//1.先根据index找到要插入的位置          //2.修改引用，完成插入操作。          final Node<E> pred = succ.prev;          final Node<E> newNode = new Node<>(pred, e, succ);          succ.prev = newNode;          if (pred == null)//插入位置为0              first = newNode;          else              pred.next = newNode;          size++;      }  }</code></pre>    <p>上面代码中的<code>node(int index)</code>函数有一点小小的trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件<code>index < (size >> 1)</code>，也即是index是靠近前端还是后端。</p>    <h3>remove()</h3>    <p><code>remove()</code>方法也有两个版本，一个是删除跟指定元素相等的第一个元素<code>remove(Object o)</code>，另一个是删除指定下标处的元素<code>remove(int index)</code>。</p>    <p><img alt="Java LinkedList源码剖析" src="https://simg.open-open.com/show/9e88026a0e0f0185df0c6fedebf0a41b.png" width="800" height="569"></p>    <p>两个删除操作都要1.先找到要删除元素的引用，2.修改相关引用，完成删除操作。在寻找被删元素引用的时候<code>remove(Object o)</code>调用的是元素的<code>equals</code>方法，而<code>remove(int index)</code>使用的是下标计数，两种方式都是线性时间复杂度。在步骤2中，两个<code>revome()</code>方法都是通过<code>unlink(Node<E> x)</code>方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。</p>    <pre>  <code class="language-java">//unlink(Node<E> x)，删除一个Node  E unlink(Node<E> x) {      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;//let GC work      size--;      return element;  }</code></pre>    <h2>get()</h2>    <p><code>get(int index)</code>得到指定下标处元素的引用，通过调用上文中提到的<code>node(int index)</code>方法实现。</p>    <pre>  <code class="language-java">public E get(int index) {      checkElementIndex(index);//index >= 0 && index < size;      return node(index).item;  }</code></pre>    <h3>set()</h3>    <p><code>set(int index, E element)</code>方法将指定下标处的元素修改成指定值，也是先通过<code>node(int index)</code>找到对应下表元素的引用，然后修改<code>Node</code>中<code>item</code>的值。</p>    <pre>  <code class="language-java">public E set(int index, E element) {      checkElementIndex(index);      Node<E> x = node(index);      E oldVal = x.item;      x.item = element;//替换新值      return oldVal;  }</code></pre>    <p>来源：https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/3-LinkedList.md</p>