Python数据结构之双链表

本文转载自微信公众号「python与大数据分析」，作者一只小小鸟鸟。转载本文请联系python与大数据分析公众号。

创新互联是一家专注于成都网站设计、做网站、成都外贸网站建设公司与策划设计,二七网站建设哪家好?创新互联做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:二七等地区。二七做网站价格咨询:18980820575

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

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

方法和单链表是一致的。

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. 
  
  
  
  
  2. # -*- coding: UTF-8 -*- 
    3. 
  
  
  
  
  3. #                     _ooOoo_ 
    4. 
  
  
  
  
  4. #                   o8888888o 
    5. 
  
  
  
  
  5. #                    88" . "88 
    6. 
  
  
  
  
  6. #                 ( | -  _  - | ) 
    7. 
  
  
  
  
  7. #                     O\ = /O 
    8. 
  
  
  
  
  8. #                 ____/`---'\____ 
    9. 
  
  
  
  
  9. #                  .' \\| |// `. 
    10. 
  
  
  
  
  10. #                 / \\|||:|||// \ 
    11. 
  
  
  
  
  11. #               / _|||||-:- |||||- \ 
    12. 
  
  
  
  
  12. #                | | \\\ - /// | | 
    13. 
  
  
  
  
  13. #              | \_| ''\---/'' | _/ | 
    14. 
  
  
  
  
  14. #               \ .-\__ `-` ___/-. / 
    15. 
  
  
  
  
  15. #            ___`. .' /--.--\ `. . __ 
    16. 
  
  
  
  
  16. #         ."" '< `.___\_<|>_/___.' >'"". 
    17. 
  
  
  
  
  17. #       | | : `- \`.;`\  _ /`;.`/ - ` : | | 
    18. 
  
  
  
  
  18. #          \ \ `-. \_ __\ /__ _/ .-` / / 
    19. 
  
  
  
  
  19. #      ==`-.____`-.___\_____/___.-`____.-'== 
    20. 
  
  
  
  
  20. #                     `=---=' 
    21. 
  
  
  
  
  21. ''' 
    22. 
  
  
  
  
  22. @Project ：pythonalgorithms  
    23. 
  
  
  
  
  23. @File ：doublelinklist.py 
    24. 
  
  
  
  
  24. @Author ：不胜人生一场醉 
    25. 
  
  
  
  
  25. @Date ：2021/7/13 23:00  
    26. 
  
  
  
  
  26. ''' 
    27. 
  
  
  
  
  27.  
    28. 
  
  
  
  
  28.  
    29. 
  
  
  
  
  29. class Node(object): 
    30. 
  
  
  
  
  30.     def __init__(self, data): 
    31. 
  
  
  
  
  31.         self.prev = None 
    32. 
  
  
  
  
  32.         self.data = data 
    33. 
  
  
  
  
  33.         self.next = None 
    34. 
  
  
  
  
  34.  
    35. 
  
  
  
  
  35.  
    36. 
  
  
  
  
  36. class DoubleLinkList(object): 
    37. 
  
  
  
  
  37.     def __init__(self): 
    38. 
  
  
  
  
  38.         self.header = None 
    39. 
  
  
  
  
  39.         self.currentnum = 0 
    40. 
  
  
  
  
  40.  
    41. 
  
  
  
  
  41.     def isempty(self): 
    42. 
  
  
  
  
  42.         return self.header == None 
    43. 
  
  
  
  
  43.  
    44. 
  
  
  
  
  44.     def travel(self): 
    45. 
  
  
  
  
  45.         tempnode = self.header 
    46. 
  
  
  
  
  46.         while tempnode != None: 
    47. 
  
  
  
  
  47.             print("{}".format(tempnode.data), end=" ") 
    48. 
  
  
  
  
  48.             tempnode = tempnode.next 
    49. 
  
  
  
  
  49.         print("\r") 
    50. 
  
  
  
  
  50.  
    51. 
  
  
  
  
  51.     def add(self, item): 
    52. 
  
  
  
  
  52.         node = Node(item) 
    53. 
  
  
  
  
  53.         if self.isempty(): 
    54. 
  
  
  
  
  54.             self.header = node 
    55. 
  
  
  
  
  55.             self.currentnum += 1 
    56. 
  
  
  
  
  56.             return 
    57. 
  
  
  
  
  57.         node.next = self.header 
    58. 
  
  
  
  
  58.         self.header.prev = node 
    59. 
  
  
  
  
  59.         self.header = node 
    60. 
  
  
  
  
  60.         self.currentnum += 1 
    61. 
  
  
  
  
  61.  
    62. 
  
  
  
  
  62.     def append(self, item): 
    63. 
  
  
  
  
  63.         if self.isempty(): 
    64. 
  
  
  
  
  64.             self.add(item) 
    65. 
  
  
  
  
  65.             self.currentnum += 1 
    66. 
  
  
  
  
  66.             return 
    67. 
  
  
  
  
  67.         tempnode = self.header 
    68. 
  
  
  
  
  68.         while tempnode.next is not None: 
    69. 
  
  
  
  
  69.             tempnode = tempnode.next 
    70. 
  
  
  
  
  70.         node = Node(item) 
    71. 
  
  
  
  
  71.         node.prev = tempnode 
    72. 
  
  
  
  
  72.         tempnode.next = node 
    73. 
  
  
  
  
  73.         self.currentnum += 1 
    74. 
  
  
  
  
  74.  
    75. 
  
  
  
  
  75.     def length(self): 
    76. 
  
  
  
  
  76.         length = 0 
    77. 
  
  
  
  
  77.         tempnode = self.header 
    78. 
  
  
  
  
  78.         while tempnode is not None: 
    79. 
  
  
  
  
  79.             length += 1 
    80. 
  
  
  
  
  80.             tempnode = tempnode.next 
    81. 
  
  
  
  
  81.         return length 
    82. 
  
  
  
  
  82.  
    83. 
  
  
  
  
  83.     def search(self, item): 
    84. 
  
  
  
  
  84.         tempnode = self.header 
    85. 
  
  
  
  
  85.         while tempnode != None: 
    86. 
  
  
  
  
  86.             if tempnode.data == item: 
    87. 
  
  
  
  
  87.                 return True 
    88. 
  
  
  
  
  88.             else: 
    89. 
  
  
  
  
  89.                 tempnode = tempnode.next 
    90. 
  
  
  
  
  90.         return False 
    91. 
  
  
  
  
  91.  
    92. 
  
  
  
  
  92.     def update(self, index, item): 
    93. 
  
  
  
  
  93.         pass 
    94. 
  
  
  
  
  94.  
    95. 
  
  
  
  
  95.     def getitem(self, index): 
    96. 
  
  
  
  
  96.         if index > self.currentnum or index <= 0: 
    97. 
  
  
  
  
  97.             raise IndexError("{} is not find in Linklist".format(index)) 
    98. 
  
  
  
  
  98.         tempnode = self.header 
    99. 
  
  
  
  
  99.         i = 1 
    100. 
  
  
  
  
  100.         while i < index: 
    101. 
  
  
  
  
  101.             tempnode = tempnode.next 
    102. 
  
  
  
  
  102.             i += 1 
    103. 
  
  
  
  
  103.         if tempnode.next == None: 
    104. 
  
  
  
  
  104.             return -1 
    105. 
  
  
  
  
  105.         else: 
    106. 
  
  
  
  
  106.             return tempnode.data 
    107. 
  
  
  
  
  107.  
    108. 
  
  
  
  
  108.     def getindex(self, item): 
    109. 
  
  
  
  
  109.  
    110. 
  
  
  
  
  110.         tempnode = self.header 
    111. 
  
  
  
  
  111.         i = 0 
    112. 
  
  
  
  
  112.         flag = False 
    113. 
  
  
  
  
  113.         while tempnode != None: 
    114. 
  
  
  
  
  114.             i += 1 
    115. 
  
  
  
  
  115.             if tempnode.data == item: 
    116. 
  
  
  
  
  116.                 flag = True 
    117. 
  
  
  
  
  117.                 return i 
    118. 
  
  
  
  
  118.             else: 
    119. 
  
  
  
  
  119.                 tempnode = tempnode.next 
    120. 
  
  
  
  
  120.         if flag == False: 
    121. 
  
  
  
  
  121.             return 0 
    122. 
  
  
  
  
  122.  
    123. 
  
  
  
  
  123.     def insert(self, item, index): 
    124. 
  
  
  
  
  124.         tempnode = self.header 
    125. 
  
  
  
  
  125.         if index > self.currentnum + 1 or index <= 0: 
    126. 
  
  
  
  
  126.             raise IndexError("{} is not find in Linklist".format(index)) 
    127. 
  
  
  
  
  127.         # 指定位置为第一个即在头部插入 
    128. 
  
  
  
  
  128.  
    129. 
  
  
  
  
  129.         if index == 1: 
    130. 
  
  
  
  
  130.             self.add(item) 
    131. 
  
  
  
  
  131.         elif index > self.currentnum - 1: 
    132. 
  
  
  
  
  132.             self.append(item) 
    133. 
  
  
  
  
  133.         else: 
    134. 
  
  
  
  
  134.             node = Node(item) 
    135. 
  
  
  
  
  135.             for i in range(1, index - 1): 
    136. 
  
  
  
  
  136.                 tempnode = tempnode.next 
    137. 
  
  
  
  
  137.             node.next = tempnode.next 
    138. 
  
  
  
  
  138.             node.prev = tempnode 
    139. 
  
  
  
  
  139.             tempnode.next.prev = node 
    140. 
  
  
  
  
  140.             tempnode.next = node 
    141. 
  
  
  
  
  141.         self.currentnum += 1 
    142. 
  
  
  
  
  142.  
    143. 
  
  
  
  
  143.     def deletebyitem(self, item): 
    144. 
  
  
  
  
  144.         tempnode = self.header 
    145. 
  
  
  
  
  145.         while tempnode != None: 
    146. 
  
  
  
  
  146.             if tempnode.data == item: 
    147. 
  
  
  
  
  147.                 self.currentnum -= 1 
    148. 
  
  
  
  
  148.                 if tempnode == self.header: 
    149. 
  
  
  
  
  149.                     self.header = self.header.next 
    150. 
  
  
  
  
  150.                     if tempnode.next: 
    151. 
  
  
  
  
  151.                         tempnode.next.prev = None 
    152. 
  
  
  
  
  152.                     return 
    153. 
  
  
  
  
  153.                 if tempnode.next is None: 
    154. 
  
  
  
  
  154.                     tempnode.prev.next = tempnode.next 
    155. 
  
  
  
  
  155.                     return 
    156. 
  
  
  
  
  156.                 tempnode.prev.next = tempnode.next 
    157. 
  
  
  
  
  157.                 tempnode.next.prev = tempnode.prev 
    158. 
  
  
  
  
  158.                 return 
    159. 
  
  
  
  
  159.             tempnode = tempnode.next 
    160. 
  
  
  
  
  160.  
    161. 
  
  
  
  
  161.     def deletebyindex(self, index): 
    162. 
  
  
  
  
  162.  
    163. 
  
  
  
  
  163.         if index > self.currentnum or index <= 0: 
    164. 
  
  
  
  
  164.             raise IndexError("{} is not find in Linklist".format(index)) 
    165. 
  
  
  
  
  165.  
    166. 
  
  
  
  
  166.         i = 1 
    167. 
  
  
  
  
  167.         tempnode = self.header 
    168. 
  
  
  
  
  168.  
    169. 
  
  
  
  
  169.         if index == 1: 
    170. 
  
  
  
  
  170.             self.header = tempnode.next 
    171. 
  
  
  
  
  171.             if tempnode.next: 
    172. 
  
  
  
  
  172.                 tempnode.prev = None 
    173. 
  
  
  
  
  173.             self.currentnum -= 1 
    174. 
  
  
  
  
  174.             return 
    175. 
  
  
  
  
  175.  
    176. 
  
  
  
  
  176.         while tempnode.next and i < index: 
    177. 
  
  
  
  
  177.             tempnode = tempnode.next 
    178. 
  
  
  
  
  178.             i += 1 
    179. 
  
  
  
  
  179.         if tempnode.next is None: 
    180. 
  
  
  
  
  180.             tempnode.prev.next = tempnode.next 
    181. 
  
  
  
  
  181.             self.currentnum -= 1 
    182. 
  
  
  
  
  182.             return 
    183. 
  
  
  
  
  183.         if i == index: 
    184. 
  
  
  
  
  184.             tempnode.prev.next = tempnode.next 
    185. 
  
  
  
  
  185.             tempnode.next.prev = tempnode.prev 
    186. 
  
  
  
  
  186.             self.currentnum -= 1 
    187. 
  
  
  
  
  187.  
    188. 
  
  
  
  
  188.  
    189. 
  
  
  
  
  189. if __name__ == '__main__': 
    190. 
  
  
  
  
  190.     a = DoubleLinkList() 
    191. 
  
  
  
  
  191.     a.add(1)  # 1 
    192. 
  
  
  
  
  192.     a.travel() 
    193. 
  
  
  
  
  193.     a.add(2) 
    194. 
  
  
  
  
  194.     a.travel() 
    195. 
  
  
  
  
  195.     a.append(4) 
    196. 
  
  
  
  
  196.     a.travel() 
    197. 
  
  
  
  
  197.     a.append(3) 
    198. 
  
  
  
  
  198.     a.travel() 
    199. 
  
  
  
  
  199.     print(a.length()) 
    200. 
  
  
  
  
  200.     print(a.search(1)) 
    201. 
  
  
  
  
  201.     print(a.getindex(4)) 
    202. 
  
  
  
  
  202.     print(a.getindex(5)) 
    203. 
  
  
  
  
  203.     print(a.getitem(2)) 
    204. 
  
  
  
  
  204.     # print(a.getitem(5)) 
    205. 
  
  
  
  
  205.     # IndexError: 5 is not find in Linklist 
    206. 
  
  
  
  
  206.     a.insert(5, 1) 
    207. 
  
  
  
  
  207.     a.travel() 
    208. 
  
  
  
  
  208.     a.insert(6, 5) 
    209. 
  
  
  
  
  209.     a.travel() 
    210. 
  
  
  
  
  210.     a.insert(7, 2) 
    211. 
  
  
  
  
  211.     a.travel() 
    212. 
  
  
  
  
  212.     a.deletebyitem(7) 
    213. 
  
  
  
  
  213.     a.travel() 
    214. 
  
  
  
  
  214.     a.deletebyitem(6) 
    215. 
  
  
  
  
  215.     a.travel() 
    216. 
  
  
  
  
  216.     a.deletebyitem(5) 
    217. 
  
  
  
  
  217.     a.travel() 
    218. 
  
  
  
  
  218.     a.deletebyindex(2) 
    219. 
  
  
  
  
  219.     a.travel() 
    220. 
  
  
  
  
  220.     a.deletebyindex(3) 
    221. 
  
  
  
  
  221.     a.travel() 
    222. 
  
  
  
  
  222.     a.deletebyindex(1) 
    223. 
  
  
  
  
  223.     a.travel() 
    224.

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

