Python数据结构之双链表

 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双链表和单链表在查找和遍历上没什么区别，在新增节点、添加节点、删除节点上需要注意前后节点的修改，比单链表会复杂一些，一不小心就绕晕了。

方法和单链表是一致的。

isempty(self) 链表是否为空

length(self) 链表长度

travel(self) 遍历整个链表

add(self,item) 链表头部添加元素

append(self,item) 链表尾部添加元素

insert(self,item,index) 指定位置添加元素

deletebyitem(self,item) 根据数据项删除节点

deletebyindex(self,index) 根据索引位置删除节点

search(self,item) 根据数据项查找节点是否存在

update(self,index,item) 暂无实现

getitem(self,index) 获取索引位置对应的数据项

getindex(self,item) 获取数据项对应的索引位置

如下：

1. #!/usr/bin/env python 

2. # -*- coding: UTF-8 -*- 

3. #                     _ooOoo_ 

4. #                   o8888888o 

5. #                    88" . "88 

6. #                 ( | -  _  - | ) 

7. #                     O\ = /O 

8. #                 ____/`---'\____ 

9. #                  .' \\| |// `. 

10. #                 / \\|||:|||// \ 

11. #               / _|||||-:- |||||- \ 

12. #                | | \\\ - /// | | 

13. #              | \_| ''\---/'' | _/ | 

14. #               \ .-\__ `-` ___/-. / 

15. #            ___`. .' /--.--\ `. . __ 

16. #         ."" '< `.___\_<|>_/___.' >'"". 

17. #       | | : `- \`.;`\  _ /`;.`/ - ` : | | 

18. #          \ \ `-. \_ __\ /__ _/ .-` / / 

19. #      ==`-.____`-.___\_____/___.-`____.-'== 

20. #                     `=---=' 

21. ''' 

22. @Project ：pythonalgorithms  

23. @File ：doublelinklist.py 

24. @Author ：不胜人生一场醉 

25. @Date ：2021/7/13 23:00  

26. ''' 

27. class Node(object): 

28.     def __init__(self, data): 

29.         self.prev = None 

30.         self.data = data 

31.         self.next = None 

32. class DoubleLinkList(object): 

33.     def __init__(self): 

34.         self.header = None 

35.         self.currentnum = 0 

36.    def isempty(self): 

37.         return self.header == None 

38.     def travel(self): 

39.         tempnode = self.header 

40.         while tempnode != None: 

41.             print("{}".format(tempnode.data), end=" ") 

42.             tempnode = tempnode.next 

43.         print("\r") 

44.     def add(self, item): 

45.         node = Node(item) 

46.         if self.isempty(): 

47.             self.header = node 

48.             self.currentnum += 1 

49.             return 

50.         node.next = self.header 

51.         self.header.prev = node 

52.         self.header = node 

53.         self.currentnum += 1 

54.     def append(self, item): 

55.         if self.isempty(): 

56.             self.add(item) 

57.             self.currentnum += 1 

58.             return 

59.         tempnode = self.header 

60.         while tempnode.next is not None: 

61.             tempnode = tempnode.next 

62.         node = Node(item) 

63.         node.prev = tempnode 

64.         tempnode.next = node 

65.         self.currentnum += 1 

66.     def length(self): 

67.         length = 0 

68.         tempnode = self.header 

69.         while tempnode is not None: 

70.             length += 1 

71.             tempnode = tempnode.next 

72.         return length 

73.     def search(self, item): 

74.         tempnode = self.header 

75.         while tempnode != None: 

76.             if tempnode.data == item: 

77.                 return True 

78.             else: 

79.                 tempnode = tempnode.next 

80. <360>        return False 

81.     def update(self, index, item): 

82.         pass 

83.     def getitem(self, index): 

84.         if index > self.currentnum or index <= 0: 

85.             raise IndexError("{} is not find in Linklist".format(index)) 

86.         tempnode = self.header 

87.         i = 1 

88.         while i < index: 

89.            tempnode = tempnode.next 

90.            i += 1 

91.         if tempnode.next == None: 

92.             return -1 

93.         else: 

94.             return tempnode.data 

95.     def getindex(self, item): 

96.         tempnode = self.header 

97.         i = 0 

