SLList：单向链表

链表概述

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

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

SLList：单向链表

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

1class Node {
2 public:
3   T x;
4   Node *next;
5   Node(T x0) {
6     x = x0;
7     next = nullptr;
8   }
9};

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

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

可视化演示

下图展示了对 SLList 执行的一系列 Stack 和 Queue 操作。其中包括对 SLList 执行的 Queue（add(x) 和 remove()）以及 Stack（push(x) 和 pop()）操作。

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

1void push(T x) {
2    Node<T>* u = new Node<T>(x);
3    u->next = head;
4    head = u;
5    if (n == 0) {
6        tail = u;
7    }
8    n++;
9}

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

1T pop() {
2    if (n == 0) {
3        return 0;
4    }
5    T x = head->x;
6    Node<T>* u = head;
7    head = head->next;
8    delete u;
9    if (--n == 0) {
10        tail = nullptr;
11    }
12    return x;
13}

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

队列操作

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

1T remove() {
2    if (n == 0) {
3        return -1;
4    }
5    T x = head->x;
6    Node<T>* u = head;
7    head = head->next;
8    delete u;
9    if (--n == 0) {
10        tail = nullptr;
11    }
12    return x;
13}

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

1void add(T x) {
2    Node<T>* u = new Node<T>(x);
3
4    if (n == 0) {
5        head = u;
6    } else {
7        tail->next = u;
8    }
9    tail = u;
10    n++;
11}

显然，add(x) 和 remove() 操作都花费常数时间。

总结

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

定理： SLList 实现了 Stack 和（先进先出）Queue 接口。push(x)、pop()、add(x) 和 remove() 每次操作均在 $O(1)$ 时间内完成。

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

1#include <iostream>
2
3using namespace std;
4
5// 定义模板类 Node
6template <typename T>
7class Node {
8public:
9    T x;
10    Node<T>* next;
11
12    Node(T x0) {
13        x = x0;
14        next = nullptr;
15    }
16};
17
18// 定义模板类 LinkedList
19template <typename T>
20class LinkedList {
21public:
22    Node<T>* head;
23    Node<T>* tail;
24    int n;
25
26    LinkedList() {
27        head = nullptr;
28        tail = nullptr;
29        n = 0;
30    }
31
32    // 将新元素推入列表前端
33    void push(T x) {
34        Node<T>* u = new Node<T>(x);
35        u->next = head;
36        head = u;
37        if (n == 0) {
38            tail = u;
39        }
40        n++;
41    }
42
43    // 弹出列表前端的第一个元素
44    T pop() {
45        if (n == 0) {
46            return 0;
47        }
48        T x = head->x;
49        Node<T>* u = head;
50        head = head->next;
51        delete u;
52        if (--n == 0) {
53            tail = nullptr;
54        }
55        return x;
56    }
57
58    // 移除列表第一个元素并返回其值
59    T remove() {
60        if (n == 0) {
61            return -1;
62        }
63        T x = head->x;
64        Node<T>* u = head;
65        head = head->next;
66        delete u;
67        if (--n == 0) {
68            tail = nullptr;
69        }
70        return x;
71    }
72
73    // 将新元素添加到列表末尾
74    void add(T x) {
75        Node<T>* u = new Node<T>(x);
76
77        if (n == 0) {
78            head = u;
79        } else {
80            tail->next = u;
81        }
82        tail = u;
83        n++;
84    }
85};
86
87int main() {
88    // 创建一个存储整数的 LinkedList 对象
89    LinkedList<int> list;
90    cout << "原始列表包含: ";
91    
92    // 将一些值推入列表前端
93    list.push(3);
94    list.push(5);
95    list.push(7);
96
97    // 打印列表中的值
98    Node<int>* current = list.head;
99    while (current != nullptr) {
100        cout << current->x << " ";
101        current = current->next;
102    }
103    cout << endl;
104
105    // 从列表中弹出一些值
106    int x = list.pop();
107    cout << "弹出的值: " << x << endl;
108    x = list.pop();
109    cout << "弹出的值: " << x << endl;
110    cout << "弹出操作后: ";
111    
112    // 打印列表中剩余的值
113    current = list.head;
114    while (current != nullptr) {
115        cout << current->x << " ";
116        current = current->next;
117    }
118    cout << endl;
119
120    // 向列表中添加一些值
121    list.add(5);
122    list.add(10);
123    list.add(15);
124
125    // 从列表中移除一个值
126    int removed = list.remove();
127    cout << "移除的值: " << removed << endl;
128
129    return 0;
130}

解释

让我们从 main() 函数开始解释：

• 第 87 行： 创建了一个存储整数的 LinkedList 类实例。

• 第 90–92 行： 使用 push() 方法将三个值（3、5 和 7）添加到链表前端。

• 第 95–98 行： 通过 while 循环遍历链表，打印出每个节点的 x 成员变量的值。current 最初指向链表头，循环持续打印每个节点的值，直到 current 到达链表末尾。

• 第 103–106 行： 使用 pop() 方法从链表前端移除两个值，该方法会移除并返回头节点的值。

• 第 117–119 行： 使用 add() 方法将三个值（5、10 和 15）添加到链表末尾。

• 第 122–123 行： 使用 remove() 方法移除链表第一个节点，该方法会移除并返回头节点的值。