学过数据结构的都知道双端队列（链表），没学过的也没有关系，下面我先介绍一下双端队列（链表），为什么要介绍它了，因为LinkedList本质上就是一个双端队列（链表）。
一. 双端队列（链表）的介绍
1. 如下图：双端队列（链表）中单个节点对应的结构
每个节点包含三个部分：
指向前一个节点的引用
指向后一个节点的引用
自身存储的数据元素
引用在C语言中就相当于指针，在Java语言中，习惯用引用来描述地址的指向。
2. 如下图：双端队列的整体结构
二. LinkedList的介绍（基于JDK1.8）
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
（1）实现了List接口，表明LinkedList是一个有序、可重复元素的集合
（2）实现了Deque，表明LinkedList是一个双端队列（链表）
（3）实现了Cloneable接口，表明LinkedList支持克隆，即可以重写Object.clone方法，否则在重写clone方法时，报CloneNotSupportedException
（4）实现了Serializable接口，可以被序列化与反序列化
三. 基本属性
// 链表的长度transient int size = 0;// 链表的头节点transient Node<E> first;// 链表的尾节点transient Node<E> last;
四. 构造方法（有2个）
（1）无参构造函数
// 无参构造函数public LinkedList() {}
（2）传入一个集合对象
// 传入一个集合，自动初始化一个含有相同长度的，且列表元素相同的LinkedListpublic LinkedList(Collection<? extends E> c) { this(); addAll(c);}
五. 静态内部类 （重点）
（1）表示双端队列（链表）的一个节点的类
// 此类使用了泛型，传入的类型表示存储元素的类型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; }}
六. 主要方法解析
（1）linkFirst(E e)，将元素插入到头部
图解源码：红色为原始链表部分，蓝色为修改部分，如下所示
（2）linkLast（E e），插入一个元素到尾部
void linkLast(E e) { // 定义一个节点，指向尾节点，在插入完成之后，f表示倒数第二个节点 final Node<E> l = last; // 构造一个新节点，用它来表示新尾节点，尾节点的定义就是（下一个节点引用指向null） // 如下表示（之前last节点，就变成了倒数第二个节点，就是新尾节点的上一个节点引用） final Node<E> newNode = new Node<>(l, e, null); // 改变全局尾节点的引用，指向新尾节点 last = newNode; // f为空，表示插入的元素为第一个，即头节点和首节点为一个，如果插入的不是第一个元素， // 则需要把之前的last节点的下一个节点引用指向新尾节点 if (l == null) first = newNode; else l.next = newNode; size++; modCount++;}
图解源码：红色为原始链表部分，蓝色为修改部分，如下所示
（3）linkBefore(E e，Node
// 在指定节点之前插入一个元素void linkBefore(E e, Node<E> succ) { // assert succ != null; // 定义一个指定节点的上一个引用 final Node<E> pred = succ.prev; // 定义一个新节点，新节点的前引用指向pred,新节点的后引用指向指定节点 final Node<E> newNode = new Node<>(pred, e, succ); // 指定节点的前节点引用为新节点 succ.prev = newNode; if (pred == null) first = newNode; else // pred的后节点引用为新节点 pred.next = newNode; size++; modCount++;}
图解源码：红色为原始链表部分，蓝色为修改部分，如下所示
（4）unlinkFirst（Node
// 移除头节点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 // 将全局变量的头节点重新定义为f.next first = next; // 如果当前链表只有一个元素，则移除头节点后，头节点和尾节点都为空 if (next == null) last = null; else // 如果当前链表中有多个元素，移除头节点后，第二个节点就为头节点 next.prev = null; size--; modCount++; return element;}
图解源码：红色为原始链表部分，蓝色为修改部分，如下所示
（5）unlinkLast(Node
// 移除尾节点private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; // 找到尾节点的前节点，就是倒数第二个节点 final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; // 如果链表中只有一个元素，则移除尾节点后，头节点和尾节点都为空 if (prev == null) first = null; else // 如果当前链表中有多个元素，移除尾节点后，倒数第二个节点就为尾节点 prev.next = null; size--; modCount++; return element;}
图解源码：红色为原始链表部分，蓝色为修改部分，如下所示
（6）unlink(Node
// 移除某个节点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; x.prev = null; } // 如果后节点为空，则表示移除的是尾节点 if (next == null) { last = prev; } else { // 如果移除的是中间的某个节点，则移除节点的前节点为prev next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element;}
图解源码：红色为原始链表部分，蓝色为修改部分，如下所示
（7）node(int index)，根据下标找到对应的节点，重点的重点
// 根据下标找到对应的节点Node<E> node(int index) { // assert isElementIndex(index); // size >> 1表示size的一半，就是size/2 if (index < (size >> 1)) { // 下标小于size的一半，就从0开始遍历到，每遍历一次把节点引用后移一位 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 下标大于或者等于size的一半，就从最后一个开始遍历，每遍历一次把节点引用前移一位 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}
图解源码：红色为原始链表部分，蓝色为修改部分，如下所示
总结：
1). LinkedList的add，remove方法都是基于以上7个方法扩展来的
2). LinkedList本身没有下标的概念，因为从源码上看，每个节点都只包含三个属性（前节点引用，后节点引用，存储元素），但这并不代表它是无序的，因为双向链表的前后引用，导致它成为了一个有序队列。
本文分享自微信公众号 - Java学习进阶手册（javastudyup）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
