共计 5302 个字符，预计需要花费 14 分钟才能阅读完成。
如果本文中有不正确的地方请指出
由于没有留言可以在公众号添加我的好友共同讨论。
1. 介绍
LinkedList 是线程不安全的，允许元素为 null 的双向链表。
2. 继承结构
我们来看一下 LinkedList 的继承结构图：
代码实现:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable- Cloneable 实现克隆
- Serializable 序列化
- List 定义了一些集合类的方法
- Deque 双向队列接口(就是两端都可以进行增加删除操作)
注意一点 LinkedList 并没有实现 RandomAccess 所以随机访问是非常慢的。
3. 属性
元素个数
transient int size = 0;指向第一个节点的指针(注释直接就写着)
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;指向最后一个节点的指针
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;transient 关键字的作用是保持变量不被序列化具体的百度。
不过我们注意到 LinkedList 是有 Node 类，这里的 Node 是一个内部类：
- item 存储的元素
- next 指向后置节点
- prev 指向前置节点
- 内部类同时包含了一个构造函数
其实 LinkedList 集合就是由许多个 Node 对象 y 一个连着一个组成手构成，可以看下方的图
可以看上面的四个元素，分别就是四个 Node 对象，可以看到 node1 所指向的 prev 上一个节点是空也就是没有上节点,node4 所指向的 next 节点为空也就是没有下一个节点。
4. 构造方法
LinkedList 共有两个构造方法，一个是创建一个空的构造函数，一个是将已有的 Collection 添加到 LinkedList 中。
因为 LinkedList 不同于 ArrayList 所以初始化不需要指定大小取分配内存空间。
5. 添加元素
LinkedList 有几种添加方法我们先从 add()开始。
5.1 add 方法
checkPositionIndex(index);可以看到在调用 Add 方法首先校验一下索引是否合法，如果不合法就会抛出异常。
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));然后如果索引值等于 size 的值则直接调用 linkLast 插入到尾部节点。
否则就 linkBefore 方法。
linkLast 方法：
void linkLast(E e) {
// 将 l 设为尾节点
final Node<E> l = last;
// 构造一个新节点，节点上一个节点引用指向尾节点 l
final Node<E> newNode = new Node<>(l, e, null);
// 将尾节点设为创建的新节点
last = newNode;
// 如果尾节点为空，表示原先链表为空
if (l == null)
// 将头节点设为新创建的节点（尾节点也是新创建的节点）first = newNode;
else
// 将原来尾节点下一个节点的引用指向新节点
l.next = newNode;
size++;// 节点数加 1
modCount++;
}注意一下这里出现了 modCount 方法，和 ArrayList 中一样，iterator 和 listIterator 方法返回的迭代器和列表迭代器实现使用。
linkBefore:
void linkBefore(E e, Node<E> succ) {
// 将 pred 设为插入节点的上一个节点
final Node<E> pred = succ.prev;
// 将新节点的上引用设为 pred, 下引用设为 succ
final Node<E> newNode = new Node<>(pred, e, succ);
//succ 的上一个节点的引用设为新节点
succ.prev = newNode;
// 如果插入节点的上一个节点引用为空
if (pred == null)
// 新节点就是头节点
first = newNode;
else
// 插入节点的下一个节点引用设为新节点
pred.next = newNode;
size++;
// 同上
modCount++;
}5.2 addAll()
在 LinkedList 中有两个 addAll 方法一个是 addAll(Collection<? extends E> c)一个是 addAll(int index, Collection<? extends E> c), 其实
addAll(Collection<? extends E> c)=addAll(int index, Collection<? extends E> c)
可以看下面的截图:
源码如下：
现在开始分析源码：
首先我们可以看到先调用了 checkPositionIndex(index); 方法来检查索引是否合法。
然后将传进来的 Collection 转成 Object 数组
Object[] a = c.toArray();如果集合为空就直接返回 false
if (numNew == 0)
return false;如果插入的位置等于链表的长度就把新增加的元素放在尾部。
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {succ = node(index);
pred = succ.prev;
}最后在循环要插入的元素。这里我们可以看到上面也有 modCount。
5.3 addFirst()
addFirst 是将元素插入到 LinkedList 的头部。
如果现在的机构是下图的：
addFirst 执行的操作就是：
红色是使用 addFirst 插入后的位置。一下是源码
调用了 linkFirst 方法。
上面的操作时：
- 首先执行 final Node<E> f = first; 将头节点赋值给 f
- final Node<E> newNode = new Node<>(null, e, f); 将指定元素构造成一个新节点，此节点的指向下一个节点的引用为头节点
// 将新节点设为头节点，那么原先的头节点 f 变为第二个节点
first = newNode;
// 如果第二个节点为空，也就是原先链表是空
if (f == null)
// 将这个新节点也设为尾节点（前面已经设为头节点了）last = newNode;
else
f.prev = newNode;// 将原先的头节点的上一个节点指向新节点
size++;// 节点数加 1
modCount++;// 和 ArrayList 中一样记录修改次数5.4 addLast 方法
addLast 是将元素插入到尾部如图(黄色元素)：
黄色 node 是新增加。注意 add 也是把元素添加到尾部。我们来看一下源码：
这里看到 addLast 和 add 是调用的同一方法，这里就不在讲解。可以看上方的代码。
由于文章比较长分为两次更新。下一篇文章继续分析
上次分析了 LinkedList 的结构和添加方法这次开始分析下面的。
注意源码版本为 JDK1.8
直接进入正题。
1. 删除
1.2remove()
在 LinkedList 中 remove()和 removeFirst()是相同的
在 LinkedList 中的删除其实就是通过修改上一个节点和指向下一个节点的引用完成的, 可以看下面的图片：
我们可以看到把 node6 的 prev 指向清空然后把 node3 的 next 设置成空就完成了删除的操作。
看一下 JDK 的源码实现：
调用 removeFirst, 在调用 removeFirst 中先获取头部节点，如果头节点为空就抛异常。
调用 unlinkFirst
private E unlinkFirst(Node<E> f) {
final E element = f.item;
//next 为头结点的下一个节点
final Node<E> next = f.next;
f.item = null;
// 将节点的元素以及引用都设为 null，便于垃圾回收
f.next = null;
// 修改头结点为第二个节点
first = next;
// 如果第二个节点为空（当前链表只存在第一个元素）if (next == null)
// 那么尾节点也置为 null
last = null;
else
// 如果第二个节点不为空，那么将第二个节点的上一个引用置为 null
next.prev = null;
size--;
modCount++;
return element;
} 1.3 removeLast()
我们看一下 removeLast，从列表中删除最后一个元素
首先看到先获取了 last 最后一个元素，如果为空然后就抛异常
然后调用了 unlinkLast
看到 unlinkLast 方法中有一个 help gc , 它的主要作用就是帮助 GC 来做垃圾回收。
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;
// 帮助 GC 垃圾回收
l.prev = null;
// 尾节点为倒数第二个节点
last = prev;
// 如果倒数第二个节点为 null
if (prev == null)
// 那么将节点也置为 null
first = null;
else
prev.next = null;
// 如果倒数第二个节点不为空，那么将倒数第二个节点的下一个引用置为 null
size--;
modCount++;
return element;
}同样执行了 modCount++
1.3 remove(int index)
根据索引来删除元素
// 删除此列表中指定位置的元素
public E remove(int index) {
// 判断索引 index >= 0 && index <= size 中时抛出 IndexOutOfBoundsException 异常
checkElementIndex(index);
return unlink(node(index));
}
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) {// 如果删除节点位置的上一个节点引用为 null（表示删除第一个元素）first = next;// 将头结点置为第一个元素的下一个节点
} else {// 如果删除节点位置的上一个节点引用不为 null
prev.next = next;// 将删除节点的上一个节点的下一个节点引用指向删除节点的下一个节点（去掉删除节点）x.prev = null;// 删除节点的上一个节点引用置为 null
}
if (next == null) {// 如果删除节点的下一个节点引用为 null（表示删除最后一个节点）last = prev;// 将尾节点置为删除节点的上一个节点
} else {// 不是删除尾节点
next.prev = prev;// 将删除节点的下一个节点的上一个节点的引用指向删除节点的上一个节点
x.next = null;// 将删除节点的下一个节点引用置为 null
}
// 删除节点内容置为 null，便于垃圾回收
x.item = null;
size--;
modCount++;
return element;
}3.set(int index, E element)
简单粗暴直接贴代码
public E set(int index, E element) {
// 检查索引是否合法否则 IndexOutOfBoundsException 异常
checkElementIndex(index);
// 获取指定索引的元素
Node<E> x = node(index);
E oldVal = x.item;
// 将指定索引的元素替换成新的元素
x.item = element;
/ 返回指定索引位置原来的元素
return oldVal;/
}4. 查找元素
很简单
4.1 getFirst()
返回第一个元素
public E getFirst() {
获取头
final Node<E> f = first;
判断是否为空
if (f == null)
throw new NoSuchElementException();
元素返回
return f.item;
}4.2 getLast()
返回最后一个元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}4.3 get
返回指定索引元素
public E get(int index) {checkElementIndex(index);
return node(index).item;
}暂时就这么多
原创不易, 如果你喜欢本文或者对你有帮助就请转发