使用python实现单向链表，供大家参考，具体内容如下
单向链表：是将所有的数据作为一个个节点，将所有的节点链接在一起。每一个节点中又分为： 存储数据区，链接区
存储数据区： 存储具体的数据
链接区： 指向下一个节点
分析实现：
1、 分析：根据链表的特性，首先要存放有数据的容器，还要有存放节点的容器
2、 节点类中：要有数据区和next区
3、 链表类中：存放所有节点
单链表操作
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
|
# Functions 函数声明class Node(): """ 存放节点类 每次调用该类，实例化一个节点 默认每个节点中有数据区，next区。 数据区为该数据，next区为空 """ def __init__(self, item,next=None): self.item = item self.next = next passclass Linklist(): """ 存放数据类 将所有的节点存放起来的容器 首先，默认链表为空，在这里需要有一个头节点，默认头节点为空 """ def __init__(self, head=None): self.head = head def is_empty(self): return self.head == None def append(self, item): """ 往链表尾部添加数据 1、实例化游标：使用游标指向每一个数据，检索数据和判断数据next是否为空 2、移动游标，从头节点开始，每次使用self.next移动，以为next指向的就是下一个数据 3、添加数据，首先判断链表是否为空，为空的情况下，直接将头节点等于node数据 4、如果不为空，需要从头节点开始，移动游标，判断游标指向的next是否为空 5、使用循环不停的移动节点，当遇到节点中的next为空的情况下停止移动 6、循环条件： 当 条件 != None, 进入循环获取，当cur为空时就不会进入循环，所以在这里要使用 cur != None """ # 首先要实例化一个节点 node = Node(item) # 如果链表为空 if self.is_empty(): # 直接将头节点的next添加node self.head = node else: # 实例化一个游标 cur = self.head while cur.next != None: # 移动游标，得到最后一个游标的数据 cur = cur.next # 将移动后的数据的下一个next添加上 node cur.next=node pass def travel(self): """遍历数据""" # 实例化一个游标 cur = self.head # 数据链为空的情况 if self.is_empty(): print('') else: # 获取每个数据区中的数据 # 移动游标，每移动一次，输出一次数据区内的数据 while cur != None: print(cur.item, end=' ') cur = cur.next print() def length(self): """返回链表的长度""" # 实例化游标 cur = self.head # 计数，这里对空链表进行判断，如果是链表，则不会进入循环，直接输出 0 count = 0 # 移动游标，获取下一个数据，然后让count +=1 while cur != None: # 计数 count+=1 # 移动游标 cur = cur.next return count def add(self, item): """ 头部添加数据 分析： 将数据添加到第一个节点当中 1、 需要先将node的next指向 原第一个节点，这原第一个节点就是self.head 2、 再讲self.head指向node进行连接 """ # 先实例化节点 node = Node(item) # 将数据添加到头部当中 node.next=self.head self.head=node def insert(self, index, item): """ 指定位置添加数据 分析： 1、首先要找到，该位置的数据 2、将要添加的数据next等于 原位置的next数据 3、原数据的 next等于node新数据 """ if index<=0: # 如果输入的索引小于或者等于O，默认使用头插发 self.add(item) elif index>self.length(): # 如果输入的索引大于链表的长度,使用尾插法 self.append(item) else: # 实例化数据节点 node = Node(item) # 找到该数据的位置 # 实例化一个游标 cur = self.head # 计数 conent = 0 while conent<(index-1): conent+=1 cur = cur.next node.next=cur.next cur.next=node def search(self, item): """ 查询指定的数据是否存在 分析： 查询指定的数据，需要对整个链表扫描，判断这个数据是否等的该节点中的数据 """ # 实例化一个游标 cur = self.head # 进行判断是否相等 while cur != None: # 判断 if cur.item == item: return True else: cur = cur.next pass # 否则返回False return False def remove(self, item): """ 移除指定的数据 分析： 1、删除数据，需要首先判断数据是否存在 2、找到该数据所在的位置，将该数据的上一个数据的next指向自己的next 3、如何获取该数据的指向，和上一个数据的指向 4、需要定义两个指针 5、先将两个指针相等，再讲一个指针先移动一次，再同时移动 """ # 先找到该数据 cur = self.head por = None while cur != None: if cur.item==item: # 要判断是否为第一个节点 if cur == self.head: self.head = cur.next else: por.next = cur.next break else: # 如果在当前节点中没有相等的，将节点进行移动 # 移动要注意，现将两个游标相等，再讲另一个游标移动一次 por = cur cur = cur.next |
测试运行
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# 程序的入口if __name__ == "__main__": s = Linklist() s.append(100) s.append(200) s.append(300) s.add(1) s.add(12) s.insert(-1,6) s.travel() # 6 12 1 100 200 300 print(s.length()) # 6 print(s.search(11)) # False s.remove(12) s.travel() # 6 1 100 200 300 print(s.length()) # 5 print(s.search(11)) # False pass |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/Dhaihaihai/article/details/111304273
