SLList：单向链表

链表概述

在本节课中，我们将学习使用基于指针的数据结构来实现 List 接口。这些数据结构由节点组成，每个节点包含列表中的一个元素。通过引用（指针），节点被链接成一个序列。我们首先学习单向链表，它可以在每次操作中以常数时间实现 Stack 和（FIFO）Queue 操作，然后转向双向链表，它可以在常数时间内实现 Deque 操作。

与基于数组的 List 接口实现相比，链表有其优缺点。主要缺点是无法以常数时间通过 get(i) 或 set(i, x) 访问任意元素。相反，我们必须逐个遍历链表，直到到达第 $i$ 个元素。主要优点在于其更高的动态性：给定任意链表节点 u 的引用，我们可以在常数时间内删除 u 或在其相邻位置插入一个新节点，无论 u 在链表中的位置如何。

SLList：单向链表

SLList（单向链表） 是一系列节点的序列。每个节点 u 存储一个数据值 u.x 以及指向序列中下一个节点的引用 u.next。序列中最后一个节点 w 的 w.next = null。

1class Node {
2  T x;
3  Node next;
4}

为了提高效率，SLList 使用变量 head 和 tail 来跟踪序列的第一个和最后一个节点，同时用整数 n 来记录序列的长度：

1Node head;
2Node tail;
3int n;

可视化演示

下图展示了对 SLList 执行一系列 Stack（push(x) 和 pop()）和 Queue（add(x) 和 remove()）操作的过程。

一个 SLList 可以高效地实现 Stack 操作 push() 和 pop()，即在序列头部添加和移除元素。push() 操作只需创建一个新节点 u，其数据值为 x，将 u.next 指向旧的头节点，并将 u 设为新的头节点。最后，由于 SLList 的大小增加了一，因此递增 n：

1T push(T x) {
2  Node u = new Node();
3  u.x = x;
4  u.next = head;
5  head = u;
6  if (n == 0)
7    tail = u;
8  n++;
9  return x;
10}

pop() 操作在检查 SLList 非空后，通过设置 head = head.next 来移除头节点，并递减 n。当删除最后一个元素时会出现特殊情况，此时将 tail 设置为 null：

1T pop() {
2  if (n == 0) return null;
3  T x = head.x;
4  head = head.next;
5  if (--n == 0) tail = null;
6  return x;
7}

显然，push(x) 和 pop() 操作均在 $O(1)$ 时间内完成。

队列操作

SLList 也可以在常数时间内实现先进先出（FIFO）队列操作 add(x) 和 remove()。移除操作从链表头部进行，与 pop() 操作完全相同：

1T remove() {
2  if (n == 0) return null;
3  T x = head.x;
4  head = head.next;
5  if (--n == 0) tail = null;
6  return x;
7}

而添加操作则在链表尾部进行。大多数情况下，通过设置 tail.next = u 实现，其中 u 是包含 x 的新创建节点。但当 n = 0 时存在特殊情况，此时 tail = head = null。在这种情况下，tail 和 head 都被设为 u：

1boolean add(T x) {
2  Node u = new Node();
3  u.x = x;
4  if (n == 0) {
5    head = u;
6  } else {
7    tail.next = u;
8  }
9  tail = u;
10  n++;
11  return true;
12}

显然，add(x) 和 remove() 操作都只需要常数时间。

小结

以下定理总结了 SLList 的性能表现：

定理： SLList 实现了 Stack 和（FIFO）Queue 接口。push(x)、pop()、add(x) 和 remove() 操作每次运行时间均为 $O(1)$。

SLList 几乎实现了完整的 Deque 操作集。唯一缺失的操作是从 SLList 尾部删除元素。从 SLList 尾部删除元素较为困难，因为需要更新 tail 的值，使其指向紧邻 tail 前面的那个节点 w，即满足 w.next = tail 的节点 w。不幸的是，要找到 w 的唯一方法是从 head 开始遍历链表，共需走 $n - 2$ 步。

说明

让我们从 main() 方法的开始解释：

• 第 135 行： 使用 SLList 实现的 Queue 接口创建了一个类型为 Integer 的新 Queue 实例。
• 第 136 至 138 行： 使用 add() 方法将整数 0 到 9 添加到队列中。
• 第 139 行： 打印队列 q 的内容。
• 第 140 至 142 行： 使用 remove() 方法移除队列中的前 5 个整数。
• 第 152 至 154 行： 使用 remove() 方法移除队列中剩余的所有元素，并通过 isEmpty() 方法判断何时停止。