98.         flag = False 

99.         while tempnode != None: 

100.             i += 1 

101.             if tempnode.data == item: 

102.                 flag = True 

103.                 return i 

104.             else: 

105.                 tempnode = tempnode.next 

106.         if flag == False: 

107.             return 0 

108.     def insert(self, item, index): 

109.         tempnode = self.header 

110.         if index > self.currentnum + 1 or index <= 0: 

111.             raise IndexError("{} is not find in Linklist".format(index)) 

112.         # 指定位置为第一个即在头部插入 

113.         if index == 1: 

114.             self.add(item) 

115.         elif index > self.currentnum - 1: 

116.             self.append(item) 

117.         else: 

118.             node = Node(item) 

119.             for i in range(1, index - 1): 

120.                 tempnode = tempnode.next 

121.            node.next = tempnode.next 

122.             node.prev = tempnode 

123.             tempnode.next.prev = node 

124.             tempnode.next = node 

125.         self.currentnum += 1 

126.     def deletebyitem(self, item): 

127.         tempnode = self.header 

128.         while tempnode != None: 

129.             if tempnode.data == item: 

130.                 self.currentnum -= 1 

131.                 if tempnode == self.header: 

132.                     self.header = self.header.next 

133.                     if tempnode.next: 

134.                         tempnode.next.prev = None 

135.                     return 

136.                 if tempnode.next is None: 

137.                     tempnode.prev.next = tempnode.next 

138.                     return 

139.                 tempnode.prev.next = tempnode.next 

140.                 tempnode.next.prev = tempnode.prev 

141.                 return 

142.             tempnode = tempnode.next 

143.     def deletebyindex(self, index): 

144.         if index > self.currentnum or index <= 0: 

145.             raise IndexError("{} is not find in Linklist".format(index)) 

146.         i = 1 

147.         tempnode = self.header 

148.         if index == 1: 

149.             self.header = tempnode.next 

150.             if tempnode.next: 

151.                 tempnode.prev = None 

152.             self.currentnum -= 1 

153.             return 

154.         while tempnode.next and i < index: 

155.             tempnode = tempnode.next 

156.             i += 1 

157.         if tempnode.next is None: 

158.             tempnode.prev.next = tempnode.next 

159.             self.currentnum -= 1 

160.             return 

161.         if i == index: 

162.             tempnode.prev.next = tempnode.next 

163.             tempnode.next.prev = tempnode.prev 

164.             self.currentnum -= 1 

165. if __name__ == '__main__': 

166.     a = DoubleLinkList() 

167.     a.add(1)  # 1 

168.     a.travel() 

169.     a.add(2) 

170.     a.travel() 

171.     a.append(4) 

172.     a.travel() 

173.     a.append(3) 

174.     a.travel() 

175.     print(a.length()) 

176.     print(a.search(1)) 

177.     print(a.getindex(4)) 

178.     print(a.getindex(5)) 

179.     print(a.getitem(2)) 

180.     # print(a.getitem(5)) 

181.     # IndexError: 5 is not find in Linklist 

182.     a.insert(5, 1) 

183.     a.travel() 

184.     a.insert(6, 5) 

185.     a.travel() 

186.     a.insert(7, 2) 

187.     a.travel() 

188.     a.deletebyitem(7) 

189.     a.travel() 

190.     a.deletebyitem(6) 

191.     a.travel() 

192.     a.deletebyitem(5) 

193.     a.travel() 

194.     a.deletebyindex(2) 

195.     a.travel() 

196.     a.deletebyindex(3) 

197.     a.travel() 

198.     a.deletebyindex(1) 

199.     a.travel() 

调试了2、3个小时的bug，才跑通。

运行如下：

1. C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/doublelinklist.py 

2. 1  

3. 2 1  

4. 2 1 4  

5. 2 1 4 3  

6. 4 

7. True 

8. 3 

9. 0 

10. 1 

11. 5 2 1 4 3  

12. 5 2 1 4 6 3  

13. 5 7 2 1 4 6 3  

14. 5 2 1 4 6 3  

15. 5 2 1 4 3  

16. 2 1 4 3  

17. 2 4 3  

18. 2 4  

19. 4  

20. Process finished with exit code 0 

链表头部增加节点示意图