1. 链表综述

LinkedList是基于链表实现的，所以先讲解一下什么是链表。链表原先是C/C++的概念，是一种线性的存储结构，意思是将要存储的数据存在一个存储单元里面，这个存储单元里面除了存放有待存储的数据以外，还存储有其下一个存储单元的地址（下一个存储单元的地址是必要的，有些存储结构还存放有其前一个存储单元的地址），每次查找数据的时候，通过某个存储单元中的下一个存储单元的地址寻找其后面的那个存储单元。

这么讲可能有点抽象，先提一句，LinkedList是一种双向链表，双向链表我认为有两点含义：

1. 链表中任意一个存储单元都可以通过向前或者向后寻址的方式获取到其前一个存储单元和其后一个存储单元

2. 链表的尾节点的后一个节点是链表的头结点，链表的头结点的前一个节点是链表的尾节点

2. 链表定义

2.1 继承和实现：

• 继承了AbstractSequentialList抽象类：在遍历LinkedList的时候，官方更推荐使用顺序访问，也就是使用我们的迭代器。（因为LinkedList底层是通过一个链表来实现的）（虽然LinkedList也提供了get（int index）方法，但是底层的实现是：每次调用get（int index）方法的时候，都需要从链表的头部或者尾部进行遍历，每一的遍历时间复杂度是O(index)，而相对比ArrayList的底层实现，每次遍历的时间复杂度都是O(1)。所以不推荐通过get（int index）遍历LinkedList。至于上面的说从链表的头部后尾部进行遍历：官方源码对遍历进行了优化：通过判断索引index更靠近链表的头部还是尾部来选择遍历的方向）（所以这里遍历LinkedList推荐使用迭代器）。
• 实现了List接口。（提供List接口中所有方法的实现）
• 实现了Cloneable接口，它支持克隆（浅克隆），底层实现：LinkedList节点并没有被克隆，只是通过Object的clone（）方法得到的Object对象强制转化为了LinkedList,然后把它内部的实例域都置空，然后把被拷贝的LinkedList节点中的每一个值都拷贝到clone中。（后面有源码解析）
• 实现了Deque接口。实现了Deque所有的可选的操作。
• 实现了Serializable接口。表明它支持序列化。（和ArrayList一样，底层都提供了两个方法：readObject（ObjectInputStream o）、writeObject（ObjectOutputStream o），用于实现序列化，底层只序列化节点的个数和节点的值）。

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

2.2 数据结构：

LinkedList是一个双向链表，则一定有存储单元，LinkedList的存储单元是它的一个静态内部类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;
    }
}

其中item是真正存储的数据，next和prev分别是前后个和前一个存储单元的引用地址。用图表示：

3. 初始化

初始化有2种方式：

• 初始化一个空链表

transient int size = 0;

transient Node<E> first; // 头单元

transient Node<E> last; // 尾单元

 // 空的构造函数，初始化prev和next
 public LinkedList() {
 }

• 根据一个集合初始化，将集合种的数据存放到链表中

 // 含参构造，根据一个Collection初始化	
 public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

3. 链表操作

3.1 添加操作：

因为LinkedList即实现了List接口，又实现了Deque接口，所以LinkedList既可以添加将元素添加到尾部，也可以将元素添加到指定索引位置，还可以添加整个集合；另外既可以在头部添加，又可以在尾部添加。下面我们分别从List接口和Deque接口分别介绍。

3.1.1 List接口添加

3.1.1.1 末尾添加add(E e)

假如我在链表中添加元素做了哪些事情？首先我们看看插入代码：

List<String> list = new LinkedList<String>();
list.add("111");
list.add("222");

1. 第一句初始化调用无参构造，做的事情可以看成：
   初始化一个空的item，值为null，同时将它的prev设置为first的引用地址，next设置为last的引用地址，而此时first和last都是null。
   debug展示：

2. 第二句，插入111做了什么事情，我们看看相关的源码：

public boolean add(E e) {
   linkLast(e);
   return true;
}

void linkLast(E e) {
   final Node<E> l = last; // 定义一个node指向链表尾部
   // 初始化成员变量：this.item = e; this.next = null; this.prev = l;
   final Node<E> newNode = new Node<>(l, e, null);
   last = newNode; // 将new的节点设置为尾节点
   if (l == null) 
       first = newNode; // 如果之前的为节点是空，则头节点是新节点
   else
       l.next = newNode; // 否则，上一个节点的next指向新节点
   size++;
   modCount++;
}

根据源码，
首先定义一个Node，并赋值为last，用于判断
然后new一个新的Node假设地址为0x00000001，node的item赋值为111，next存的地址为null，prev存的地址为l即last，此时last是null，如图所示即：

最后分别是将链表的last指向当前new的Node，如果之前的last为空的话，那么first也指向new的Node，如果不为空，则上一个Node的next指向new出来的地址，如图表示即：

debug展示：

3. 第三句，插入222
代码解释就不说了，我们画图直接来看插入222的图解，我们假设222的地址是0x00000002：
首先new一个新的Node并设值：

然后重新设置first和last及上一个节点的尾节点：

debug展示：

3.1.1.2 中间插入add(int index, E e)

在原来代码基础上执行如下代码做了哪些事情？

list.add(1, 333);

首先来看源码：

public void add(int index, E element) {
        checkPositionIndex(index); // 查看index是否越界或小于0

        if (index == size)
            linkLast(element); // 相当于在最后添加
        else
            linkBefore(element, node(index));
    }
    
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev; // 初始化index处节点的前节点
        // new一个新节点，item = e, prev = pred, next = succ 
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode; // 原index处节点的前节点设置为新节点
        if (pred == null)
            first = newNode; // 如果前节点为空，说明是第一个节点
        else
            pred.next = newNode;// 否则原节点的前节点的尾节点指向为新节点
        size++;
        modCount++;
    }
