1 '''
2 创建一个结点类
3 '''
4
5
6 class Node:
7 def __init__(self, value=None):
8 self.value = value
9 self.prev = None
10 self.next = None
11
12
13 '''
14 创建一个双链表
15 '''
16
17
18 class doubleLink:
19 def __init__(self):
20 self.header = None # 初始化头结点
21 self.length = 0 # 链表的长度
22
23 # 判断链表是否为空
24 def is_empty(self):
25 return self.length == 0
26
27 '''
28 实现向双链表添加元素的功能
29 有三种实现方式:
30 1.头插法
31 2.尾插法
32 3.向双链表的指定位置添加元素
33 '''
34
35 # 1.头插法
36 def __add__(self, value):
37 node = Node(value)
38 if self.is_empty():
39 node.prev = self.header
40 self.header = node
41 self.length += 1
42 return
43 else:
44 node.next = self.header
45 self.header.prev = node
46 self.header = node
47 self.length += 1
48
49 # 2.尾插法
50 def append(self, value):
51 node = Node(value)
52 if self.is_empty():
53 self.__add__(value)
54 else:
55 cur = self.header
56 while cur.next is not None:
57 cur = cur.next
58 cur.next = node
59 node.prev = cur
60 self.length += 1
61
62 # 3.向双链表的指定位置添加元素
63 def insert(self, index, value):
64 node = Node(value)
65 cur = self.header
66 if index <= 0 or index > self.length:
67 print('您输入的信息有误')
68 return ' '
69 if index == 1:
70 self.__add__(value)
71 for i in range(2, index):
72 cur = cur.next
73 node.next = cur.next
74 cur.next.prev = node
75 cur.next = node
76 node.prev = cur
77 self.length += 1
78 return value
79
80 '''
81 实现插寻双链表元素的功能
82 有三种实现方式:
83 1.根据索引查询元素
84 2.直接查询元素
85 3.遍历整个双链表，并打印出所有的元素
86 '''
87
88 # 1.根据索引查询元素
89 def __getitem__(self, index):
90 cur = self.header
91 for i in range(index - 1):
92 cur = cur.next
93 return cur.value
94
95 # 2.直接查询元素，并返回该元素的索引
96 def getIndex(self, value):
97 cur = self.header
98 temp = 0
99 while cur.next is not self.header:
100 if cur.value == value:
101 return temp + 1
102 cur = cur.next
103 temp += 1
104
105 # 3.遍历整个双链表，并打印出所有的元素
106 def getAll(self):
107 if self.is_empty():
108 print('目前双链表中没有元素！')
109 return
110 cur = self.header
111 for i in range(self.length):
112 print('%d' % cur.value, end=' ')
113 cur = cur.next
114
115 # 4.查询某个元素的后继节点
116 def getItem(self, value):
117 cur = self.header
118 temp = 0
119 while cur.next is not self.header:
120 if cur.value == value:
121 if cur.next is not None:
122 return cur.next.value
123 else:
124 return -1
125 cur = cur.next
126 temp += 1
127
128 # 5.查询某个元素的前驱节点
129 def getPrevItem(self, value):
130 cur = self.header
131 temp = 0
132 while cur.next is not self.header:
133 if cur.value == value:
134 if cur.prev is not None:
135 return cur.prev.value
136 else:
137 return -1
138 cur = cur.next
139 temp += 1
140
141 '''
142 实现修改指定位置元素的功能
143 '''
144
145 def __setitem__(self, index, value):
146 cur = self.header
147 for i in range(index - 1):
148 cur = cur.next
149 cur.value = value
150 return value
151
152 '''
153 实现删除双链表元素的功能
154
155 '''
156 # 直接删除元素
157 def __delete__(self, value):
158 cur = self.header
159 if self.getIndex(value) == 1:
160 self.header = cur.next
161 self.length -= 1
162 elif self.getIndex(value) != 1:
163 while self.getIndex(value) != self.length:
164 cur = cur.next
165 cur=None
166 self.length -= 1
167 else:
168 while cur.value != value:
169 cur = cur.next
170 cur.prev.next = cur.next
171 cur.next.prev = cur.prev
172 self.length -= 1
173
174
175 if __name__ == '__main__':
176 s = doubleLink()
177 s.__add__(12)
178 s.__add__(13)
179 s.__add__(14)
180 s.__add__(15)
181 s.append(22)
182 s.getAll()
183 print('\n第%d个位置的元素是%d.' % (1, s.__getitem__(1)))
184 print('\n元素%d在双链表的第%d个位置' % (14, s.getIndex(14)))
185 print('获取元素%d的后继节点%d' % (12, s.getItem(12)))
186 print('获取元素%d的前驱节点%d' % (13, s.getPrevItem(13)))
187 print('在第%d个位置插入元素%d:' % (2, s.insert(2, 45)))
188 s.getAll()
189 print('\n将第%d个位置的元素修改为%d:' % (1, s.__setitem__(1, 900)))
190 s.getAll()
191 print('\n删除第%d个元素:' % 5)
192 s.__delitem__(5)
193 print('\n删除元素22:')
194 s.__delete__(22)
195 s.getAll()