SLList：单向链表

链表概述

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

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

SLList：单向链表

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

1class SLList(BaseList):
2    
3    class Node(object):
4        def __init__(self, x):
5            self.x = x
6            self.next = None
7
8    def __init__(self, iterable=[]):
9        self._initialize()
10        self.add_all(iterable)

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

1class SLList(BaseList):
2    
3    class Node(object):
4        def __init__(self, x):
5            self.x = x
6            self.next = None
7
8    def __init__(self, iterable=[]):
9        self._initialize()
10        self.add_all(iterable)
11        
12    def _initialize(self):
13        self.n = 0
14        self.head = None
15        self.tail = None

可视化演示

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

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

1class SLList(BaseList):
2    
3    class Node(object):
4        def __init__(self, x):
5            self.x = x
6            self.next = None
7
8    def __init__(self, iterable=[]):
9        self._initialize()
10        self.add_all(iterable)
11        
12    def _initialize(self):
13        self.n = 0
14        self.head = None
15        self.tail = None
16
17    def push(self, x):
18        u = self.new_node(x)
19        u.next = self.head
20        self.head = u
21        if self.n == 0:
22            self.tail = u
23        self.n += 1
24        return x

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

1class SLList(BaseList):
2    
3    class Node(object):
4        def __init__(self, x):
5            self.x = x
6            self.next = None
7
8    def __init__(self, iterable=[]):
9        self._initialize()
10        self.add_all(iterable)
11        
12    def _initialize(self):
13        self.n = 0
14        self.head = None
15        self.tail = None
16    
17    def pop(self):
18        if self.n == 0: return None
19        x = self.head.x
20        self.head = self.head.next
21        self.n -= 1
22        if self.n == 0:
23            self.tail = None
24        return x

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

队列操作

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

1class SLList(BaseList):
2    
3    class Node(object):
4        def __init__(self, x):
5            self.x = x
6            self.next = None
7
8    def __init__(self, iterable=[]):
9        self._initialize()
10        self.add_all(iterable)
11        
12    def _initialize(self):
13        self.n = 0
14        self.head = None
15        self.tail = None
16
17    def remove(self, i):
18        if i < 0 or i > self.n-1: raise IndexError()
19        if i == 0: return self.pop()
20        u = self.head
21        for _ in range(i-1):
22            u = u.next
23        w = u.next
24        u.next = u.next.next
25        self.n -= 1
26        return w.x

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

1class SLList(BaseList):
2    
3    class Node(object):
4        def __init__(self, x):
5            self.x = x
6            self.next = None
7
8    def __init__(self, iterable=[]):
9        self._initialize()
10        self.add_all(iterable)
11        
12    def _initialize(self):
13        self.n = 0
14        self.head = None
15        self.tail = None
16
17    def add(self, i, x):
18        if i < 0 or i > self.n: raise IndexError()
19        if i == 0: self.push(x); return True
20        u = self.head
21        for _ in range(i-1):
22            u = u.next
23        w = self.new_node(x)
24        w.next = u.next
25        u.next = w
26        self.n += 1
27        return True

显然，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 开始遍历 SLList，共需 $n - 2$ 步。

1from base import BaseList
2
3class SLList(BaseList):    
4    class Node(object):
5        def __init__(self, x):
6            self.x = x
7            self.next = None
8
9    def __init__(self, iterable=[]):
10        self._initialize()
11        self.add_all(iterable)
12    # 初始化函数
13    def _initialize(self):
14        self.n = 0
15        self.head = None
16        self.tail = None
17    # 创建新节点
18    def new_node(self, x):
19        return SLList.Node(x)
20    # 添加值的函数
21    def _add(self, x):
22        u = self.new_node(x)
23        if self.n == 0:
24            self.head = u
25        else:
26            self.tail.next = u
27        self.tail = u
28        self.n += 1
29        return True
30    # 将值压入链表的函数
31    def push(self, x):
32        u = self.new_node(x)
33        u.next = self.head
34        self.head = u
35        if self.n == 0:
36            self.tail = u
37        self.n += 1
38        return x
39    # 在链表末尾追加值的函数
40    def append(self, x):
41        u = self.new_node(x)
42        if self.n == 0:
43            self.head = u
44        else:
45            self.tail.next = u
46        self.tail = u
47        self.n += 1
48        return True
49    # 获取指定索引节点的函数
50    def get_node(self, i):
51        u = self.head
52        for _ in range(i):
53            u = u.next
54        return u
55    # 获取节点值的函数
56    def get(self, i):
57        if i < 0 or i > self.n-1: raise IndexError()
58        return self.get_node(i).x
59    # 设置节点值的函数
60    def set(self, i, x):
61        if i < 0 or i > self.n-1: raise IndexError()
62        u = self.get_node(i)
63        y, u.x = u.x, x
64        return y
65    # 使用 push() 添加值的函数
66    def add(self, i, x):
67        if i < 0 or i > self.n: raise IndexError()
68        if i == 0: self.push(x); return True
69        u = self.head
70        for _ in range(i-1):
71            u = u.next
72        w = self.new_node(x)
73        w.next = u.next
74        u.next = w
75        self.n += 1
76        return True
77    # 删除值的函数
78    def remove(self, i):
79        if i < 0 or i > self.n-1: raise IndexError()
80        if i == 0: return self.pop()
81        u = self.head
82        for _ in range(i-1):
83            u = u.next
84        w = u.next
85        u.next = u.next.next
86        self.n -= 1
87        return w.x
88    # 弹出值的函数
89    def pop(self):
90        if self.n == 0: return None
91        x = self.head.x
92        self.head = self.head.next
93        self.n -= 1
94        if self.n == 0:
95            self.tail = None
96        return x
97    # 使用 pop() 删除的函数
98    def _remove(self):
99        return self.pop()
100    # 字符串转换
101    def __str__(self):
102        s = "["
103        u = self.head
104        while u is not None:
105            s += "%r" % u.x
106            u = u.next
107            if u is not None:
108                s += ","
109        return s + "]"
110    # 使用 size() 获取长度的函数
111    def __len__(self):
112        return self.size()
113
114if __name__ == "__main__":
115    # 创建对象
116    q = SLList()
117    # 使用 append() 添加值
118    for i in range(100):
119        q.append(i)
120    print("添加后: ", q)
121    # 使用 remove() 删除值
122    for i in range(50):
123        q.remove(i)
124    print("删除后: ", q)
125    # 使用 append() 添加更多值
126    for i in range(100, 200):
127        q.append(i)
128    print("添加后: ", q)
129    # 使用 remove() 删除更多值
130    for i in range(50):
131        q.remove(i)
132    print("删除后: ", q)
133    # 使用 pop() 删除所有值
134    while len(q) != 0:
135        q.pop()
136    print("删除后: ", q)

说明

让我们从 main.py 文件中的 main() 函数开始解释。

• 第 116 行： 创建了一个类型为 Integer 的新 Queue 实例，使用 SLList 实现 Queue 接口。
• 第 118–119 行： 使用 append() 方法将整数 0 到 99 添加到队列中。
• 第 120 行： 打印队列内容 q。
• 第 122–123 行： 使用 remove() 方法从队列中移除前 50 个整数。
• 第 126–127 行： 使用 append() 方法将整数 100 到 199 添加到队列中。
• 第 130–131 行： 使用 remove() 方法从队列中移除前 50 个整数。
• 第 134–135 行： 使用 pop() 方法和 len(q) != 0 条件判断来持续移除队列中剩余的所有元素。