本文已收录，技术和职场问题，请关注公众号【彭旭睿】提问。
前言
大家好，我是小鹏。
在上一篇文章中，我们谈到了基于动态数组的线性列表。 今天我们来讨论一个基于链表的线性表——。
小鹏02交流群已经建立，欢迎加入~
思维导图：
1. 特点 1.1 说说和？的区别？ 遍历速度上：数组是连续的内存空间，基于局部性原则可以更好的命中CPU cache line，而链表是离散的内存空间，对cache line不友好； 在访问速度方面：数组是一个连续的内存空间，支持O(1)时间复杂度的随机访问，而链表需要O(n)时间复杂度来查找元素； 另外和删除操作：如果是在数组的末尾，只需要O(1)的时间复杂度，但是在数组的中间操作需要移动元素，所以需要O(n)的时间复杂度，以及链表本身的删除操作只是修改了引用点，只需要O(1)的时间复杂度（如果考虑到查询被删除节点的时间，复杂度分析还是O(n)，还是比较快的比工程分析中的数组）； 在额外的内存消耗方面：在数组的末尾增加了一个空闲位置java string转list集合，list集合转成数组，在节点中增加了前驱和后继指针。 1.2 多面生活
在数据结构上，它不仅实现了相同的List接口，还实现了Deque接口（继承自Queue接口）。
Deque接口代表了一个双端队列（Ended Queue），它允许在队列的两端进行操作，因此它可以同时实现队列行为和栈行为。
队列接口：
拒绝策略 抛出异常 返回一个特殊值 入队（队尾） add(e)offer(e) 出队（队头） ()poll() 观察（队头） ()peek ()
Queue的API可以分为两类，区别在于方法的拒绝策略：
双端队列接口：
Java并没有提供标准的栈接口（不知为何没有），而是放在Deque接口中：
拒绝策略 抛出异常相当于push(e)(e)出栈 pop()() 观察(栈顶) peek()()
除了标准的队列和堆栈行为外，Deque 接口还提供了 12 个在两端操作的方法：
拒绝策略 抛出异常 返回值增加 (e)/ (e)(e)/ (e) ()/ ()()/ () ()/ ()()/ ()
2.源码分析
本节我们来分析一下主进程的源码。
2.1 属性
属性很容易理解。 如无意外，有小朋友走出来举手提问：
直接回答这个问题。 我的理解是：因为内部类编译后会生成一个独立的Class文件，如果外部类的字段是类型，那么编译器需要调用方法，非字段可以直接访问字段。
我们在分析源码的过程中回答这个问题。
疑惑少了很多，真香（别高兴得太早）。
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable {
// 疑问 1：为什么字段都不声明 private 关键字？
// 疑问 2：为什么字段都声明 transient 关键字？
// 元素个数
transient int size = 0;
// 头指针
transient Node first;
// 尾指针
transient Node last;
// 链表节点
private static class Node {
// 节点数据
// （类型擦除后：Object item;）
E item;
// 前驱指针
Node next;
// 后继指针
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
2.2 施工方法
有2个构造函数：
// 无参构造方法
public LinkedList() {
}
// 带集合的构造方法
public LinkedList(Collection c) {
this();
addAll(c);
}
// 在链表尾部添加集合
public boolean addAll(Collection c) {
// 索引为 size，等于在链表尾部添加
return addAll(size, c);
}
2.3 如何添加
提供了很多方法，都称为一个系列java string转list集合，list集合转成数组，或者内部完成。 如果在链表的中间添加了一个节点，会使用node(index)方法查询指定位置的节点。
其实我们会发现，所有添加的逻辑都可以归纳为6个步骤：
分析添加方法的时间复杂度，区分在链表的两端或中间添加元素：
添加方法
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
// 在尾部添加
linkLast(element);
else
// 在指定位置添加
linkBefore(element, node(index));
}
public boolean addAll(Collection c) {
return addAll(size, c);
}
// 在链表头部添加
private void linkFirst(E e) {
// 1. 找到插入位置的后继节点（first）
final Node f = first;
// 2. 构造新节点
// 3. 将新节点的 prev 指针指向前驱节点（null）
// 4. 将新节点的 next 指针指向后继节点（f）
// 5. 将前驱节点的 next 指针指向新节点（前驱节点是 null，所以没有这个步骤）
final Node newNode = new Node<>(null, e, f);
// 修改 first 指针
first = newNode;
if (f == null)
// f 为 null 说明首个添加的元素，需要修改 last 指针
last = newNode;
else
// 6. 将后继节点的 prev 指针指向新节点
f.prev = newNode;
size++;
modCount++;
}
// 在链表尾部添加
void linkLast(E e) {
final Node l = last;
// 1. 找到插入位置的后继节点（null）
// 2. 构造新节点
// 3. 将新节点的 prev 指针指向前驱节点（l）
// 4. 将新节点的 next 指针指向后继节点（null）
final Node newNode = new Node<>(l, e, null);
// 修改 last 指针
last = newNode;
if (l == null)
// l 为 null 说明首个添加的元素，需要修改 first 指针
first = newNode;
else
// 5. 将前驱节点的 next 指针指向新节点
l.next = newNode;
// 6. 将后继节点的 prev 指针指向新节点（后继节点是 null，所以没有这个步骤）
size++;
modCount++;
}
// 在指定节点前添加
// 1. 找到插入位置的后继节点
void linkBefore(E e, Node succ) {
final Node pred = succ.prev;
// 2. 构造新节点
// 3. 将新节点的 prev 指针指向前驱节点（pred）
// 4. 将新节点的 next 指针指向后继节点（succ）
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
// 5. 将前驱节点的 next 指针指向新节点
pred.next = newNode;
size++;
modCount++;
}
// 在指定位置添加整个集合元素
// index 为 0：在链表头部添加
// index 为 size：在链表尾部添加
public boolean addAll(int index, Collection c) {
checkPositionIndex(index);
// 事实上，c.toArray() 的实际类型不一定是 Object[]，有可能是 String[] 等
// 不过，我们是通过 Node中的item 承接的，所以不用担心 ArrayList 中的 ArrayStoreException 问题
Object[] a = c.toArray();
// 添加的数组为空，跳过
int numNew = a.length;
if (numNew == 0)
return false;
// 1. 找到插入位置的后继节点
// pred：插入位置的前驱节点
// succ：插入位置的后继节点
Node pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
// 找到 index 位置原本的节点，插入后变成后继节点
succ = node(index);
pred = succ.prev;
}
// 插入集合元素
for (Object o : a) {
E e = (E) o;
// 2. 构造新节点
// 3. 将新节点的 prev 指针指向前驱节点
Node newNode = new Node<>(pred, e, null);
if (pred == null)
// pred 为 null 说明是在头部插入，需要修改 first 指针
first = newNode;
else
// 5. 将前驱节点的 next 指针指向新节点
pred.next = newNode;
// 修改前驱指针
pred = newNode;
}
if (succ == null) {
// succ 为 null 说明是在尾部插入，需要修改 last 指针
last = pred;
} else {
// 4. 将新节点的 next 指针指向后继节点
pred.next = succ;
// 6. 将后继节点的 prev 指针指向新节点
succ.prev = pred;
}
// 数量增加 numNew
size += numNew;
modCount++;
return true;
}
// 将 LinkedList 转化为 Object 数组
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
在链表中间添加节点时，会使用node(index)方法查询指定位置的节点。 可以看出，维护首尾节点的作用又发挥出来了：
虽然，从复杂度分析的角度来看，向哪个方向查询没有区别，时间复杂度都是O(n)。 但从工程分析的角度来看，还是有区别的。 从靠近目标节点的位置开始查询，实际执行时间会更短。
查询指定位置节点
// 寻找指定位置的节点，时间复杂度：O(n)
Node node(int index) {
if (index < (size >> 1)) {
// 如果索引位置小于 size/2，则从头节点开始找
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果索引位置大于 size/2，则从尾节点开始找
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
方法其实就是add方法的逆操作，这里不再赘述。
// 删除头部元素
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 删除尾部元素
public E removeLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// 删除指定元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
2.4 的迭代器
Java 是句法糖，本质上就是它采用的方式。 由于它是双向的，因此只提供了 1 个迭代器：
与其他容器类一样，它的迭代器中有一个快速失败机制。 如果在迭代过程中发现有变化，就说明数据被修改了，会提前抛出异常（当然不一定是被其他线程修改了）。
public ListIterator listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
// 非静态内部类
private class ListItr implements ListIterator {
private Node lastReturned;
private Node next;
private int nextIndex;
// 创建迭代器时会记录外部类的 modCount
private int expectedModCount = modCount;
ListItr(int index) {
next = (index == size) ? null : node(index);
nextIndex = index;
}
public E next() {
// 更新 expectedModCount
checkForComodification();
...
}
...
}
2.5 序列化过程
重写了JDK序列化的逻辑，不再对链表节点进行序列化，只对链表节点中的有效数据进行序列化，从而减小序列化后产品的体积。 反序列化时，只需要将对象添加到链表的末尾即可恢复链表的顺序。
// 序列化和反序列化只考虑有效数据
// 序列化过程
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// 写入链表长度
s.writeInt(size);
// 写入节点上的有效数据
for (Node x = first; x != null; x = x.next)
s.writeObject(x.item);
}
// 反序列化过程
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// 读取链表长度
int size = s.readInt();
// 读取有效元素并用 linkLast 添加到链表尾部
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
2.6 clone()过程
中的第一个和最后一个指针是引用类型，所以需要在clone()中实现深拷贝。 否则，两个对象克隆后会相互影响：
private LinkedList superClone() {
try {
return (LinkedList) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
public Object clone() {
LinkedList clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// 将原链表中的数据依次添加到新立案表中
for (Node x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
2.7 如何实现线程安全？
有5种方式：
三、总结
在上一篇文章中，我们提到了List的数组实现，不仅是List的链表实现，还有Queue和Stack的链表实现。 那么，Java中Queue和Stack的数组实现是怎样的呢？ 我们将在下一篇文章中讨论，敬请关注。
评论列表
发表评论: