链表的知识总结

链式结构内存不连续的，而是一个个串起来的，每个链接表的节点保存一个指向下一个节点的指针。
⭐ 链式结构包含：node（节点）还有value（值），由于内存不连续的，那么对于数据的插入，只需找到一个节点便可以插入数据，这也是链表优于列表的一个优点，反之，对于数据的删除，由于不是连续的，不能通过索引删除数据，只能一一遍历删除元素。 ⭐ 接下来上代码 单链表的增删功能

1. # 定义一个结点的类
2. class Node():
3.     def __init__(self,value=None,next=None):
4.         self.next = next
5.         self.value = value
6.    
7.     def __str__(self):
8.         return "Node:{}".format(self.value)
10. # 定义一个连接点的类
11. class Linklist():
13.     def __init__(self):
14.         self.root = Node()
15.         self.size = 0
16.         self.next = None  # 增加新数据时，将信数据的地址与谁关联
18.     # 只要是追加 就要创造节点
19.     def append(self,value):
20.         node = Node(value)
21.         # 判断root节点下面是否有数据
22.         if not self.next: # 如果没有节点
23.             self.root.next = node  # 将新节点挂在root后面
24.         else:
25.             self.next.next = node  # 将新节点挂在最后一个节点上  
26.         self.next = node # 重新赋值 一开始的是None
27.         self.size += 1
28.    
29.     def append_first(self,value):
30.         # 只要是追加 就要创造节点
31.         node = Node(value)
32.         # 判断root下面是否存在节点
33.         if not self.next:
34.             self.root.next = node
35.             self.next = node
36.         else:
37.             temp = self.root.next # 获取原来root后面的那个节点
38.             self.root.next = node #  将新节点挂在root后面
39.             node.next = temp # 新的节点的下一个节点是原来的root的节点
40.    
41.     # 迭代链表
42.     def __iter__(self):
43.         # 获得root节点下面的数据
44.         current = self.root.next
45.         # 判断current是否有之 由于一开始赋予value和next没有值 所以进行判断 否则报错
46.         if current:
47.             # 判断时候有下一个节点 有的话则返回下一个结点的值
48.             while current is not self.next: # self.next可以列结成最后一个节点
49.                 yield current
50.                 current = current.next
51.             yield current
52.    
53.     # 查找数据
54.     def find(self,value):
55.         for n in self.__iter__():
56.             if n.value == value:
57.                 return n
58.    
59.     # 查找出现的次数
60.     def find_count(self,value):
61.         count = 0
62.         for n in self.__iter__():
63.             if n.value == value:
64.                 count += 1
65.         return count
66.    
67.     # 移除数据(链表的移除，需要逐一遍历，找到当前元素的节点，再删除)
68.     def remove(self,value):
69.         prve = self.root
70.         for n in self.__iter__():
71.             # 判断节点的值与要删除的值是否相等
72.             if n.value == value:
73.                 # 查看是不是最后一个节点
74.                 if n == self.next:
75.                     # 更新倒数第二节点的关系
76.                     prve.next = None
77.                     # 更新最后一个节点为原倒数第二个节点
78.                     self.next = prve
79.                 prve.next = None
80.                 # 删除当前节点
81.                 del n
82.                 # 链表大小减少
83.                 self.size -= 1
84.                 return True
85.             prve = n
86.    
87.     def remove_all(self,value):
88.         prve =self.root
89.         for n in self.__iter__():
90.             if n.value == value:
91.                 if n == self.next:
92.                     prve.next = None
93.                     self.next = prve
94.                 prve.next = n.next
95.                 # 删除当前节点
96.                 del n
97.                 # 链表大小减少
98.                 self.size -= 1
99.                 return True
100.             prve = n
102. if __name__ == "__main__":
103.     link = Linklist()
104.     link.append("孙悟空")   
105.     link.append("猪八戒")   
106.     link.append("孙悟空")   
107.     link.append("猪八戒")   
108.     link.append("猪八戒")   
109.     link.append("唐僧")   
110.     link.append_first("唐僧")
111.     link.append_first("唐僧")
112.     # for v in link:
113.     #     print(v)
114.     # print(link.find('孙悟空'))
115.     # print(link.find_count('唐僧'))  
117.     print("**************删除之前的数据******************")
118.     for v in link:
119.         print(v)
120.     link.remove('唐僧')
121.     link.remove('唐僧')
122.     link.remove('唐僧')
123.     link.remove('唐僧')
124.     link.remove('孙悟空')
125.     link.remove('猪八戒')
127.     link.remove_all("猪八戒")
128.     link.remove_all("孙悟空")
129.     link.remove_all("唐僧")     
131.     print("**************删除之后的数据******************")
132.     for v in link:
133.         print(v)        

复制代码

 
 
 
 ⭐ 接下来上代码 双链表的增删功能：

1. # 定义一个结点的类
2. class Node():
3.     def __init__(self,value=None,node=None,next=None):
4.         self.value = value
5.         self.node = node
6.         self.next = next
7.     def __str__(self):
8.         return "Node:{}".format(self.value)
9.    
10. # 定义一个连接点的类
11. class DoubleLinkedList():
12.     def __init__(self):
13.         self.root = Node()
14.         self.size = 0
15.         self.end = None
16.    
17.     def append(self,value):
18.         node = Node(value)
19.         # 判断root节点下面是否有数据
20.         if not self.end: # 如果没有元素
21.             self.root.next = node  # 将root 的下一个节点 设置为新的node节点
22.             node.prev = self.root  # 设置新节点的 上一个节点 为 root
23.         else:
24.             self.end.next = node  # 将原来最后节点的下一个节点 设置为新的node节点
25.             node.prev = self.end # 设置新节点的 上一个节点 为 原来的最后一个节点
26.         self.end = node # 更新最后 一个节点新加的node节点
27.         self.size += 1
28.    
29.     def append_first(self,value):
30.         node = Node(value) # 封装节点对象
31.         # 判断是否已经有数据
32.         if not self.end:# 如果没有元素
33.             self.end = node # 更新最后 一个节点新加的node节点
34.         else:
35.             # temp指向node，node指向root，root指向temp
36.             temp = self.root.next # 保存原来的第一个节点
37.             node.next = temp # 设置新节的下一个节为原来的 第一个节点
38.             temp.prev = node # 更新原来的第一个节点的上一个节点位置为 新的node节点
39.         node.prev = self.root # 设置新节点的 上一个节点 为 root
40.         self.root.next = node # 将root 的下一个节点 设置为新的node节点
41.         self.size += 1
43.     # 正序循环
44.     def __iter__(self):
45.         current = self.root.next
46.         if current:
47.             while current is not self.end:
48.                 yield current.value
49.                 current = current.next
50.             yield current.value
51.    
52.     # 倒叙循环
53.     def revers_iter(self):
54.         current  = self.end #获取最后一节点
55.         if current:
56.             while current is not self.root:
57.                 yield current
58.                 current = current.prev
60. if __name__ == "__main__":
61.     link = DoubleLinkedList()
62.     link.append('孙悟空')
63.     link.append('猪八戒')
64.     link.append_first('唐三藏')
66.     for v in link:
67.         print(v)
69.     print('-'*30)
71.     for v in link.revers_iter():
72.         print(v)
73.    
74.          

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！