对于 LinkedList ，我们先来看一下JDK中对LinkedList源码的一点解释：

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

大致意思就是：LinkedList 是 List 和 Deque 的双链表实现，实现所有可选列表操作，并允许所有元素（包括null）。
链表 是数据结构中 线性结构 的一种。
再简单说一下Deque吧，它不是这篇文章的主角！

Deque 是 double ended queue 的简写，即“双端队列”。Deque是线性集合，支持两端插入和移除元素。大多数Deque实现对它们可能包含的元素数量没有固定限制，但是此接口支持容量限制的双锻链表以及没有固定大小限制的。此接口定义了访问双端队列两端元素的方法。提供了插入，移除和检查元素的方法。这些方法中的每一种都以两种形式存在：一种在操作失败时抛出异常，另一种返回特殊值（null或false，具体取决于操作）。后一种形式的插入操作专门设计用于容量限制的Deque实现；在大多数实现中，插入操作不会失败。

LinkedList 是 非线程安全的，插入和删除速度快，但是随机访问的速度就比较慢了。为什么呢？接下来我们就从源码一探究竟吧！

以下源码基于 JDK 1.8.0_11。

首先来说一下 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;
    }
}

增加

对于添加功能来说，最常用的两个方法分别是 add(E e) 和 add(int index, E element)
(1). add(E e)：直接添加元素至链表尾部

public boolean add(E e) {
    // 直接插入链表尾部
    linkLast(e);
    return true;
}

// linkLast(E element) 方法源码
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    // 默认新节点为链表的尾节点
    last = newNode;
    // 如果原链表的尾节点为 null ，说明链表是空的，则新节点就是第一个节点
    // 否则新节点就成了原尾节点的后继节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 链表大小 + 1
    size++;
    // modCount + 1
    modCount++;
}

(2). add(int index, E element)：添加元素 element 至链表指定索引 index 处

public void add(int index, E element) {
    // 该方法的主要作用是检查 index 是否在区间 [0,size] 内 (size是指链表的大小，初始值为0)
    checkPositionIndex(index);
    // 如果要插入的 index == size ，直接插入至链表尾部
    // 否则插入到链表 index 位置处
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

// linkBefore(E e, Node<E> succ) 方法源码
void linkBefore(E e, Node<E> succ) {
    // 获取 succ 的前驱节点
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    // succ 的前驱节点指向新节点
    succ.prev = newNode;
    // 如果原链表 succ 节点的前驱节点为 null，则说明原链表是空链表
    // 那么新节点就理所当然的应该是第一个节点了
    // 否则，新节点即为原链表 succ 节点的前驱节点的后继节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    // 链表大小 + 1
    size++;
    // modCount + 1
    modCount++;
}

linkBefore(E e, Node<E> succ) 方法分析：

linkBefore.png

对于在链表中的添加操作，一般用到的就这两种，要么直接添加到链表尾部，要么添加到链表指定位置。根据自己的需求选择对应的方法使用即可。

删除

对于删除功能来说，最常用的两个方法分别是 remove(int index) 和 remove(Object o)。
(1). remove(int index)：删除链表指定位置某元素

public E remove(int index) {
    // 该方法的主要作用是检查 index 是否在区间 [0,size) 内
    checkElementIndex(index);
    // 如果上面的方法不会抛异常，就直接调用 unlink(node(index));
    return unlink(node(index));
}

// unlink(Node<E> x) 方法：取消链接，即删除元素
E unlink(Node<E> x) {
    // 获取 x 节点的相关属性
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    // 如果x的前驱为 null，说明x就是链表的第一个节点
    // 要删除x节点，直接将x的后继节点变为链表的首节点即可
    if (prev == null) {
        first = next;
    } else {
     // 否则，让 x 的前驱节点的后继节点赋值为 x 的后继节点，x 的前驱节点置为 null
        prev.next = next;
        x.prev = null;
    }
    // 如果 x 的后继为 null，说明 x 就是链表的尾节点
    // 则直接将链表的尾节点赋值为 x 的前驱节点
    if (next == null) {
        last = prev;
    } else {
     // 否则，让 x 的后继节点的前驱节点赋值为 x 的前驱节点，x 的后继节点置为 null
        next.prev = prev;
        x.next = null;
    }
    // 置空，等待GC回收
    x.item = null;
    // 链表大小 - 1
    size--;
    // modCount + 1
    modCount++;
    // 返回被删除的元素
    return element;
}

unlink(Node<E> x) 方法其实就是 linkBefore(E e, Node<E> succ) 的逆向过程，这里就不画图分析了。
(2). remove(Object o)：删除链表中的某元素

public boolean remove(Object o) {
    // 因为链表允许 null 元素，所以这里需要判断待删除元素是否是 null 元素
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            // 找到为 null 的元素 
            if (x.item == null) {
                // 直接删除
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            // 找到待删除的元素
            if (o.equals(x.item)) {
                // 直接删除
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

修改

修改链表中的元素使用的是 set(int index, E element) 方法，即修改指定 index 位置处的元素。

public E set(int index, E element) {
    // 该方法的主要作用是检查 index 是否在区间 [0,size) 内
    checkElementIndex(index);
    // 获取指定 index 处的节点 x 
    Node<E> x = node(index);
    // 以下两步就完成了新值与旧值的替换工作
    E oldVal = x.item;
    x.item = element;
    // 修改完后返回的是旧值
    return oldVal;
}

查询

查询使用的是 get(int index) 方法，获取指定 index 位置处节点的 item 值。因为查找的时候要从头节点或者尾节点开始查找，所以当链表比较长的时候效率可能就不是很理想。

public E get(int index) {
    // 该方法的主要作用是检查 index 是否在区间 [0,size) 内
    checkElementIndex(index);
    // 返回指定 index 处节点的 item 值
    return node(index).item;
}

// node(int index) 方法源码
Node<E> node(int index) {
    // 根据 size >> 1 即size右移一位的结果，判断是从链表的头节点查找还是从尾节点查找
    // 有点类似折半查找的感觉
    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;
    }
}

遍历

为什么说使用迭代器遍历 list 的时候要避免使用类似 add、remove这种修改 list 结构的操作？原因就是如果在创建迭代器之后的任何时候对列表进行结构修改(因为修改list结构的时候modCount会自增)，迭代器将抛出并发修改异常ConcurrentModificationException。比如下面的代码就会抛出 ConcurrentModificationException

public class LinkedListTest {
    public static void main(String[] args) {
        List list = new LinkedList();
        list.add("first");
        list.add("a");
        list.add("m");
        list.add("p");
        list.add(null);
        list.add("last");

        Iterator iterator = list.iterator();
        while (iterator.hasNext()){
            Object next = iterator.next(); // 第二次循环的时候就会抛异常
            list.remove("m");
            System.out.println(next);
        }
    }
}

来看一下调用这个异常的方法实现：

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

相关的源码比较多，就不贴出来了，简单说一下抛出这个异常的原因吧：
第一次调用 next() 方法的时候 expectedModCount 就已经被赋值了(expectedModCount = modCount; )，当下面的代码调用了 remove() 方法后，修改了 modCount 的值(modCount++;)，所以当第二次遍历进来的时候，调用 next() 方法，next() 方法再调用 checkForComodification() 方法时，就会检测到这两个值不相等，所以抛出异常。
关于 LinkedList 的常用方法就说这些吧，还有一些方法可能并没有提及，但是也不难，如果你肯努力，你一定会看懂的！请记住，千万不要假装自己很努力！

我是bearPotMan，一个经验不足的十八线演(码)员(农)。
Know everything,control everything!