一、简述
我们知道，数据结构中主要有两种存储结构，分别是：顺序存储结构（线性表）、链式存储结构（链表），在Java中，对这两种结构分别进行实现的类有：
- 顺序存储结构：ArrayList、Vector、Stack
- 链式存储结构：LinkedList、Queue
二、归纳
- 继承了AbstractList抽象类，实现了List和Deque接口，底层基于双向链表实现的，允许null的存在。
- 实现了Cloneable, java.io.Serializable接口，所以支持复制(拷贝)、序列化。
- LinkedList中的元素就是一个个的节点，而真正的数据则存放在Node之中。
- 增和删除操非常快【时间复杂度：O(1)】，查和改操作相对较慢【时间复杂度：最快O(1)最慢O(n)】。
- LinkedList的操作单线安全，多线程不安全。
三、分析
1、接口
在分析ArrayList源码之前，我们先来看看集合的接口--List。
public interface List<E> extends Collection<E> {
...
// 增
boolean add(E e);
void add(int index, E element);
// 删
boolean remove(Object o);
E remove(int index);
// 改
E set(int index, E element);
// 查
E get(int index);
...
}
在上述接口中，我只抽取了比较重要的几个方法，然后以此为后续重点分析目标，其List接口对应的源码中远不止上述几个方法，有兴趣的同学可以自行翻阅。
2、成员变量
在LinkedList的源码中,其成员变量并不多,所以在此把它们都一一列出。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
// 序列化唯一表示UID
private static final long serialVersionUID = 876323262645176354L;
// LinkedList的大小，其实就是其内部维护的双向链表存储元素的数量
transient int size = 0;
// 头结点，指向第一个节点的指针或引用，默认为null
transient Node<E> first;
// 尾节点，指向最后一个节点的指针或引用，默认为null
transient Node<E> last;
...
}
3、构造函数
构造函数是一个类最常见的，同样也是最常被使用到的，接着我们分析LinkedList的两个不同的构造函数。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 无参的构造函数
*/
public LinkedList() {
}
/**
* 有参构造函数
* 构造包含指定元素的列表集合
*
* @param c 集合元素
* @throws NullPointerException 如果c为null，则会抛出空指针异常
*/
public LinkedList(Collection<? extends E> c) {
// 指向无参的构造函数
this();
addAll(c);
}
...
}
4、内部的Node节点
因为LinkedList是双向链表，故从下面的Node节点可以看出有两个指针数据，一个指向上一个节点，一个指向下一个节点；</br>
- 为什么Node这个类是静态的？</br>
答案是：这跟内存泄露有关，Node类是在LinkedList类中的，也就是一个内部类，若不使用static修饰，那么Node就是一个普通的内部类，在java中，一个普通内部类在实例化之后，默认会持有外部类的引用，这就有可能造成内存泄露。但使用static修饰过的内部类（称为静态内部类），就不会有这种问题，在Android中，有很多这样的情况，如Handler的使用。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
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;
}
}
...
}
5、增
LinkedList的增操作有两种实现，分别为add(E e)和add(int index, E element)，下面我们来分析其两种实现。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 将指定的元素添加到此列表的末尾
*
* @param e 将要添加的元素
* @return 返回true标识添加成功
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 将指定的元素添加到指定的位置
*
* @param index 要插入指定元素的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException 如果索引角标不合法，则抛出索引越界异常
*/
public void add(int index, E element) {
// 判断index是否合法，不合法则抛出索引越界异常
checkPositionIndex(index);
// 判断要添加的是否是最后一个索引位置
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 将元素e添加到链表最后
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
// 如果当前链表还没有元素，则将当前元素赋值为first
if (l == null)
first = newNode;
else
l.next = newNode;
// 维护size
size++;
// 用来记录LinkedList结构性变化的次数
modCount++;
}
/**
* 将元素e插入到指定的index索引位置
*/
void linkBefore(E e, Node<E> succ) {
// 获取原本index索引位置的元素的前节点
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
// 维护size
size++;
// 用来记录LinkedList结构性变化的次数
modCount++;
}
/**
* 返回指定元素索引处的(非空)节点
*/
Node<E> node(int index) {
// 它对index与集合长度的一半做比较，来确定是在集合的前半段还是后半段进行查找，
// 从而达到节省一半的时间。
// size>>1相当于size除以2，这里的意思就是判断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;
}
}
...
}
6、删
LinkedList的删操作有两种实现，分别是remove(int index)和remove(Object o)，下面我们来分析其两种实现。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
**
* 删除索引为index的元素并返回
*
* @param index 要删除的索引
* @return 返回删除的元素
* @throws IndexOutOfBoundsException 抛出索引角标越界异常
*/
public E remove(int index) {
// 判断index是否合法，不合法则抛出索引越界异常
checkElementIndex(index);
return unlink(node(index));
}
/**
* 删除元素o，并且返回是否有效删除
*
* @param o 元素将从此列表中删除(如果存在)
* @return 如果存在该元素将其删除并返回true，否则返回false
*/
public boolean remove(Object o) {
// 这里把空和非空进行区分，空的话用“==”判断，非空用“equals”判断
if (o == null) {
// 从头节点开始遍历检索
for (Node<E> x = first; x != null; x = x.next) {
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;
}
/**
* 断开非空节点x的链接
*/
E unlink(Node<E> x) {
// 获取当前节点的元素
final E element = x.item;
// 获取当前节点的下一个节点
final Node<E> next = x.next;
// 获取当前节点的上一个节点
final Node<E> prev = x.prev;
// 判断当前节点的上一个节点是否为null，如果为null则代表x是头结点
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 判断当前节点的下一个节点是否为null，如果为null则代表x是尾结点
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 将节点x置空
x.item = null;
// 维护size
size--;
// 用来记录LinkedList结构性变化的次数
modCount++;
return element;
}
...
}
7、改
LinkedList的改操作有一种实现，对应的是set(int index, E element)，下面我们来分析这种实现。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 修改索引角标为index的元素值
*
* @param index 要修改的索引坐标
* @param element 修改后存储的元素值
* @return 返回修改前的元素值
* @throws IndexOutOfBoundsException 抛出索引角标越界异常
*/
public E set(int index, E element) {
// 判断index是否合法，不合法则抛出索引越界异常
checkElementIndex(index);
// 获取索引为index的节点
Node<E> x = node(index);
// 获取节点x的值
E oldVal = x.item;
// 将元素element赋值给节点x的item
x.item = element;
// 返回原本节点x的值
return oldVal;
}
...
}
8、查
LinkedList的查操作有一种实现，对应的是get(int index)，下面我们来分析这种实现。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 查找索引角标为index的元素值
*
* @param index 要修改的索引坐标
* @return 返回查找到的索引为index的元素值
* @throws IndexOutOfBoundsException 抛出索引角标越界异常
*/
public E get(int index) {
// 判断index是否合法，不合法则抛出索引越界异常
checkElementIndex(index);
return node(index).item;
}
...
}
四、队列
1、LinkedList源码分析为什么会牵扯到Queue？
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
}
从上面的代码中可以看到LinkedList实现了Deque，那么Deque又是什么呢？不急咱们慢慢分析。
public interface Deque<E> extends Queue<E> { ... }
由此看出代码中的Deque是Queue的一个子接口，它继承了Queue。我们都知道队列的特性是：先进先出，而Queue中的方法就是体现了这种特性。
public interface Queue<E> extends Collection<E> {
...
// 添加队尾元素
boolean offer(E e);
// 删除对头元素
E poll();
// 获取对头元素
E peek();
...
}
那么我们再从上述几个方法中再来看看LinkedList是如何实现的。
2、LinkedList对Queue的增操作
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 将元素e添加到列表的末尾
*
* @param e 将要添加的元素
* @return 返回true标识添加成功
*/
public boolean offer(E e) {
return add(e);
}
...
}
由上述代码可以看出，在LinkedList中，队列的offer(E e)方法实际上就是调用了LinkedList的#add(E e)方法，而add(E e)方法已经在最前面咱们分析过了，就是在链表的尾部添加一个元素。
3、LinkedList对Queue的删操作
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 删除队列对头的元素
*
* @return 返回对头元素
*/
public E poll() {
// 头结点
final Node<E> f = first;
// 判断头结点是否为null，因为可能还没存入元素
return (f == null) ? null : unlinkFirst(f);
}
/**
* 删除原本的头结点，删除后维护好现有的链表
*/
private E unlinkFirst(Node<E> f) {
// 在前面已做鲁棒性
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // 防止GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
...
}
4、LinkedList对Queue的查操作
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 获取对头的元素
*
* @return 返回对头元素，如果对头为null，则返回null，否则返回队列头部的元素
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
...
}