// 返回index处的Node
Node<E> node(int index) {
        // assert isElementIndex(index);
        
        if (index < (size >> 1)) { // 判断index是处于前半段还是后半段
        	// 前半段就从头节点用next向后遍历直到index，
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
        	// 后半段就从尾节点用prev向前遍历直到index
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

简单翻译一下就是：
首先找到index位置的节点即succ，定义一个pred代表succ的前节点，然后new一个新节点，前节点为pred，后节点为succ，假设333的地址是0x00000003：

然后将succ的前节点设置为新节点，pred的后节点设置为新节点，如果pred为null，则将新节点设置为头节点：

3.1.2 Deque接口添加

3.1.2.1 addFirst(E e)

addFirst()方法用于将元素添加到链表头部，源码如下（上面画图基本上LinkedList的数据结构也了解了，简单的逻辑就不画图直接通过文字解释了）：

	public void addFirst(E e) {
        linkFirst(e);
    }
     private void linkFirst(E e) {
        final Node<E> f = first; 
        // 新建节点，前节点为null，后节点为原头节点
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode; // 头节点设置为新节点
        if (f == null)
            last = newNode; // 如果原头节点为null，则尾节点为新节点
        else
            f.prev = newNode; // 否则原头节点的前节点为新节点
        size++;
        modCount++;
    }

3.1.2.2 addLast(E e)方法

addLast()方法用于将元素添加到链表尾部，与add()方法一样。所以实现也一样，如下：

public void addLast(E e) {
        linkLast(e);
    }

3.1.2.3 offer(E e)方法

offer(E e)方法用于将数据添加到链表尾部，其内部调用了add(E e)方法，如下：

  public boolean offer(E e) {
        return add(e);
    }

3.1.2.4 offerFirst(E e)方法

offerFirst()方法用于将数据插入链表头部，与addFirst的区别在于该方法可以返回特定的返回值，而addFirst的返回值为void。

  public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

3.1.2.5 offerLast(E e)方法

offerLast()与addLast()的区别和offerFirst()和addFirst()的区别一样，所以这儿就不多说了。

3.1.3 添加操作总结

LinkedList由于实现了List和Deque接口，所以有多种添加方法，下面总结了一下。

• 将数据插入到链表尾部
  • boolean add(E e):
  • void addLast(E e)
  • boolean offerLast(E e)
• 将数据插入到链表头部
  • void addFirst(E e)
  • boolean offerFirst(E e)
• 将数据插入到指定索引位置
  • boolean add(int index,E e)

3.2 查询操作

3.2.1 根据index检索

3.2.1.1 获取任意位置数据：get(int index)

根据指定index查询数据：

public E get(int index) {
		// 越界检测
        checkElementIndex(index);
        // node方法源码已经展示过了，可以看上面，主要是：
        //1. 先判断index处于list的前半段还是后半段
        //2. 前半段就从头节点用next向后遍历直到index，
        // 后半段就从尾节点用prev向前遍历直到index
        return node(index).item; 
    }

3.2.1.2 获取头节点：

LinkedList中有多种方法可以获得头节点的数据，实现大同小异，区别在于对链表为空时的处理，是抛出异常还是返回null。主要方法有getFirst()、element()、peek()、peekFirst()方法。其中getFirst()和element()方法将会在链表为空时，抛出异常，它们的实现如下：

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
public E element() {
    return getFirst();
}

从代码可以看到，element()方法的内部就是使用getFirst()实现的。它们会在链表为空时，抛出NoSuchElementException。下面再看peek()和peekFirst()的实现：

public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

从代码可以看到，当链表为空时，peek()和peekFirst()方法返回null。

3.2.1.3 获得尾节点数据

获得尾节点数据的方法有getLast()和peekLast()。getLast()的实现如下：

 public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

可以看到，getLast()方法在链表为空时，会抛出NoSuchElementException，而peekLast()则不会，只是会返回null。实现如下：

 public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

3.2.2 根据对象得到索引

根据对象得到索引分为两种，一种是第一个匹配的索引，一个是最后一个匹配的索引，实现的在于一个从前往后遍历，一个从后往前遍历。

3.2.2.1 从前往后索引

indexOf方法是从前往后找到第一个匹配的index：

//返回第一个匹配的索引
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; //没有结果返回-1
}

从上面的代码可以看到，LinkedList可以包含null元素，遍历方式都是从前往后，一旦匹配了，就返回索引。

3.2.2.2 从后往前索引

lastIndexOf()方法返回最后一个匹配的索引，实现为从后往前遍历，源码如下：

//返回最后一个匹配的索引
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;
    }

注意index自增和自减的顺序。

3.2.3 判断是否包含某对象：

contains(Object o)方法检查对象o是否存在于链表中，其实现如下：

 public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

3.2.4 检索操作总结

检索操作分为按照位置得到对象以及按照对象得到位置两种方式，其中按照对象得到位置的方法有indexOf()和lastIndexOf()；按照位置得到对象有如下方法：

• 根据任意位置得到数据的get(int index)方法，当index越界会抛出异常
• 获得头节点数据
• getFirst()和element()方法在链表为空时会抛出NoSuchElementException
• peek()和peekFirst()方法在链表为空时会返回null
• 获得尾节点数据
• getLast()在链表为空时会抛出NoSuchElementException
• peekLast()在链表为空时会返回null

3.3 删除操作

删除操作分为按照位置删除和按照对象删除，其中按照位置删除的方法又有区别，有的只是返回是否删除成功的标志，有的还需要返回被删除的元素。下面分别讨论。

3.3.1 删除指定对象

当删除指定对象时，只需调用remove(Object o)即可，不过该方法一次只会删除一个匹配的对象，如果删除了匹配对象，返回true，否则false。其实现如下：

