1.数据结构
LinkedList底层数据结构是一个双向链表，整体结构如上图所示，链表中的每个节点都可以向前或者向后追溯。
源码
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;
}
}源码解析
- 链表的每个节点都被称为Node，Node有prev和next属性，分别代表前一个节点和后一个节点的位置。
- first是双向链表的头节点，它的前一个节点是null，last是双向链表的尾节点，它的后一个节点也是null。
- 当链表中没有数据时，first和last是同一个节点，前后指向都是null。
- 因为是个双向链表，只要机器内存足够强大，是没有大小限制的。
2.新增
新增节点时，可以选择追加到链表头部或追加到链表尾部，add方法默认是从尾部开始追加，addFirst方法是从头部开始追加，具体源码如下。
源码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
//从尾部开始追加节点
void linkLast(E e) {
//尾节点赋值给临时变量
final Node<E> l = last;
//新建节点，l是新节点的前一个节点，e表示当前新节点，null表示当前新节点的后一个节点
final Node<E> newNode = new Node<>(l, e, null);
//将新节点追加到尾部
last = newNode;
//如果链表为空(l和尾节点相等，尾节点为空，链表即为空)，头部和尾部是同一个节点且都是新建的节点
if (l == null)
first = newNode;
//否则把前一个节点的下一个节点指向当前节点
else
l.next = newNode;
//修改链表大小和版本
size++;
modCount++;
}
//从头部追加
private void linkFirst(E e) {
//头节点赋值给临时变量
final Node<E> f = first;
//新建节点，null表示前一个节点，e表示当前新节点，f表示新节点的下一个节点，目前值是头节点的值
final Node<E> newNode = new Node<>(null, e, f);
//将新节点追加到头部
first = newNode;
//如果链表为空(f和头节点相等，头节点为空，链表即为空)，头部和尾部是同一个节点且都是新建的节点
if (f == null)
last = newNode;
//否则把下一个节点的前一节点指向当前尾节点
else
f.prev = newNode;
//修改链表大小和版本
size++;
modCount++;
}
}源码解析
从源码可以看出头尾部追加节点的方式都比较简单，只需修改指向位置即可，只是前者是移动头节点的prev指向，后者是移动尾节点的next指向。
3.查询
链表查询某一个节点是比较慢的，需要挨个循环查找 ，具体源码如下。
源码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
//根据链表索引位置查询节点
Node<E> node(int index) {
//如果index处于队列的前半部分，从头开始找，size >> 1是size除以2的意思
if (index < (size >> 1)) {
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;
}
}
}源码解析
从源码中可以发现，LinkedList并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看index是在链表的前半部分还是后半部分。如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数至少降低了一半，提高了查找的效率，这种思想值得借鉴。
4.迭代器
Iterator接口满足不了LinkedList要实现双向迭代访问的需求(Iterator只支持从头到尾的访问)，因此Java新增了一个迭代接口ListIterator，这个接口提供了向前和向后的迭代方法，如hasPrevious、previous、previousIndex、hasNext、next和nextIndex，其中hasNext、next和remove的源码如下。
源码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
//判断是否有下一个元素
public boolean hasNext() {
//下一个节点的索引小于链表的大小，就存在下一个元素
return nextIndex < size;
}
//取下一个元素
public E next() {
//检查期望版本号是否发生变化
checkForComodification();
//再次检查
if (!hasNext())
throw new NoSuchElementException();
//next是当前节点，在上一次执行next()方法时被赋值
lastReturned = next;
//next是下一个节点了，为下次迭代做准备
next = next.next;
nextIndex++;
return lastReturned.item;
}
public void remove() {
checkForComodification();
//lastReturned是本次迭代需要删除的值，分空和非空两种情况
//lastReturned为空，说明调用者没有主动执行过next()或者previos()，直接报错
//lastReturned不为空，是在上次执行next()或者previos()方法时赋的值
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
//删除当前节点
unlink(lastReturned);
/**
* next == lastReturned的场景分析
* 从尾到头递归执行，第一次迭代并且要删除最后一个元素的情况下，previous()方法里面设置了lastReturned = next = last，所以next和lastReturned会相等
*/
if (next == lastReturned)
//这时候lastReturned是尾节点，lastNext是null，所以next也是null，这样在previous()执行时，发现next是null，就会把尾节点赋值给next
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
}5.删除
节点删除的方式和追加类似，可以选择从头部删除，也可以选择从尾部删除，删除操作会把节点的值，前后指向节点都置为null，最后由GC进行回收。
源码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
//头部删除
//f是链表头节点
private E unlinkFirst(Node<E> f) {
//取出头节点的值作为方法的返回值
final E element = f.item;
//取出头节点的下一个节点
final Node<E> next = f.next;
//帮助GC回收头节点
f.item = null;
f.next = null;
//将头节点的下一个节点设置为头节点
first = next;
//如果next为空，表明链表为空
if (next == null)
last = null;
//链表不为空，将头节点的前一个节点指向null
else
next.prev = null;
//修改链表大小和版本
size--;
modCount++;
return element;
}
}源码解析
- 从源码中可以看出链表结构的节点删除操作也比较简单，仅仅把前后节点的指向做一下修改即可。因此LinkedList的新增和删除操作速度是比较快的。
- 尾部删除节点代码同头部删除节点代码类似。