Python数据结构之双链表，

文章由Byrx.net分享于2021-07-15 09:07:07评论（119）

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

链表头部增加节点示意图

相关内容

评论关闭

最新python教程

python~HOT