在一些面试或者力扣题中都要求用双向链表来实现，下面是基于python的双向链表实现。
一、构建链表节点
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Node: def __init__(self, key, value): """ 初始化方法 :param key: :param value: """ self.key = key self.value = value self.prev = None self.next = None def __str__(self): val = '{%s: %s}' % (self.key, self.value) return val def __repr__(self): val = '{%s: %s}' % (self.key, self.value) return val |
除了一些节点的基础属性外还有__str__方法用于自定义print(node)的字符串描述(类似Java的toString())，__repr__用于自定义直接调用Node类时的字符串描述
二、实现链表类
具体逻辑主要包括头部添加、尾部添加、头部删除、尾部删除和任意节点的删除，所有对双向链表的操作都是基于这几个方法实现的，具体流程都写在注释中了
|
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
|
class DoubleLinkedList: def __init__(self, capacity=0xffffffff): """ 双向链表 :param capacity: 链表容量 初始化为int的最大值2^32-1 :return: """ self.capacity = capacity self.size = 0 self.head = None self.tail = None def __add_head(self, node): """ 向链表头部添加节点 头部节点不存在 新添加节点为头部和尾部节点 头部节点已存在 新添加的节点为新的头部节点 :param node: 要添加的节点 :return: 已添加的节点 """ # 头部节点为空 if not self.head: self.head = node self.tail = node self.head.next = None self.tail.prev = None # 头部节点不为空 else: node.next = self.head self.head.prev = node self.head = node self.head.prev = None self.size += 1 return node def __add_tail(self, node): """ 向链表尾部添加节点 尾部节点不存在 新添加的节点为头部和尾部节点 尾部节点已存在 新添加的节点为新的尾部节点 :param node: 添加的节点 :return: 已添加的节点 """ # 尾部节点为空 if not self.tail: self.tail = node self.head = node self.head.next = None self.tail.prev = None # 尾部节点不为空 else: node.prev = self.tail self.tail.next = node self.tail = node self.tail.next = None self.size += 1 return node def __remove_head(self): """ 删除头部节点 头部节点不存在 返回None 头部节点已存在 判断链表节点数量 删除头部节点 :return: 头部节点 """ # 头部节点不存在 if not self.head: return None # 链表至少存在两个节点 head = self.head if head.next: head.next.prev = None self.head = head.next # 只存在头部节点 else: self.head = self.tail = None self.size -= 1 return head def __remove_tail(self): """ 删除尾部节点 尾部节点不存在 返回None 尾部节点已存在 判断链表节点数量 删除尾部节点 :return: 尾部节点 """ # 尾部节点不存在 if not self.tail: return None # 链表至少存在两个节点 tail = self.tail if tail.prev: tail.prev.next = None self.tail = tail.prev # 只存在尾部节点 else: self.head = self.tail = None self.size -= 1 return tail def __remove(self, node): """ 删除任意节点 被删除的节点不存在 默认删除尾部节点 删除头部节点 删除尾部节点 删除其他节点 :param node: 被删除的节点 :return: 被删除的节点 """ # 被删除的节点不存在 if not node: node = self.tail # 删除的是头部节点 if node == self.head: self.__remove_head() # 删除的是尾部节点 elif node == self.tail: self.__remove_tail() # 删除的既不是头部也不是尾部节点 else: node.next.prev = node.prev node.prev.next = node.next self.size -= 1 return node def pop(self): """ 弹出头部节点 :return: 头部节点 """ return self.__remove_head() def append(self, node): """ 添加尾部节点 :param node: 待追加的节点 :return: 尾部节点 """ return self.__add_tail(node) def append_front(self, node): """ 添加头部节点 :param node: 待添加的节点 :return: 已添加的节点 """ return self.__add_head(node) def remove(self, node=None): """ 删除任意节点 :param node: 待删除的节点 :return: 已删除的节点 """ return self.__remove(node) def print(self): """ 打印当前链表 :return: """ node = self.head line = '' while node: line += '%s' % node node = node.next if node: line += '=>' print(line) |
三、测试逻辑
|
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__': double_linked_list = DoubleLinkedList(10) nodes = [] # 构建十个节点的双向列表 for i in range(10): node_item = Node(i, i) nodes.append(node_item) double_linked_list.append(nodes[0]) double_linked_list.print() double_linked_list.append(nodes[1]) double_linked_list.print() double_linked_list.pop() double_linked_list.print() double_linked_list.append_front(nodes[2]) double_linked_list.print() double_linked_list.append(nodes[3]) double_linked_list.print() double_linked_list.remove(nodes[3]) double_linked_list.print() double_linked_list.remove() double_linked_list.print() |
测试结果:
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/wang_xiaowang/article/details/105911411
