介绍

LinkedList将做为双端链表来实现，它本身实现了List接口和Deque接口，并且实现了所有可选的列表操作，并且允许包含所有元素（包括null）。
下面是LinkedList的类图：
image.png
虽然LinkedList有get(int index)方法，但是不推荐通过for循环调用get方法来遍历它，因为get内部实际上是从头部或尾部进行遍历，get一次的时间复杂度是O(n)，而ArrayList的get的时间复杂度是O(1)的。如果你要遍历LinkedList，调用iterator函数获取迭代器进行遍历是一个最佳选择。

内部结构

先看看成员变量有哪些

  1.     transient int size = 0;
  3.     /**
  4.      * Pointer to first node.
  5.      * Invariant: (first == null && last == null) ||
  6.      *            (first.prev == null && first.item != null)
  7.      */
  8.     transient Node<E> first;
  10.     /**
  11.      * Pointer to last node.
  12.      * Invariant: (first == null && last == null) ||
  13.      *            (last.next == null && last.item != null)
  14.      */
  15.     transient Node<E> last;

size是链表的大小，first指向链表的头结点，last指向链表的尾节点，节点用Node表示。

  1.     private static class Node<E> {
  2.         E item;
  3.         Node<E> next;
  4.         Node<E> prev;
  6.         Node(Node<E> prev, E element, Node<E> next) {
  7.             this.item = element;
  8.             this.next = next;
  9.             this.prev = prev;
  10.         }
  11.     }

item表示当前节点下存储的数据，next指向下一个节点，prev指向上一个节点，这样通过prev和next指针连接起来就构成了链表。

构造方法

  1.     public LinkedList() {
  2.     }

默认构造和ArrayList有所不同，构造方法是一个空的函数，因为ArrayList底层通过数组保存数组，可以事先指定数组的大小，但是LinkedList并不需要，LinkedList通过prev和next指针来连接每一个节点，它的大小是动态变化的，也不需要扩容。
除此之外，还有第二个构造方法，传入一个Collection集合来初始化链表。

  1.     public LinkedList(Collection<? extends E> c) {
  2.         this();
  3.         addAll(c);
  4.     }
  6.     public boolean addAll(Collection<? extends E> c) {
  7.         // 这里初始化size是0，从0下标位置进行添加
  8.         return addAll(size, c);
  9.     }
  11.     // 在链表的指定位置前插入一个集合作为链表
  12.     public boolean addAll(int index, Collection<? extends E> c) {
  13.         // 检查index的范围
  14.         checkPositionIndex(index);
  15.         // 集合转为数组
  16.         Object[] a = c.toArray();
  17.         // 获取数组的长度
  18.         int numNew = a.length;
  19.         // 长度为0，直接返回，不进行添加
  20.         if (numNew == 0)
  21.             return false;
  22.         // 定义指定插入index位置的节点succ 和succ的上一个节点pred
  23.         Node<E> pred, succ;
  24.         // 如果添加的位置是在末尾
  25.         if (index == size) {
  26.             // 在末尾进行添加，pred赋值为last节点，指定位置node为null
  27.             succ = null;
  28.             pred = last;
  29.         } else {
  30.              // 不是在末尾进行添加，先根据index查到对应的节点再赋值
  31.             succ = node(index);
  32.             pred = succ.prev;
  33.         }
  34.         // 遍历待添加的元素数组，把元素添加到链表
  35.         for (Object o : a) {
  36.             @SuppressWarnings("unchecked") E e = (E) o;
  37.             // 构造新节点，值为e，上一个节点是pred
  38.             Node<E> newNode = new Node<>(pred, e, null);
  39.             // 上一个节点pred等于null，说明前面没有元素，当前节点是头节点
  40.             if (pred == null)
  41.                 // 把newNode节点赋值给头节点first
  42.                 first = newNode;
  43.             else
  44.                 // 连接pred和newNode，通过next指针连接起来
  45.                 pred.next = newNode;
  46.             // 当前节点赋值给上一个节点pred，用于下次遍历
  47.             pred = newNode;
  48.         }
  49.         // 在末尾进行添加的，给尾节点last进行赋值即可
  50.         if (succ == null) {
  51.             last = pred;
  52.         } else {
  53.             // 不是在末尾进行的添加，还需要连接前后
  54.             pred.next = succ;
  55.             succ.prev = pred;
  56.         }
  57.         // size大小增加
  58.         size += numNew;
  59.         modCount++;
  60.         return true;
  61.     }
  63.     // 根据index索引到对应的node节点
  64.     Node<E> node(int index) {
  65.         // assert isElementIndex(index);
  66.         // 判断下标是在前半部分还是后半部分
  67.         if (index < (size >> 1)) {
  68.             // 从first节点顺序遍历查找
  69.             Node<E> x = first;
  70.             for (int i = 0; i < index; i++)
  71.                 x = x.next;
  72.             return x;
  73.         } else {
  74.              // 从last节点倒序遍历查找
  75.             Node<E> x = last;
  76.             for (int i = size - 1; i > index; i--)
  77.                 x = x.prev;
  78.             return x;
  79.         }
  80.     }

