使用python实现双向链表，供大家参考，具体内容如下
双向链表： 指的是讲数据链接在一起，每个数据是一个节点，每一个节点都有一个数据区，两个链接区，分别链接上一个节点和下一个节点
数据区： 存放数据的地方
prev： 链接上一个节点
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
|
# 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 # 技术器 # 如果链表为空，不会进入循环，直接输出 0 count = 0 # 遍历所有的数据 while cur != None: count +=1 cur = cur.next return count # 3. 遍历链表 def treval(self): """ 遍历链表，获取所有的数据 使用游标，遍历整个链表，每次输出cur.item 的值 注意链表为空的情况， """ # 实例化一个游标 cur = self.head # 遍历链表 while cur != None: print(cur.item, end=' ') cur = cur.next print() # 4. 链表头部添加元素 def add(self, item): """ 头部添加数据 分析： 1、头部添加数据，链表为空时： self.head 指向node 2、链表不为空时： 先将node.next = self.head.next, 再讲 self.head = node """ # 实例化节点 node = Node(item) # 添加数据 # 判断链表是否为空 if self.is_empty(): # 为空，直接将self.head 指向node self.head=node else: # 不为空，先将noede node.next = self.head self.head.prev=node self.head=node # 5. 链表尾部添加元素 def append(self,item): """ 尾部添加数据 分析： 要先将指针指向尾部的节点 最后的节点的 cur.next = node, node.prev = cur """ # 实例化节点 node = Node(item) # 实例化游标 cur = self.head # 移动游标到最后一个节点 # 如果链表为空 # 直接使用头插法 if self.is_empty(): self.add(item) else: while cur.next != None: # cur.next 不为空，则进入循环， 上次循环，是进入上上个节点，但 将cur = cur.next，就指向了最后一个节点 cur = cur.next node.prev = cur cur.next = node # 6. 链表指定位置添加元素 def insert(self, index, item): """ 指定位置添加数据 分析 单链表中需要实例化两个有游标 双向链表，直接向指针指向索引的位置 将这个位置节点的 cur. """ # 实例化节点 node = Node(item) # 实例化游标 cur = self.head # 起始位置 count = 0 if index<=0: # 使用头插法 self.add(item) elif index > (self.length()-1): self.append(item) else: # 移动游标 while count < index: # 增加一 count += 1 # 移动游标到索引位置 cur = cur.next node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node # 7. 链表删除节点 def remove(self,item): """ 删除指定的节点 首先实例化节点，遍历链表，找到该节点，删除该节点 """ # 实例化游标 cur = self.head # 遍历链表，找到该节点 while cur != None: if cur.item == item: if self.head == cur: self.head = cur.next if cur.next: cur.next.prev = None else: cur.prev.next = cur.next # 如果有下个节点，防止最后一个节点 if cur.next: cur.next.prev = cur.prev pass break else: cur = cur.next # # 8. 查找节点是否存在 def search(self, item): """ 查看节点是否存在 分析 遍历链表，查看每一个节点的数据区 空链表 只有头节点 只有尾节点 """ # 实例化一个游标 cur = self.head # 遍历链表 while cur != None: if cur.item == item: return True else: cur = cur.next return False |
测试运行
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# 程序的入口if __name__ == "__main__": s = Linklist() print(s.is_empty()) # True s.append(100) s.append(200) s.append(300) s.add(6) s.insert(1, 10) s.search(6) s.treval() # 6 10 100 200 300 s.remove(100) s.treval() # 6 10 200 300 pass |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/Dhaihaihai/article/details/111304360
