Python数据结构之单链表

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

创新互联建站主要从事成都做网站、成都网站建设、成都外贸网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务石城,10余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108

今天终于把大学都没想明白的链表数据结构整明白了，也算小小的收获，挺好玩的。文后附链表操作示意图。

单向链表(单链表)是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。它的每个节点包含两个域，一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

  • 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. class Node(object): 
    2.   
  
  
  
  2.     def __init__(self, item): 
    3.   
  
  
  
  3.         self.item = item 
    4.   
  
  
  
  4.         self.next = None 
    5.   
  
  
  
  5.     def __repr__(self): 
    6.   
  
  
  
  6.         pass 
    7.   
  
  
  
  7.     def __str__(self): 
    8.   
  
  
  
  8.         return str(self.item) 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10. class SingleLinkList(object): 
    11.   
  
  
  
  11.     def __init__(self): 
    12.   
  
  
  
  12.         self.header = None 
    13.   
  
  
  
  13.         self.currentnum=0 
    14.   
  
  
  
  14.  
    15.   
  
  
  
  15.     def isempty(self): 
    16.   
  
  
  
  16.         return self.header == None 
    17.   
  
  
  
  17.  
    18.   
  
  
  
  18.     def length(self): 
    19.   
  
  
  
  19.         return self.currentnum 
    20.   
  
  
  
  20.  
    21.   
  
  
  
  21.     def travel(self): 
    22.   
  
  
  
  22.         cur =self.header 
    23.   
  
  
  
  23.         while cur !=None: 
    24.   
  
  
  
  24.             print("{}".format(cur.item),end=" ") 
    25.   
  
  
  
  25.             cur=cur.next 
    26.   
  
  
  
  26.         print("\r") 
    27.   
  
  
  
  27.  
    28.   
  
  
  
  28.     def add(self,item): 
    29.   
  
  
  
  29.         node=Node(item) 
    30.   
  
  
  
  30.         # 新节点的链接指向头节点 
    31.   
  
  
  
  31.         node.next=self.header 
    32.   
  
  
  
  32.         # 链表的头指向新节点 
    33.   
  
  
  
  33.         self.header=node 
    34.   
  
  
  
  34.         self.currentnum+=1 
    35.   
  
  
  
  35.  
    36.   
  
  
  
  36.     def append(self,item): 
    37.   
  
  
  
  37.         tempnode=self.header 
    38.   
  
  
  
  38.         node=Node(item) 
    39.   
  
  
  
  39.         if self.isempty(): 
    40.   
  
  
  
  40.             self.add(node) 
    41.   
  
  
  
  41.         else: 
    42.   
  
  
  
  42.             while tempnode.next!=None: 
    43.   
  
  
  
  43.                 tempnode=tempnode.next 
    44.   
  
  
  
  44.             tempnode.next=node 
    45.   
  
  
  
  45.             self.currentnum+=1 
    46.   
  
  
  
  46.  
    47.   
  
  
  
  47.     def insert(self,item,index): 
    48.   
  
  
  
  48.         node=Node(item) 
    49.   
  
  
  
  49.         tempnode=self.header 
    50.   
  
  
  
  50.         if index>self.currentnum+1 or index<=0: 
    51.   
  
  
  
  51.             raise IndexError("{} is not find in Linklist".format(index)) 
    52.   
  
  
  
  52.         # 指定位置为第一个即在头部插入 
    53.   
  
  
  
  53.         if index==1: 
    54.   
  
  
  
  54.             self.add(node) 
    55.   
  
  
  
  55.         elif index>self.currentnum-1: 
    56.   
  
  
  
  56.             self.append(node) 
    57.   
  
  
  
  57.         else: 
    58.   
  
  
  
  58.             for i in range(1,index-1): 
    59.   
  
  
  
  59.                 tempnode=tempnode.next 
    60.   
  
  
  
  60.             node.next=tempnode.next 
    61.   
  
  
  
  61.             tempnode.next=node 
    62.   
  
  
  
  62.             self.currentnum+=1 
    63.   
  
  
  
  63.  
    64.   
  
  
  
  64.     def deletebyitem(self,item): 
    65.   
  
  
  
  65.         tempnode=self.header 
    66.   
  
  
  
  66.         prenode=None 
    67.   
  
  
  
  67.         while tempnode!=None: 
    68.   
  
  
  
  68.             if tempnode.item==item: 
    69.   
  
  
  
  69.                 if tempnode==self.header: 
    70.   
  
  
  
  70.                     self.header=tempnode.next 
    71.   
  
  
  
  71.                 else: 
    72.   
  
  
  
  72.                     prenode.next=tempnode.next 
    73.   
  
  
  
  73.                 break 
    74.   
  
  
  
  74.             else: 
    75.   
  
  
  
  75.                 prenode=tempnode 
    76.   
  
  
  
  76.                 tempnode=tempnode.next 
    77.   
  
  
  
  77.  
    78.   
  
  
  
  78.  
    79.   
  
  
  
  79.     def deletebyindex(self,index): 
    80.   
  
  
  
  80.  
    81.   
  
  
  
  81.         if index>self.currentnum or index<=0: 
    82.   
  
  
  
  82.             raise IndexError("{} is not find in Linklist".format(index)) 
    83.   
  
  
  
  83.  
    84.   
  
  
  
  84.         i=1 
    85.   
  
  
  
  85.         tempnode=self.header 
    86.   
  
  
  
  86.         prenode=self.header 
    87.   
  
  
  
  87.  
    88.   
  
  
  
  88.         if index==1: 
    89.   
  
  
  
  89.             self.header = tempnode.next 
    90.   
  
  
  
  90.             self.currentnum-=1 
    91.   
  
  
  
  91.             return 
    92.   
  
  
  
  92.  
    93.   
  
  
  
  93.         while tempnode.next and i  
  
  
  
  94.             prenode = tempnode 
    95.   
  
  
  
  95.             tempnode = tempnode.next 
    96.   
  
  
  
  96.             i+=1 
    97.   
  
  
  
  97.  
    98.   
  
  
  
  98.         if i==index: 
    99.   
  
  
  
  99.             prenode.next=tempnode.next 
    100.   
  
  
  
  100.             self.currentnum-=1 
    101.   
  
  
  
  101.  
    102.   
  
  
  
  102.  
    103.   
  
  
  
  103.     def search(self,item): 
    104.   
  
  
  
  104.         tempnode=self.header 
    105.   
  
  
  
  105.         while tempnode!=None: 
    106.   
  
  
  
  106.             if tempnode.item==item: 
    107.   
  
  
  
  107.                 return True 
    108.   
  
  
  
  108.             else: 
    109.   
  
  
  
  109.                 tempnode=tempnode.next 
    110.   
  
  
  
  110.         return False 
    111.   
  
  
  
  111.  
    112.   
  
  
  
  112.     def update(self,index,item): 
    113.   
  
  
  
  113.         pass 
    114.   
  
  
  
  114.  
    115.   
  
  
  
  115.     def getitem(self,index): 
    116.   
  
  
  
  116.         if index<=0 or index>self.currentnum: 
    117.   
  
  
  
  117.             raise IndexError("{} is not find in Linklist".format(index)) 
    118.   
  
  
  
  118.         tempnode=self.header 
    119.   
  
  
  
  119.         i=1 
    120.   
  
  
  
  120.         while i  
  
  
  
  121.             tempnode=tempnode.next 
    122.   
  
  
  
  122.             i+=1 
    123.   
  
  
  
  123.         return tempnode.item 
    124.   
  
  
  
  124.  
    125.   
  
  
  
  125.     def getindex(self,item): 
    126.   
  
  
  
  126.         tempnode = self.header 
    127.   
  
  
  
  127.         i=0 
    128.   
  
  
  
  128.         flag=False 
    129.   
  
  
  
  129.         while tempnode != None: 
    130.   
  
  
  
  130.             i+=1 
    131.   
  
  
  
  131.             if tempnode.item == item: 
    132.   
  
  
  
  132.                 flag=True 
    133.   
  
  
  
  133.                 return i 
    134.   
  
  
  
  134.             else: 
    135.   
  
  
  
  135.                 tempnode = tempnode.next 
    136.   
  
  
  
  136.         if flag==False: 
    137.   
  
  
  
  137.             return 0 
    138.   
  
  
  
  138.  
    139.   
  
  
  
  139. if __name__ == '__main__': 
    140.   
  
  
  
  140.     a = SingleLinkList() 
    141.   
  
  
  
  141.     a.add(1)  # 1 
    142.   
  
  
  
  142.     print('a.add(1)') 
    143.   
  
  
  
  143.     a.travel() 
    144.   
  
  
  
  144.     a.add(2)  # 2 1 
    145.   
  
  
  
  145.     print('a.add(2)') 
    146.   
  
  
  
  146.     a.travel() 
    147.   
  
  
  
  147.     a.append(3)  # 2 1 3 
    148.   
  
  
  
  148.     print('a.append(3)') 
    149.   
  
  
  
  149.     a.travel() 
    150.   
  
  
  
  150.     a.insert(4, 2)  # 2 1 4 3 
    151.   
  
  
  
  151.     print('a.insert(2, 4)') 
    152.   
  
  
  
  152.     a.travel() 
    153.   
  
  
  
  153.     print('a.search(1)=',a.search(1)) 
    154.   
  
  
  
  154.     print('a.search(5)=', a.search(5)) 
    155.   
  
  
  
  155.     print('a.getindex(1)=',a.getindex(1)) 
    156.   
  
  
  
  156.     print('a.getindex(5)=', a.getindex(5)) 
    157.   
  
  
  
  157.     print('a.getitem(2)=', a.getitem(2)) 
    158.   
  
  
  
  158.     print('a.getitem(4)=', a.getitem(4)) 
    159.   
  
  
  
  159.     print('a.getitem(3)=', a.getitem(3)) 
    160.   
  
  
  
  160.     # a.deletebyitem(5) 
    161.   
  
  
  
  161.     # print('a.deletebyitem(5)') 
    162.   
  
  
  
  162.     # a.travel() 
    163.   
  
  
  
  163.     # a.deletebyitem(4) 
    164.   
  
  
  
  164.     # print('a.deletebyitem(4)') 
    165.   
  
  
  
  165.     # a.travel() 
    166.   
  
  
  
  166.     # a.deletebyitem(2) 
    167.   
  
  
  
  167.     # print('a.deletebyitem(2)') 
    168.   
  
  
  
  168.     # a.travel() 
    169.   
  
  
  
  169.     a.deletebyindex(4) 
    170.   
  
  
  
  170.     print('a.deletebyindex(4)') 
    171.   
  
  
  
  171.     a.travel() 
    172.   
  
  
  
  172.     a.deletebyindex(2) 
    173.   
  
  
  
  173.     print('a.deletebyindex(2)') 
    174.   
  
  
  
  174.     a.travel() 
    175.   
  
  
  
  175.     a.deletebyindex(1) 
    176.   
  
  
  
  176.     print('a.deletebyindex(1)') 
    177.   
  
  
  
  177.     a.travel() 
    178.