public boolean remove(Object o) {
    if (o == null) {
    	// 从前往后查找，碰到匹配的就调用unlink方法
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true; // 删除成功返回true，否则返回false
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

因为LinkedList可以存放null，所以要对是不是null分开判断，主要还是unlink方法，源码如下：

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) {
    	// 如果前节点是null，说明头节点是要删除的节点，将头节点设置为后继节点
        first = next; 
    } else {
        prev.next = next; // 否则前驱节点的后节点尾当前节点的后节点
        x.prev = null; // 当前节点的前节点设为null
    }

    if (next == null) {
    	// 如果后节点是null，说明尾节点是要删除的节点，将尾节点设置为前驱节点
        last = prev;
    } else {
        next.prev = prev; // 否则后继节点的前驱节点尾当前节点的前节点
        x.next = null; // 当前节点的后节点设为null
    }

    x.item = null; // 当前节点的内容设为null
    size--;
    modCount++;
    return element; // 返回删除节点的值
}

接下来我用画图来展示一下：
原链表：

首先是对前驱节点的操作：

然后是对后继节点的操作：

最后将要删除的节点的内容设为null：

3.3.2 按照位置删除对象

3.3.2.1 删除任意位置的对象

boolean remove(int index)方法用于删除任意位置的元素，如果删除成功将返回true，否则返回false。实现如下：

 public E remove(int index) {
    //检查index范围
    checkElementIndex(index);
    //将节点删除
    return unlink(node(index));
}

从上面可以看到remove(int index)操作有两步：

1. 检查index范围，属于[0,size）
2. 将索引出节点删除

3.3.2.2 删除头节点的对象

删除头节点的对象的方法有很多，包括remove()、removeFirst()、pop()、poll()、pollFirst()，其中前三个方法在链表为空时将抛出NoSuchElementException，后两个方法在链表为空时将返回null。
remove()、pop()、removeFirst()的实现如下：

public E remove() {
        return removeFirst();
    }

public E pop() {
        return removeFirst();
    }

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(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;
 }

从上面代码可以看到，remove()和pop()内部调用了removeFirst()方法，而removeFirst()在链表为空时将抛出NoSuchElementException。
下面是poll()和pollFirst()的实现：

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

可以看到poll()和pollFirst()的实现代码是相同的，在链表为空时将返回null。

3.3.2.3 删除尾节点的对象

删除尾节点的对象的方法有removeLast()和pollLast()。removeLast的实现如下：

public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

可以看到removeLast()在链表为空时将抛出NoSuchElementException。而pollLast()方法则不会，如下：

public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

可以看到pollLast()在链表为空时会返回null，而不是抛出异常。

删除操作总结

删除操作由很多种方法，有：

• 按照指定对象删除：boolean remove(Object o)，一次只会删除一个匹配的对象
• 按照指定位置删除
• 删除任意位置的对象：E remove(int index),当index越界时会抛出异常
• 删除头节点位置的对象
• 在链表为空时抛出异常：E remove()、E removeFirst()、E pop()
• 在链表为空时返回null：E poll()、E pollFirst()
• 删除尾节点位置的对象
• 在链表为空时抛出异常：E removeLast()
• 在链表为空时返回null：E pollLast()

3.4 迭代器操作

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

调用listIterator(int index)方法，其中参数表示迭代器开始的位置。在ArrayList源码分析中提到过ListIterator是一个可以指定任意位置开始迭代，并且有两个遍历方法。下面直接看ListItr的实现：

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;//保存当前modCount，确保fail-fast机制

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);//得到当前索引指向的next节点
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    //获取下一个节点
    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    //获取前一个节点，将next节点向前移
    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

在ListIterator的构造器中，得到了当前位置的节点，就是变量next。next()方法返回当前节点的值并将next指向其后继节点，previous()方法返回当前节点的前一个节点的值并将next节点指向其前驱节点。由于Node是一个双端节点，所以这儿用了一个节点就可以实现从前向后迭代和从后向前迭代。另外在ListIterator初始时，exceptedModCount保存了当前的modCount，如果在迭代期间，有操作改变了链表的底层结构，那么再操作迭代器的方法时将会抛出ConcurrentModificationException。

参考：
https://blog.csdn.net/qq_19431333/article/details/54572876
https://www.cnblogs.com/xrq730/p/5005347.html
https://blog.csdn.net/m0_37884977/article/details/80467658