目录
一、介绍
前面我们深度分析了ArrayList的源码和使用方法，它的底层是通过数组来保存每一个元素的（从ArrayList名字也显而易见），但是由于ArrayList读取快、增删慢的特点，决定了它适合于频繁读取的场景。那么如果是增删操作频繁的场景该怎么办？
今天的主角上场，铛铛铛铛~，它就是LinkedList。
顾名思义，这是一个底层数据结构采用链表的集合，而链表的特点就是顺序访问、读取慢、增删快。
看一下他的UML类图：
从UML类图中可以看到：
- 实现了
Serializable接口，说明LinkedList支持序列化 - 实现了
List接口，说明满足List集合规范，表示LinkedList是一个集合 - 实现了
Deque接口，说明满足双端队列规范，表示LinkedList是一个双端队列或栈 - 实现了
Cloneable接口，说明LinkedList可克隆。 - 继承自
AbstractSequentialList类，提供了顺序访问的基础支持，而AbstractList提供的是随机访问的支持。
虽然
LinkedList既可以作为双端队列使用，也可以作为双向链表使用，但本文主要介绍它作为双向链表时的源码部分，因为看过双端队列的源码后会发现，他和双向链表只是从宏观来看有不同的应用，但是他们的微观层面的代码逻辑其实是相同的。如果对双端队列部分感兴趣，可以自行前往源码阅读。
二、成员变量
transient int size = 0;
/**
* 指向头节点
* Invariant: (first == null && last == null) || (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* 指向尾节点
* Invariant: (first == null && last == null) || (last.next == null && last.item != null)
*/
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内部采用双向链表的数据结构来保存元素，从成员变量中也是可以看出来的。
链表中每一个节点用Node对象表示，在Node对象中，item表示当前节点实际保存的数据，next表示当前节点在链表中的下一个节点，prev表示当前节点在链表中的前一个节点。
链表的第一个元素用first属性表示，最后一个元素用last属性表示。如果为空链表，则first属性和last属性都指向null。
因此，LinkedList内部数据结构可以用下图表示。
思考：为什么使用双向链表而不是单向链表？
单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入、删除操作时)，只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。
双向链表在节点中添加了一个
prev属性来表示当前节点的前驱结点，虽然在按值查找和按位查找在时间复杂度上和单向链表相同，但是在插入和删除方面双向链表有着巨大的优势。拿删除来举例，删除单向链表中的节点时，因节点中只有
next属性，为了保证删除节点后不断链，需要遍历链表以得到待删除节点的前驱结点，因此时间复杂度为O(n)；而在双向链表的节点中还有prev属性，因此在删除节点时就可以直接得到前驱结点，从而保证不断链，因此时间复杂度为O(1)。
四、基本操作
作为一个双向链表，最基本的功能就是新增、删除、查找。下面我们来看一下LinkedList是如何实现的。
1、新增
在链表头部新增
private void linkFirst(E e) { // 声明一个临时变量f指向first节点 // 此时链表为first(f) <-> ... <-> last final Node<E> f = first; // 根据参数，实例化一个节点newNode，并使该节点的next指向first节点 // 此时链表为newNode <-> first(f) <-> ... <-> last final Node<E> newNode = new Node<>(null, e, f); // first指向新节点，此时临时变量f依然指向原first节点， // 此时链表为first(newNode) <-> f <-> ... <-> last first = newNode; if (f == null) // 如果f节点为null，则说明当前链表只有first(newNode)这一个节点，需要将last指向该节点 last = newNode; else // 否则，f节点的prev应指向first(newNode) f.prev = newNode; // 最后链表大小加一，结构修改次数加一 size++; modCount++; }
在链表尾部新增
void linkLast(E e) { // 声明一个临时变量l指向last节点 // 此时链表为first <-> ... <-> last(l) final Node<E> l = last; // 根据参数，实例化一个节点newNode，并使该节点的prev指向last节点 // 此时链表为first <-> ... <-> last(l) <-> newNode final Node<E> newNode = new Node<>(l, e, null); // last指向新节点，此时临时变量l依然指向原last节点， // 此时链表为first <-> ... <-> l <-> newNode(last) last = newNode; if (l == null) // 如果l节点为null，则说明当前链表只有newNode(last)这一个节点，需要将first指向该节点 first = newNode; else // 否则，l节点的next应指向newNode(last) l.next = newNode; // 最后链表大小加一，结构修改次数加一 size++; modCount++; }
在指定结点之前新增
/** * 在指定的节点succ前面插入数据e * 注意：指定的节点succ不能为空，否则会抛出空指针异常 * @param e 要插入的数据 * @param succ 指定的节点 **/ void linkBefore(E e, Node<E> succ) { // 根据succ.prev获得原链表中succ的前置节点 // 此时链表结构不变，first <-> ... <-> pred <-> succ <-> ... -> last final Node<E> pred = succ.prev; // 根据元素e，实例化一个新的节点newNode，新节点的前置节点指向pred，后置节点指向succ， // 此时链表结构为，first <-> ... <-> pred <-> (newNode) <-> succ <-> ... <-> last // prev节点的next依然指向succ节点，succ的prev依然指向prev节点 final Node<E> newNode = new Node<>(pred, e, succ); // 将succ的prev从prev节点指向newNode节点 // 此时链表结构为，first <-> ... <-> pred <-> (newNode <-> succ <-> ... <-> last // prev节点的next依然指向succ节点，而succ的prev则指向newNode节点 succ.prev = newNode; if (pred == null) // 如果pred节点为null，说明在原链表中succ节点即为首节点first，即succ(first) <-> ... <-> last // 这种情况下在succ节点前面添加newNode节点，则newNode节点应为现链表中的首节点first // 此时链表结构为，newNode(first) <-> succ <-> ... <-> last first = newNode; else // 否则，说明在原链表中succ节点不是首节点first，即first <-> succ <-> ... <-> last // 则需要将pred节点的next从succ节点指向newNode节点 // 此时链表结构为，first <-> ... <-> pred <-> newNode <-> succ <-> ... <-> last pred.next = newNode; // 最后链表大小加一，结构修改次数加一 size++; modCount++; }
2、删除
删除头部结点
/** * @param f 头部节点， * 在调用此方法前，需要保证f节点为头结点first，且不为空 **/ private E unlinkFirst(Node<E> f) { // 获取f节点中的元素element，待方法执行结束后返回 final E element = f.item; // 将f节点的next节点赋值给临时变量next // 此时链表结构为f(first) <-> next <-> ... <-> last final Node<E> next = f.next; // 将f节点内的item和next属性置为null，因为f节点是头结点，因此prev属性本就为null // 置为null的目的是释放内存 f.item = null; f.next = null; // 将first指向f节点的next节点， // 此时链表结构为f <-> next(first) <-> ... <-> last first = next; if (next == null) // 如果next节点为null，说明原链表只有f(first)一个节点 last = null; else // 如果next节点不为null，说明原链表有多个节点 // 此时链表结构为f -> next(first) <-> ... <-> last // 因为first节点表示首节点，因此链表结构可表示为 next(first) <-> ... <-> last next.prev = null; // 删除成功，size减一，修改次数加一 size--; modCount++; // 将已删除节点f的元素返回 return element; }
删除尾部结点
/** * @param l 尾部节点， * 在调用此方法前，需要保证l节点为尾结点last，且不为空 **/ private E unlinkLast(Node<E> l) { // 获取l节点中的元素element，待方法执行结束后返回 final E element = l.item; // 将l节点的prev节点赋值给临时变量prev // 此时链表结构为first <-> ... prev <-> last(l) final Node<E> prev = l.prev; // 将l节点内的item和prev属性置为null，因为l节点是尾结点，因此next属性本就为null // 置为null的目的是释放内存 l.item = null; l.prev = null; // 将last指向l节点的prev节点， // 此时链表结构为first <-> ... <-> prev(last) <-> l last = prev; if (prev == null) // 如果prev节点为null，说明原链表只有l(last)一个节点 first = null; else // 如果prev节点不为null，说明原链表有多个节点 // 此时链表结构为first <-> ... <-> prev(last) <- l // 因为first节点表示首节点，因此链表结构可表示为 first <-> ... <-> prev(last) prev.next = null; // 删除成功，size减一，修改次数加一 size--; modCount++; // 将已删除节点f的元素返回 return element; }
删除指定结点
/** * 调用此方法前需要保证x节点不为空 */ E unlink(Node<E> x) { // 获取x节点中的元素element，待方法执行结束后返回 final E element = x.item; // 获取x节点的前置节点prev和后置节点next final Node<E> next = x.next; final Node<E> prev = x.prev; // 链表结构为 first <-> ... <-> prev <-> x <-> next <-> ... <-> last // 处理x节点左边的节点 if (prev == null) { // 如果prev节点为null，说明x节点为头结点， // 在删除x节点后，next节点就变成了first节点 // 此时链表结构为 next(first) <-> ... <-> last first = next; } else { // 如果prev节点不为null，说明x节点不是头结点， // 在删除x节点后，prev节点的next属性就指向next节点 prev.next = next; // 将x的prev属性置为空，内存回收 x.prev = null; // 此时结构为： // prev节点后置节点为next，x的后置节点为next，next的前置节点为x } // 处理x节点右边的节点 if (next == null) { // 如果next节点为null，说明x节点为尾结点， // 在删除x节点后，prev节点就变成了last节点 // 此时链表结构为 first <-> ... <-> prev(last) last = prev; } else { // 如果next节点不为null，说明x节点不是尾结点， // 在删除x节点后，next节点的prev属性就指向prev节点 next.prev = prev; // 将x的next属性置为空，内存回收 x.next = null; // 此时结构为： // prev节点后置节点为next，next的前置节点为prev // 即 first <-> ... <-> prev <-> next <-> ... <-> last } // 将x的item属性置为空，内存回收 x.item = null; // 删除成功，size减一，修改次数加一 size--; modCount++; // 方法最后返回x节点中的元素值 return element; }
3、查找
查找头部
LinkedList的成员变量中有一个first属性，该属性始终表示内部双向链表的首节点，获取链表的第一个元素，只要将首节点中的元素取出即可
public E getFirst() { // 将first赋值给final修饰的临时变量f final Node<E> f = first; // 如果f为空，则抛出异常 if (f == null) throw new NoSuchElementException(); // 如果f不为空，则将f节点中的元素返回 return f.item; }思考：为什么不能直接对first进行非空判断，而是要再声明一个final修饰的临时变量f，转而对这个临时变量进行判断呢？
上面问题所表达的代码逻辑如下所示，差别在于省去了中间变量的操作；
public E getFirst() { if (first == null) throw new NoSuchElementException(); return first.item; }这样的逻辑乍一看没有问题，但其实忽略了多线程环境下的考虑、以及final关键字的作用：
试想一下：有一个多线程之间共享的LinkedList变量
- 线程A在调用
getFirst()方法中，条件语句first == null为false，则应该执行下一行代码：return first.item，但此时线程A失去CPU调度 - 线程B获得CPU调度，但是线程B直接对这个变量调用
clear()方法将链表清空了 - 此时线程A重新获得CPU调度并继续执行代码：
return first.item，但是该链表已经被线程B清空了，因此会抛出空指针异常
改进：
- 将first变量使用final关键字修饰，这样就可以避免其他线程对其进行修改了，但是这样的话只要涉及到修改first变量的所有操作都将报错
优化：
- 声明一个final修饰的中间变量指向first节点，这样既避免了其他线程的干扰，也可以避免修改first变量的所有操作的报错问题
- 线程A在调用
查找尾部
LinkedList的成员变量中有一个last属性，该属性始终表示内部双向链表的尾节点，获取链表的最后一个元素，只要将尾节点中的元素取出即可
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
获取指定元素的索引
该操作是为了获取指定元素在当前链表中首次出现时的位置，即获取指定元素在链表中的最小索引。
因为LinkedList的底层结构为链表，它并不像ArrayList一样能直接提供某个元素在数组中的下标，因此需要从首节点(first)逐一遍历整个链表，直到某个节点中的元素与当前指定元素相等(
equals()方法返回true)为止，此时的时间复杂度为O(n)。public int indexOf(Object o) { int index = 0; if (o == null) { // 如果指定元素为null，则从首节点至尾节点逐一遍历，直到遇到一个元素为null为止，返回index // 在遍历的过程中，每遍历一个节点，index加一 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++; } } // 如果当前链表中不存在指定元素，则返回-1表示不存在 return -1; }下面我们以查找某一个链表中存在的元素为例，用动图来演示一下此方法的逻辑
移除指定元素
在了解
indexOf(Object o)方法和unlink(Node<E> x)方法后，相信对remove(Object o)方法的源码也了如指掌了该方法使用和
indexOf(Object o)方法一样的遍历方法，从首节点至尾节点逐一遍历，当遍历到某个节点时发现该节点的元素和参数相等，就表示删除当前节点即可，删除节点直接调用unlink(Node<E> x)方法即可。public boolean remove(Object o) { if (o == null) { // 对链表中的节点逐一遍历 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { // 遍历过程中当前节点的元素值与参数一致，调用unlink(Node<E> x)方法删除当前节点即可 unlink(x); // 删除成功后返回true return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } // 如果整个链表中都不存在要删除的元素则返回false return false; }
根据索引获取节点
通过
node(int index)方法获取指定索引的节点，该方法采用一次二分法来提升查找效率，通过size >> 1将当前链表从中间一分为二，如果参数index位于链表的前半段，则只需要从first到中间位置正序遍历，如果参数index位于链表的后半段，则只需要从last到中间位置倒序遍历。Node<E> node(int index) 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; } }但是此逻辑仍有不完美的地方，参数index越趋向于链表中间位置，遍历所需要花费的时间自然也越长，当链表足够长的时候，所需要的时间复杂度依然为O(n)。
或许设计者是这样想的，链表本身的有点是根据节点来操作，它最怕的就是使用索引操作，能提供给我们一个通过索引来操作的方法就不错了，如果非要用索引操作，请移步基于数组实现的
ArrayList。
五、特点
- 以节点对链表进行操作时，时间复杂度为O(1)，因为每个节点中都包含了前置节点和后置节点的引用，可以直接获取到前后节点
- 以索引对链表进行操纵时，时间复杂度为O(n)，因为在链表中并没有维护当前节点下标的属性，只能通过遍历来获取指定的节点，然后再对链表进行操作。