结果如下

 
 
 
 
      
  
  
  
  1. C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/linklist.py 
    2.   
  
  
  
  2. a.add(1) 
    3.   
  
  
  
  3. 1  
    4.   
  
  
  
  4. a.add(2) 
    5.   
  
  
  
  5. 2 1  
    6.   
  
  
  
  6. a.append(3) 
    7.   
  
  
  
  7. 2 1 3  
    8.   
  
  
  
  8. a.insert(2, 4) 
    9.   
  
  
  
  9. 2 4 1 3  
    10.   
  
  
  
  10. a.search(1)= True 
    11.   
  
  
  
  11. a.search(5)= False 
    12.   
  
  
  
  12. a.getindex(1)= 3 
    13.   
  
  
  
  13. a.getindex(5)= 0 
    14.   
  
  
  
  14. a.getitem(2)= 4 
    15.   
  
  
  
  15. a.getitem(4)= 3 
    16.   
  
  
  
  16. a.getitem(3)= 1 
    17.   
  
  
  
  17. a.deletebyindex(4) 
    18.   
  
  
  
  18. 2 4 1  
    19.   
  
  
  
  19. a.deletebyindex(2) 
    20.   
  
  
  
  20. 2 1  
    21.   
  
  
  
  21. a.deletebyindex(1) 
    22.   
  
  
  
  22. 1  
    23.   
  
  
  
  23.  
    24.   
  
  
  
  24. Process finished with exit code 0 
    25.

链表头部增加节点示意图

从链表尾部增加节点示意图

当前题目：Python数据结构之单链表
转载注明：http://www.36103.cn/qtweb/news19/719.html

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

广告

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

猜你还喜欢下面的内容

网站维护知识

各行业网站

成都全网营销　　 　眉山主机托管　　 　自适应网站设计　　 　成都网站制作　　 　营销型网站　　 　成都微信公众号开发　　 　小谭建站　　 　等级保护测评　　 　成都宣传海报　　 　网站推广　　 　企业网站设计　　 　微信小程序开发　　 　虚拟主机购买　　 　网站建设方案　　 　南充网站建设　　 　全网整合营销推广　　 　四川乐山服务器托管　　 　成都免费建网站　　 　店面门头广告　　 　广汉锦华橡塑