使用python实现双向循环链表，供大家参考，具体内容如下
双向循环链表： 将所有的数据存放到节点中，每一个节点相连接，首尾链接，
每一个节点中有一个数据存储区，和两个链接区，一个链接前一个节点，一个链接下一个节点
双向链表操作
1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在
代码实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
# Functions 函数声明class Node(): """实例化节点类""" def __init__(self, item): self.item = item self.prev = None self.next = Noneclass Linklist(): """ 存放节点类 """ def __init__(self): self.head = None # 1. 链表是否为空 def is_empty(self): return self.head == None # 2. 链表的长度 def length(self): """ 返回链表中所有数据的个数 实例化游标，遍历链表，使用计数器自增一 空链表 """ # 实例化游标 cur = self.head # 判断是否为空 if self.is_empty(): return 0 else: # 不为空 # 定义计数 count = 1 while cur.next != self.head: count+=1 cur = cur.next return count pass # 3. 遍历链表 def travel(self): """ 遍历链表 实例化游标，遍历链表，每次输出节点的数据 空链表 只有头节点 """ # 实例化游标 cur = self.head # 判断是否为空 if self.is_empty(): return None else: # 不为空的情况 while cur.next != self.head: print(cur.item, end=' ') cur = cur.next print(cur.item) pass # 4. 链表头部添加元素 def add(self, item): """ 头节点添加 实例化节点， """ # 实例化节点 node = Node(item) # 实例化游标 cur = self.head # 判断是否为空 if self.is_empty(): node.next = node node.prev = node self.head = node else: # 链表不为空的情况 # 只有一个节点的情况 # node.next = self.head node.next = cur node.prev = cur if cur.next == self.head: # print(cur.item) cur.prev = node cur.next = node self.head = node elif cur.next != self.head: pro = self.head while cur.next != self.head: cur = cur.next pro.prev = node cur.next = node self.head = node pass # 5. 链表尾部添加元素 def append(self, item): """ 链表尾部添加数据 实例化节点，实例化游标，指向尾部节点，修改指向 链表为空 """ # 实例化节点 node = Node(item) # 实例化游标 cur = self.head if self.is_empty(): self.add(item) else: # 不为空的情况 # 指针指向最后一个节点 self.head.prev = node node.next = self.head while cur.next != self.head: cur = cur.next node.prev = cur cur.next = node pass # 6. 链表指定位置添加元素 def insert(self, index, item): """ 指定位置添加数据 实例化节点， 实例化游标 移动游标到索引位置，更改指向 输入索引大小判断 链表是否为空 """ # 实例化节点 node = Node(item) # 实例化游标 cur = self.head if index <= 0: self.add(item) elif index > (self.length()-1): self.append(item) else: # 中间添加数据 # 声明计数 count = 0 print(index) while count < index-1: count+=1 cur = cur.next # print(cur.item) node.next = cur.next node.prev = cur cur.next.prev = node cur.next = node pass # 7. 链表删除节点 def remove(self, item): """ 删除数据 实例化游标，遍历链表，查找有没有改数据 有，对改数据两侧的节点进行指向修改 """ # 实例化游标 cur = self.head # 判断是否为空 if self.is_empty(): return None else: # 不为空的情况下 # 如果删除的是头节点 if cur.item == item: # 如果只有一个头节点 if cur.next == self.head: self.head = None else: # self.head = cur.next pro = cur.next while cur.next != self.head: cur = cur.next cur.next = pro pro.prev = cur self.head = pro pass else: while cur.next != self.head: if cur.item == item: # print(cur.item) pro = cur.prev nex = cur.next pro.next = cur.next nex.prev = pro return True else: cur = cur.next # 如果是最后一个节点 if cur.item == item: cur.prev.next = self.head self.head.prev = cur.prev # 8. 查找节点是否存在 def search(self, item): """ 查询指定的数据是否存在 实例化游标 遍历所有的节点。每个节点中判断数据是否相等，相等，返回True """ # 实例化游标 cur = self.head # 判断是否为空 if self.is_empty(): return None else: # 不为空的情况 # 遍历所有的节点 while cur.next != self.head: if cur.item == item: return True else: cur = cur.next if cur.item == item: return True pass |
测试运行
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# 程序的入口if __name__ == "__main__": a = Linklist() a .add(400) a .add(300) a .add(200) a .add(100) a.append(10) a.append(11) a.add(1) a.insert(30, 12) # 1 100 200 300 400 10 11 12 a.remove(1) # 100 200 300 400 10 11 12 a.remove(12) # 100 200 300 400 10 11 a.remove(400) # # 100 200 300 10 11 a.remove(4000) print(a.search(100)) # True print(a.search(11)) # True print(a.search(111)) # None print(a.is_empty()) # False a.travel() # 100 200 300 10 11 print(a.length()) # 5 pass |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/Dhaihaihai/article/details/111304544
