自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

Python數(shù)據(jù)結(jié)構(gòu)之雙鏈表

作者：一只小小鳥鳥
開發(fā) 后端
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。

[[411390]]

本文轉(zhuǎn)載自微信公眾號「python與大數(shù)據(jù)分析」，作者一只小小鳥鳥。轉(zhuǎn)載本文請聯(lián)系python與大數(shù)據(jù)分析公眾號。

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。

雙鏈表和單鏈表在查找和遍歷上沒什么區(qū)別，在新增節(jié)點(diǎn)、添加節(jié)點(diǎn)、刪除節(jié)點(diǎn)上需要注意前后節(jié)點(diǎn)的修改，比單鏈表會(huì)復(fù)雜一些，一不小心就繞暈了。

方法和單鏈表是一致的。

isempty(self) 鏈表是否為空

length(self) 鏈表長度

travel(self) 遍歷整個(gè)鏈表

add(self,item) 鏈表頭部添加元素

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

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

deletebyitem(self,item) 根據(jù)數(shù)據(jù)項(xiàng)刪除節(jié)點(diǎn)

deletebyindex(self,index) 根據(jù)索引位置刪除節(jié)點(diǎn)

search(self,item) 根據(jù)數(shù)據(jù)項(xiàng)查找節(jié)點(diǎn)是否存在

update(self,index,item) 暫無實(shí)現(xiàn)

getitem(self,index) 獲取索引位置對應(yīng)的數(shù)據(jù)項(xiàng)

getindex(self,item) 獲取數(shù)據(jù)項(xiàng)對應(yīng)的索引位置

如下：

  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.         # 指定位置為第一個(gè)即在頭部插入 
  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() 

調(diào)試了2、3個(gè)小時(shí)的bug，才跑通。

運(yùn)行如下：

  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 

 

鏈表頭部增加節(jié)點(diǎn)示意圖

 

責(zé)任編輯：武曉燕 來源： python與大數(shù)據(jù)分析
Python數(shù)據(jù)結(jié)構(gòu)
相關(guān)推薦

2017-03-01 13:58:46

Python數(shù)據(jù)結(jié)構(gòu)鏈表

2021-07-13 07:52:03

Python數(shù)據(jù)結(jié)構(gòu)

2012-02-02 10:21:05

單鏈表nexthead

2021-08-03 10:24:59

數(shù)據(jù)跳躍鏈表結(jié)構(gòu)

2021-05-12 14:09:35

鏈表數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)

2021-04-12 15:47:00

數(shù)據(jù)結(jié)構(gòu)算法鏈表

2021-07-16 07:57:34

Python數(shù)據(jù)結(jié)構(gòu)

2021-12-21 08:19:29

數(shù)據(jù)結(jié)構(gòu)算法鏈表相交

2021-10-29 11:27:52

鏈表數(shù)據(jù)結(jié)構(gòu)算法

2021-01-06 08:03:00

JavaScript數(shù)據(jù)結(jié)構(gòu)

2021-07-11 12:06:43

python數(shù)據(jù)結(jié)構(gòu)

2021-01-28 07:33:34

JavaScript鏈表數(shù)據(jù)

2021-03-10 08:42:19

Java數(shù)據(jù)結(jié)構(gòu)算法

2023-03-28 07:44:23

數(shù)據(jù)結(jié)構(gòu)數(shù)組

2023-10-06 20:21:28

Python鏈表

2009-07-02 14:59:28

Java考研試題

2021-09-12 17:31:17

Python數(shù)據(jù)結(jié)構(gòu)

2024-10-11 16:43:05

高并發(fā)數(shù)據(jù)結(jié)構(gòu)技巧

2018-06-06 08:54:23

數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)

2020-12-31 05:31:01

數(shù)據(jù)結(jié)構(gòu)算法
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號