添加节点

  1.     // 在头部插入节点
  2.     public void addFirst(E e) {
  3.         linkFirst(e);
  4.     }
  6.     // 在尾部插入节点
  7.     public void addLast(E e) {
  8.         linkLast(e);
  9.     }
  11.     // 在指定位置插入节点
  12.     public void add(int index, E element) {
  13.         // check index范围
  14.         checkPositionIndex(index);
  15.         // 在尾部插入，直接调用linkLast
  16.         if (index == size)
  17.             linkLast(element);
  18.         else
  19.             // 在一个节点之前插入，先通过node(index)找到指定位置的节点
  20.             linkBefore(element, node(index));
  21.     }
  23.     // 在指定节点succ前插入节点，值为e
  24.     void linkBefore(E e, Node<E> succ) {
  25.         // assert succ != null;
  26.         // 获取succ的上一个节点pred
  27.         final Node<E> pred = succ.prev;
  28.         // 构造新的节点
  29.         final Node<E> newNode = new Node<>(pred, e, succ);
  30.         // succ的上一个节点指针prev指向新节点newNode
  31.         succ.prev = newNode;
  32.         // 如果pred为null，说明succ之前本来没有节点，那么新的节点插入进来就是头节点了
  33.         if (pred == null)
  34.             // 头节点赋值
  35.             first = newNode;
  36.         else
  37.             // 把pred的next指针指向新的节点，插入完毕
  38.             pred.next = newNode;
  39.         // 大小+1
  40.         size++;
  41.         modCount++;
  42.     }
  44.     // 在头部插入节点
  45.     private void linkFirst(E e) {
  46.         // 获取当前头节点的值
  47.         final Node<E> f = first;
  48.         // 构造新插入的节点，他的下一个节点是原来的头节点f
  49.         final Node<E> newNode = new Node<>(null, e, f);
  50.         // 把新节点作为头节点
  51.         first = newNode;
  52.         // 原来没有头节点，说明之前链表是空的
  53.         if (f == null)
  54.             // 新节点是第一个节点，所以尾节点也是它
  55.             last = newNode;
  56.         else
  57.             // 原来的头节点不是空,把之前头节点的prev指针指向新的节点
  58.             f.prev = newNode;
  59.         // 大小+1
  60.         size++;
  61.         modCount++;
  62.     }
  64.     // 在尾部插入节点
  65.     void linkLast(E e) {
  66.         // 获取尾节点
  67.         final Node<E> l = last;
  68.         // 构造新插入的节点，上一个节点是原来的尾节点l
  69.         final Node<E> newNode = new Node<>(l, e, null);
  70.         // 把新节点作为尾节点
  71.         last = newNode;
  72.         // 原来没有尾节点，说明之前链表为空
  73.         if (l == null)
  74.             // 新节点是第一个节点，头节点也是它
  75.             first = newNode;
  76.         else
  77.             // 原来的尾节点不是空,把之前尾节点的next指针指向新的节点
  78.             l.next = newNode;
  79.         // 大小+1
  80.         size++;
  81.         modCount++;
  82.     }

移除节点

  2.     // 移除并返回第一个元素
  3.     public E removeFirst() {
  4.         final Node<E> f = first;
  5.         if (f == null)
  6.             throw new NoSuchElementException();
  7.         return unlinkFirst(f);
  8.     }
  10.     // 移除并返回最后一个元素
  11.     public E removeLast() {
  12.         final Node<E> l = last;
  13.         if (l == null)
  14.             throw new NoSuchElementException();
  15.         return unlinkLast(l);
  16.     }   
  18.     // 移除指定位置元素并返回
  19.     public E remove(int index) {
  20.         checkElementIndex(index);
  21.         return unlink(node(index));
  22.     }
  24.     // 移除头节点f
  25.     private E unlinkFirst(Node<E> f) {
  26.         // assert f == first && f != null;
  27.         // 先获取节点的值，用于返回
  28.         final E element = f.item;
  29.         // 获取f节点的下一个节点next
  30.         final Node<E> next = f.next;
  31.         // 清空节点的值
  32.         f.item = null;
  33.         // 清除next指针
  34.         f.next = null; // help GC
  35.         // 头节点变为next节点
  36.         first = next;
  37.         // 如果next节点为null，说明移除后链表没有节点了
  38.         if (next == null)
  39.             // last节点也是null
  40.             last = null;
  41.         else
  42.             // next节点是头节点，所以next的prev指针指向null
  43.             next.prev = null;
  44.         // 大小-1
  45.         size--;
  46.         modCount++;
  47.         return element;
  48.     }
  50.     // 移除尾节点
  51.     private E unlinkLast(Node<E> l) {
  52.         // assert l == last && l != null;
  53.         // 先获取节点的值，用于返回
  54.         final E element = l.item;
  55.         // 获取l节点的上一个节点prev
  56.         final Node<E> prev = l.prev;
  57.         // 清空节点的值
  58.         l.item = null;
  59.         // 清空prev指针
  60.         l.prev = null; // help GC
  61.         // 尾节点变为尾节点的上一个节点prev
  62.         last = prev;
  63.         // 上一个节点为null，说明移除之后链表就没有节点了
  64.         if (prev == null)
  65.             // 头节点也要赋值为null
  66.             first = null;
  67.         else
  68.             // prev作为新的尾节点，它的next需要指向null
  69.             prev.next = null;
  70.         // 大小-1
  71.         size--;
  72.         modCount++;
  73.         return element;
  74.     }
  76.     // 移除指定元素x
  77.     E unlink(Node<E> x) {
  78.         // assert x != null;
  79.         // 获取指定元素x的值
  80.         final E element = x.item;
  81.         // 获取x的下一个节点next
  82.         final Node<E> next = x.next;
  83.         // 获取x的上一个节点prev
  84.         final Node<E> prev = x.prev;
  85.         // 上一个节点为空，说明要移除的节点x是头节点
  86.         if (prev == null) {
  87.             // 移除后头节点应该是x的下一个节点next
  88.             first = next;
  89.         } else {
  90.             // 更改上一个节点的next指针，指向x的next
  91.             prev.next = next;
  92.             // 断开x与prev节点之间的连接
  93.             x.prev = null;
  94.         }
  95.         // 下一个节点为空，说明要移除的节点x是尾节点
  96.         if (next == null) {
  97.             // 移除后尾节点应该是x的上一个节点prev
  98.             last = prev;
  99.         } else {
  100.             // 更改下一个节点的prev指针，指向x的prev
  101.             next.prev = prev;
  102.             // 断开x与next节点之间的连接
  103.             x.next = null;
  104.         }
  105.         // x前后节点的指针都已经断开，接着把值item赋值为null，可以进行GC
  106.         x.item = null;
  107.         // 大小-1
  108.         size--;
  109.         modCount++;
  110.         return element;
  111.     }

