概述
相较于 ArrayList，LinkedList 在平时使用少一些。
LinkedList 内部是一个双向链表，并且实现了 List 接口和 Deque 接口，因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如下：
它除了作为List使用，还可以作为队列或者栈来使用。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable从源码可以看出，LinkedList实现了Cloneable和Serializable接口，说明其可以被克隆，也可以被序列化！同样的，LinkedList被克隆的时候，和ArrayList一样二者均是浅拷贝。实现了Deque接口，说明支持两端的元素插入和移除；继承了AbstractSequentialList类，说明支持按次序访问！
LinkedList 的继承结构如下：
代码分析
结点类 Node
查看 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;
}
}LinkedList 是双向链表的实现，而该 Node 类则是链表的结点。
此外，LinkedList 还有几个成员变量如下：
// list 的长度
transient int size = 0;
// 链表头结点
transient Node<E> first;
// 链表尾结点
transient Node<E> last;构造器
LinkedList 有两个构造器，如下：
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}PS: 由于链表的容量可以一直增加，因此没有指定容量的构造器。
其中第一个为无参构造器；第二个为使用指定的集合构造，并调用 addAll()，继续跟进该方法，代码如下：
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//检查索引是否正确（0<=index<=size）
checkPositionIndex(index);
//得到元素数组
Object[] a = c.toArray();
//得到元素个数
int numNew = a.length;
//若没有元素要添加，直接返回false
if (numNew == 0)
return false;
//succ指向当前需要插入节点的位置，pred指向其前一个节点
Node<E> pred, succ;
//如果是在末尾开始添加，当前节点后一个节点初始化为null，前一个节点为尾节点
if (index == size) {
succ = null;
pred = last;
} else { //如果不是从末尾开始添加，当前位置的节点为指定位置的节点，前一个节点为要添加的节点的前一个节点
succ = node(index);
pred = succ.prev;
}
//遍历数组并添加到列表中
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//将元素值e，前继节点pred“封装”为一个新节点newNode
Node<E> newNode = new Node<>(pred, e, null);
//如果原链表为null，则新插入的节点作为链表首节点
if (pred == null)
first = newNode;
else
pred.next = newNode; //如果存在前节点，前节点会向后指向新加的节点
pred = newNode; //pred指针向后移动，指向下一个需插入节点位置的前一个节点
}
//如果是从最后开始添加的，则最后添加的节点成为尾节点
if (succ == null) {
last = pred;
} else {
pred.next = succ; //如果不是从最后开始添加的，则最后添加的节点向后指向之前得到的后续第一个节点
succ.prev = pred; //当前，后续的第一个节点也应改为向前指向最后一个添加的节点
}
size += numNew;
modCount++;
return true;
}校验index是否越界，当然这里肯定是不会越界的，代码如下：
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}因为是双向链表，查找元素只能从头或尾结点开始遍历，采用就近原则，如果 index < (size >> 1) 也就是小于元素的个数的一半，从头结点遍历，反之从尾结点遍历，返回index索引结点对象。List 接口 get、set 方法都会涉及 node 方法的调用。
Node<E> node(int index) {
// assert isElementIndex(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;
}
}void linkFirst(E e)
头结点插入元素，涉及方法 addFirst、offerFirst、push(入栈)
private void linkFirst(E e) {
//获取当前首结点引用
final Node<E> f = first;
//构建一个prev值为null,节点值为e,next值为f的新节点newNode
final Node<E> newNode = new Node<>(null, e, f);
//将newNode作为首节点
first = newNode;
//如果原首节点为null，即原链表为null，则链表尾节点也设置为newNode
if (f == null)
last = newNode;
else //否则，原首节点的prev设置为newNode
f.prev = newNode;
size++; //长度+1
modCount++; //修改次数+1
}void linkLast(E e)
尾结点插入元素，涉及方法 addLast、offerLast、add、offer
void linkLast(E e) {
// 获取当前尾结点引用
final Node<E> l = last;
//构建一个prev值为l,节点值为e,next值为null的新节点newNode
final Node<E> newNode = new Node<>(l, e, null);
//将newNode作为尾节点
last = newNode;
//如果原尾节点为null，即原链表为null，则链表首节点也设置为newNode
if (l == null)
first = newNode;
else //否则，原尾节点的next设置为newNode
l.next = newNode;
size++;
modCount++;
}E unlinkFirst(Node<E> f)
头结点删除元素，涉及方法 removeFirst、poll、remove、pollFirst、pop(出栈)
private E unlinkFirst(Node<E> f) {
// 获取首结点存储的元素
final E element = f.item;
// 获取首结点的后继结点
final Node<E> next = f.next;
// 删除首结点
f.item = null;
f.next = null; //便于垃圾回收期清理
// 原来首结点的后继结点设为首结点
first = next;
// 如果原来首结点的后继结点为空，则尾结点设为null
// 否则，原来首结点的后继结点的前驱结点设为null
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
// 返回原来首结点存储的元素
return element;
}E unlinkLast(Node<E> l)
尾结点删除元素，涉及方法 removeLast、pollLast
private E unlinkLast(Node<E> l) {
// 获取尾结点存储的元素
final E element = l.item;
// 获取尾结点的前驱结点
final Node<E> prev = l.prev;
// 删除尾结点
l.item = null;
l.prev = null; // help GC
// 原来尾结点的前驱结点设为尾结点
last = prev;
// 如果原来尾结点的前驱结点为空，则首结点设为null
// 否则，原来尾结点的前驱结点的后继结点设为null
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
// 返回原来尾结点存储的元素
return element;
}Deque - E peek()
获取头结点元素，同 peekFirst 方法
public E peek() {
final Node<E> f = first;
// 如果首结点为空，则返回null
// 否则，返回首结点存储的元素
return (f == null) ? null : f.item;
}Deque - E peekLast()
获取尾结点元素
public E peekLast() {
// 获取尾结点引用
final Node<E> l = last;
// 如果尾结点为空，则返回null
// 否则，返回尾结点存储的元素
return (l == null) ? null : l.item;
}Deque - E element()
获取头结点元素 - null 抛 NoSuchElementException 异常
public E element() {
// 返回首结点存储的元素
return getFirst();
}
public E getFirst() {
// 获取首结点引用
final Node<E> f = first;
// 如果首结点为空，则抛出无该元素异常
if (f == null)
throw new NoSuchElementException();
// 返回首结点存储的元素
return f.item;
}Deque - boolean removeFirstOccurrence(Object o)
从头结点开始删除首次出现的指定元素
public boolean removeFirstOccurrence(Object o) {
// 删除顺序下首次出现的指定元素对应的结点，返回操作结果
return remove(o);
}
public boolean remove(Object o) {
//会根据是否为null分开处理。若值不是null，会用到对象的equals()方法
if (o == null) {
// 遍历链表，查找到指定元素后删除该结点，返回true
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;
}E unlink(Node<E> x)
E unlink(Node<E> x) {
// 获取指定非空结点存储的元素
final E element = x.item;
// 获取指定非空结点的后继结点
final Node<E> next = x.next;
// 获取指定非空结点的前驱结点
final Node<E> prev = x.prev;
/**
* 如果指定非空结点的前驱结点为空，则指定非空结点的后继结点设为首结点
* 否则，指定非空结点的后继结点设为指定非空结点的前驱结点的后继结点，
* 指定非空结点的前驱结点设为null
*/
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
/**
* 如果指定非空结点的后继结点为空，则指定非空结点的前驱结点设为尾结点
* 否则，指定非空结点的前驱结点设为指定非空结点的后继结点的前驱结点，
* 指定非空结点的后继结点设为null
*/
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 指定非空结点存储的元素设为null
x.item = null;
size--;
modCount++;
// 返回指定非空结点存储的元素
return element;
}boolean removeLastOccurrence(Object o)
从尾结点开始删除首次出现的指定元素
public boolean removeLastOccurrence(Object o) {
//由于LinkedList中允许存放null，因此下面通过两种情况来分别处理
if (o == null) {
// 遍历链表，从尾结点开始查找指定元素
// 如果查找成功，删除该结点，返回true
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
// 查找失败
return false;
}线程安全性
首先，LinkedList 是线程不安全的。通过内部类 ListItr 迭代器的实现，在调用 next、remove 方法时都会调用 checkForComodification 方法，校验结构是否发生过变更，若有则抛出 ConcurrentModificationException 异常。
总结
- LinkedList 内部是「双向链表」，同时实现了 List 接口和 Deque 接口，因此也具备 List、双端队列和栈的性质
- 线程不安全
参考文章：
- https://zhuanlan.zhihu.com/p/104150589