运行如下：

 
 
 
 
    
  
  
  
  
  1. C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/doublelinklist.py 
    2. 
  
  
  
  
  2. 1  
    3. 
  
  
  
  
  3. 2 1  
    4. 
  
  
  
  
  4. 2 1 4  
    5. 
  
  
  
  
  5. 2 1 4 3  
    6. 
  
  
  
  
  6. 4 
    7. 
  
  
  
  
  7. True 
    8. 
  
  
  
  
  8. 3 
    9. 
  
  
  
  
  9. 0 
    10. 
  
  
  
  
  10. 1 
    11. 
  
  
  
  
  11. 5 2 1 4 3  
    12. 
  
  
  
  
  12. 5 2 1 4 6 3  
    13. 
  
  
  
  
  13. 5 7 2 1 4 6 3  
    14. 
  
  
  
  
  14. 5 2 1 4 6 3  
    15. 
  
  
  
  
  15. 5 2 1 4 3  
    16. 
  
  
  
  
  16. 2 1 4 3  
    17. 
  
  
  
  
  17. 2 4 3  
    18. 
  
  
  
  
  18. 2 4  
    19. 
  
  
  
  
  19. 4  
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. Process finished with exit code 0 
    22.

 

链表头部增加节点示意图

名称栏目：Python数据结构之双链表
网址分享：http://www.shufengxianlan.com/qtweb/news43/498343.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

商城网站知识

行业网站建设

成都定制网站　　 　成都微信开发　　 　装饰公司网站建设方案　　 　王君美油画　　 　防护网厂　　 　H5建站　　 　全网营销推广　　 　自贡电信机房　　 　软文营销　　 　崇州网站建设　　 　重庆水土双线托管　　 　成都花箱　　 　成都广告设计公司　　 　成都手机网站建设　　 　重庆机房托管　　 　郫县明安消防器材　　 　成都小程序开发　　 　边坡防护网厂家　　 　成都logo设计标志　　 　成都做手机网站