迭代器

LinkedList的迭代器有两种，一种是ListIterator顺序迭代，一种是DescendingIterator降序迭代。

  1.  private class ListItr implements ListIterator<E> {
  2.         private Node<E> lastReturned;
  3.         private Node<E> next;
  4.         private int nextIndex;
  5.         private int expectedModCount = modCount;
  7.         ListItr(int index) {
  8.             // assert isPositionIndex(index);
  9.             next = (index == size) ? null : node(index);
  10.             nextIndex = index;
  11.         }
  13.         public boolean hasNext() {
  14.             return nextIndex < size;
  15.         }
  17.         public E next() {
  18.             checkForComodification();
  19.             if (!hasNext())
  20.                 throw new NoSuchElementException();
  22.             lastReturned = next;
  23.             next = next.next;
  24.             nextIndex++;
  25.             return lastReturned.item;
  26.         }
  28.         public boolean hasPrevious() {
  29.             return nextIndex > 0;
  30.         }
  32.         public E previous() {
  33.             checkForComodification();
  34.             if (!hasPrevious())
  35.                 throw new NoSuchElementException();
  37.             lastReturned = next = (next == null) ? last : next.prev;
  38.             nextIndex--;
  39.             return lastReturned.item;
  40.         }
  42.         public int nextIndex() {
  43.             return nextIndex;
  44.         }
  46.         public int previousIndex() {
  47.             return nextIndex - 1;
  48.         }
  50.         public void remove() {
  51.             checkForComodification();
  52.             if (lastReturned == null)
  53.                 throw new IllegalStateException();
  55.             Node<E> lastNext = lastReturned.next;
  56.             unlink(lastReturned);
  57.             if (next == lastReturned)
  58.                 next = lastNext;
  59.             else
  60.                 nextIndex--;
  61.             lastReturned = null;
  62.             expectedModCount++;
  63.         }
  65.         public void set(E e) {
  66.             if (lastReturned == null)
  67.                 throw new IllegalStateException();
  68.             checkForComodification();
  69.             lastReturned.item = e;
  70.         }
  72.         public void add(E e) {
  73.             checkForComodification();
  74.             lastReturned = null;
  75.             if (next == null)
  76.                 linkLast(e);
  77.             else
  78.                 linkBefore(e, next);
  79.             nextIndex++;
  80.             expectedModCount++;
  81.         }
  83.         public void forEachRemaining(Consumer<? super E> action) {
  84.             Objects.requireNonNull(action);
  85.             while (modCount == expectedModCount && nextIndex < size) {
  86.                 action.accept(next.item);
  87.                 lastReturned = next;
  88.                 next = next.next;
  89.                 nextIndex++;
  90.             }
  91.             checkForComodification();
  92.         }
  94.         final void checkForComodification() {
  95.             if (modCount != expectedModCount)
  96.                 throw new ConcurrentModificationException();
  97.         }
  98.     }
  100.     private class DescendingIterator implements Iterator<E> {
  101.         private final ListItr itr = new ListItr(size());
  102.         public boolean hasNext() {
  103.             return itr.hasPrevious();
  104.         }
  105.         public E next() {
  106.             return itr.previous();
  107.         }
  108.         public void remove() {
  109.             itr.remove();
  110.         }
  111.     }