使用python实现单向循环链表，供大家参考，具体内容如下
单向循环链表
将所有的链接在一起，每一个节点分为数据存储区和链接区，数据区存储数据，链接区链接下一个节点
item： 存储数据的地方
next： 链接下一个节点
注意： 单向循环链表是首位链接，即尾部的节点要和头部的节点链接
单向链表操作
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
|
# Functions 函数声明class Node(): """实例化节点类""" def __init__(self, item): self.item = item self.next = Noneclass Linklist(): """ 存放节点类 """ def __init__(self): self.head = None # 1. 链表是否为空 def is_empty(self): return self.head == None # 2. 链表的长度 def length(self): """ 返回链表的长度 遍历所有的节点，使用计数器计数 1、链表为空情况 """ # 实例化节点 cur = self.head if self.is_empty(): return 0 else: # 计数 count = 1 # 遍历链表 while cur.next != self.head: count+=1 cur = cur.next return count # 3. 遍历链表 def travel(self): """ 遍历链表，获取所有的数据 实例游标，遍历数据，输出数据 1、 空链表情况 2、 只有头部节点情况 3、 只有尾部节点情况 """ # 实例化游标 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) # 4. 链表头部添加元素 def add(self, item): """ 往链表头部添加数据 分析 链表为空 self.head 直接指向node， 再讲node指向自己 链表不为空 node.next = self.head """ # 实例化游标 cur = self.head # 实例化节点 node = Node(item) # 判断是否为空 if self.is_empty(): self.head = node node.next = node else: # 不为空的情况 # 要将最后一个节点指向node while cur.next != self.head: cur = cur.next node.next = self.head self.head = node cur.next = node # 5. 链表尾部添加元素 def append(self, item): """ 往尾部添加数据 分析 实例化节点，再实例化游标先指向最后一个节点 调换指向 1、空链表情况 2、只有一个链表情况 """ # 实例化节点 node = Node(item) # 实例化游标 cur = self.head # 判断是否为空 if self.is_empty(): self.add(item) else: # 不为空的情况,移动游标指向最后一个节点 while cur.next != self.head: cur = cur.next node.next = self.head 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: # 判断链表是否为空 if self.is_empty(): self.add(item) else: # 移动游标，指向指定的索引位置 count = 0 while count < index-1: count+=1 cur = cur.next node.next = cur.next cur.next = node pass # 7. 链表删除节点 def remove(self, item): """ 删除指定的节点 实例化游标，遍历链表插件这个节点是否存在，存在则更改指向 不存在，则不修改 空链表情况 头节点情况 尾结点情况 """ # 实例化游标 cur = self.head if self.is_empty(): return None else: # 不为空，遍历链表，对比数据是否相等 # 如果头节点是要删除的数据 if cur.item == item: self.head=cur.next # 找出最后的节点，将最后的节点指向，删除后面的那个节点 while cur.next != self.head: cur = cur.next cur.next = cur.next else: pro = None while cur.next != self.head: if cur.item == item: if cur.item == item: pro.next = cur.next return True else: pro = cur cur = cur.next if cur.item == item: pro.next = self.head pass # 8. 查找节点是否存在 def search(self, item): """ 查找该节点是否存在 实例化游标，遍历所有的节点 查看当前节点的数据是否和item 相等 空链表 头节点 尾结点 """ # 实例化游标 cur = self.head # 判断空链表 if self.is_empty(): return None else: # 不为空遍历整个链表 if cur.item == item: return True 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
|
# 程序的入口if __name__ == "__main__": a = Linklist() a.add(400) a.add(300) a.add(200) a.add(100) # a.append(10) a.insert(4,6) # a.remove(6) print(a.length()) # 5 a.travel() # 100 200 300 400 6 print(a.search(100)) # True pass |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/Dhaihaihai/article/details/111304465
