1、LinkedList 简介
一个由 Node 节点组成的双向链表集合，可以存放任意元素包括 null 。
看其内部重要源代码（存储元素的结构）：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { // 元素个数 transient int size = 0; // 头节点 transient Node<E> first; // 尾节点 transient Node<E> last; // 节点结构 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; } } // ... }
存储元素时，内部效果如图：
都说，LinkedList 集合增删快、查询慢，那这是什么依据，其内部又是如何增删元素的，这些就都是我所要分析的点，往下看吧！
2、属性分析
代码就不贴了，上面已经贴过其所有的属性了，属性不多。
- size：链表集合中元素个数。
- first：头结点，头插法时指向刚添加进来的元素，初始值为 null。
- last：尾节点，头插法时指向第一个插入的元素，尾插法时指向刚插入的元素，初始值为 null。
- Node：内部类，定义节点结构的，其内部包括三个属性：值、前驱指针、后驱指针。
注意的是，属性都被 transient 关键字修饰，说明 LinkedList 内部实现了自己的一套序列化逻辑，提高内存利用率，减少 null 值的空间占用。
3、构造器
源码：
/** * Constructs an empty list. */ public LinkedList() { }
空构造器，说明没有默认长度，当然也不需要有默认长度，有元素就创建节点，没有就不创建。
4、头插法
顾名思义就是每次添加元素的时候都在其头部添加元素，源码如下：
private void linkFirst(E e) { // 头节点 final Node<E> f = first; // 创建节点 final Node<E> newNode = new Node<>(null, e, f); // 头节点指向新创建节点 first = newNode; // 是否是第一个头节点 if (f == null) // 是第一个头节点，那头节点和尾节点都指向新创建节点 last = newNode; else // 不是第一个节点，那将开始头节点指向的节点per引用指向新创建的节点 f.prev = newNode; // 元素个数加一 size++; // 修改次数加一 modCount++; }
第一次看代码可能是有点晕，毕竟是关于地址指向的问题，下面我就来分析分析。
头插法插入元素分为两种情况：
- 插入的元素为第一个元素
- 插入的元素不是第一个元素
具体分析如下：
1、插入第一个元素
初始状态，LinkedList 集合属性状态：
初始状态，头尾指针都是指向 null。
下面，我根据头插法代码往集合中加入第一个元素，来程序运行的效果图：
结合运行效果图，当使用头插法插入第一个元素结束后，头尾指针都会指向第一个添加的元素。
2、插入的不是第一个元素
那当添加的不是第一个元素，结合上图加入第二个元素，程序运行效果图如下：
当加入第二个元素时，头节点指针指向最新添加的元素，且 first 的 next 指向前一个元素，而前一个元素的 per 指针指向 first 节点。
如此往复的通过头插法添加元素我们发现，first 永远会指向最新添加的元素，并且最新元素和前一个元素互相指引形成一个双向链表。
5、尾插法
和头插法正好相反，每次添加元素的时候都是在其尾部添加元素，源码如下：
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++; }
也是和头插法类似，添加数据时，插入的情况有两种：
- 尾插法插入的元素是第一个元素。
- 尾插法插入的元素不是第一个元素。
具体分析：
1、插入第一个元素
通过尾插法，插入第一个元素效果图如下：
我们可以发现，尾插法插入第一个元素时过程虽然和头插法不太一样，但最终的结果确一样，头尾指针都指向第一个元素。
2、插入不是第一个元素
那当添加的不是第一个元素，结合上图加入第二个元素，程序运行效果图如下：
和头插法不同的是，尾插法每次添加元素都是 last 节点移动，并指向最新添加的元素。
6、移除元素
移除方法有很多重载，我就挑几个经常使用的移除方法分析。
源码一如下：
public E remove() { // 移除头结点指向的元素 return removeFirst(); } public E removeFirst() { // 定义中间变量 f final Node<E> f = first; // 如果头指针为 null 说明集合中就没有元素，抛错 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; // 如果集合为空，last 和 first 指向 null if (next == null) last = null; else // 如果集合中还有元素，那 first 节点 per 指针为 null next.prev = null; // 元素个数减一 size--; // 修改次数加一 modCount++; // 返回移除元素值 return element; }
remove 不带参数的移除方法就是移除集合中 first 节点指向的元素，并且 first 顺延指向下一个元素。
结合上节插入元素的链表结构，移除的大致效果图如下：
主要功能还是 unlinkFirst 方法，将 first 头指针指向下一个元素，并将要移除的元素置空。
源码二如下：
public E remove(int index) { // 检查下标，如果下标不在 size 范围内，报错 checkElementIndex(index); // 获取下标指定的节点，并开始移除 return unlink(node(index)); } // 找到下标对应的节点 Node<E> node(int index) { // assert isElementIndex(index); // 判断下标更靠近头结点还是尾节点 if (index < (size >> 1)) { // 靠近头结点 // 遍历，找到下标为 index 的节点返回 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 靠近尾节点 // 遍历，找到下标为 index 的节点返回 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return 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 { // 不是头结点 // 前驱节点的 next 指向要移除节点的后驱节点 prev.next = next; // 移除节点的 per 置空 x.prev = null; } if (next == null) { // 移除的是尾结点，尾结点向前指一位 last = prev; } else { // 不是尾结点 // 将要移除的后驱节点 per 指向要移除节点的 前驱节点 next.prev = prev; // 移除节点的 next 置空 x.next = null; } // 移除节点值置空 x.item = null; // 大小减一 size--; // 修改次数加一 modCount++; // 返回移除元素的值 return element; }
结合代码，根据下标移除元素的逻辑并不是很复杂，我总结出如下实现步骤：
- 检查下标是否在 size 范围内
- 根据下标，找到移除的节点
- 将节点移除链表，并将链表的前驱指针和后驱指针链接正确
大体上就是这三步，难点应该就是第三步，节点移除，指针指向问题，下面我再来画个移除图，便于理解。
源码三如下：
public boolean remove(Object o) { // 是否移除 null 值 if (o == null) { // 移除第一个碰到的 null 元素 for (Node<E> x = first; x != null; x = x.next) { // 遍历，找到第一个为 null 值得 节点 if (x.item == null) { // 调用 源码二 分析的 unLink 方法，移除节点 unlink(x); return true; } } } else { // 移除第一个碰到的 o 元素 for (Node<E> x = first; x != null; x = x.next) { // 比较节点值是否和要移除的节点值相等 if (o.equals(x.item)) { // 调用 源码二 分析的 unLink 方法，移除节点 unlink(x); return true; } } } // 没找到要移除的值，返回 false return false; }
根据值移除元素，底层的实现逻辑就可以看出来，LinkedList 是可以存储 null 值的。
而且移除思路也是先变量一遍链表找到要移除的元素，再调用移除节点的方法进行移除（该方法在上面讲过），成功移除返回true，反之 false。
7、添加方法
上面分析了头插法和尾插法，那我们就来看看 LinkedList 集合是如何添加元素的了，看源码：
public boolean add(E e) { // 默认尾插法添加元素 linkLast(e); return true; }
前面分析了尾插法，现在看到 add 源码其底层就是通过调用尾插法的方法来添加元素，这也是集合元素有序性的原因。
通常我们也会调用下面方法，在指定的下标处添加元素，方法源码如下：
public void add(int index, E element) { // 检查下标是否在 size 范围内 checkPositionIndex(index); // 如果就添加在 尾部，那直接使用尾插法 if (index == size) linkLast(element); else // 不在尾部那就插在 index 下标指向的 node 节点之前 linkBefore(element, node(index)); } // 元素，插在 succ 节点之前 void linkBefore(E e, Node<E> succ) { // assert succ != null; // 定义中间遍历，获取 succ 节点的 per 指向的节点 final Node<E> pred = succ.prev; // 创建要插入的节点 final Node<E> newNode = new Node<>(pred, e, succ); // 将 succ 的 per 指向 新创建的 节点 succ.prev = newNode; // 是否是插在头结点前 if (pred == null) // 是，那就把 first 指针指向新创建的节点 first = newNode; else // 否，将开始 succ 节点 per 指向的前驱节点的 next 指向 新创建的 节点 pred.next = newNode; // 元素个数加一 size++; // 修改次数加一 modCount++; }
结合源码，在指定下标处添加元素，首先会检查下标是否在 size 范围内，然后会根据下标获取到对应位置的元素节点，最后才是插入元素。
linkBefore 方法看字面意思就知道，在指定节点之前插入元素，下面就根据该方法画出对应的运行效果图：
指定下标插入元素的重要步骤就是搞清楚 next 及 per 指针的指向问题。例如本次案例就是先将 e 节点的 per 指向 e3 、next 指向 e2 节点，然后再把 e3 的 next 和 e2 的 per 指向 e 节点即完成一次元素的插入。
8、清空方法
LinkedList 清空方法源码如下：
public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator // 从头结点开始循环遍历集合 for (Node<E> x = first; x != null; ) { // 中间变量，定义下一个元素节点 Node<E> next = x.next; // 将当前节点置空 x.item = null; x.next = null; x.prev = null; // 继续操作下一个节点 x = next; } // 头尾指针指向 null 表示集合为空 first = last = null; // size 大小 size = 0; // 修改次数加一 modCount++; }
清空方法很简单，就是从头结点挨个遍历置空，最后将头尾指针指向 null 并修改 size 大小即可。
9、源码分析总结
经过了很长的源码分析篇幅，基本上吧 LinkedList 中比较基础的方法都过了一遍，那我针对这些源码概括一下 LinkedList 的几个特性：
- 底层使用 Node 节点形式存储数据
- first 、last 两个节点指针分别指向链表的两头
- first 、last 都指向 null 时表示为空集合
- 添加元素时，头插法和尾插法的时间复杂度都是O(1)
- 删除元素时，时间复杂度是O(1)
- 访问元素时，如果不是头尾节点，时间复杂度是O(n)
- 内部没有初始容量，所以不会有扩容现象
- 内部没有锁机制，是一个线程不安全的集合
好了，今天的内容到这里就结束了，关注我，我们下期见。
