python 单向链表
1 # -*- coding: utf-8 -*-
2 # @author: Tele
3 # @Time : 2019/04/22 下午 3:17
4 # 单向链表的实现
5 # 每个节点包含两部分,数据区和指向下个节点的链接
6 # 单向列表:每个节点包含两部分:数据区与链接区(指向下一个节点),最后一个元素的链接区为None
7 # 单向列表只要找到头节点,就可以访问全部节点
8 class SingleNode: 9 def __init__(self, data, next=None): 10 self.data = data 11 # next指向下一个节点而不是数据
12 self.next = next 13
14
15 # 使用链表时只需要传入待存储的数据而不是节点
16 class SingleLinkedList: 17 def __init__(self, data=None): 18 node = SingleNode(data) 19 self.__head = node if node.data else None 20
21 def is_empty(self): 22 return self.__head == None 23
24 def length(self): 25 count = 0 26 cur = self.__head
27 while cur: 28 count += 1
29 cur = cur.next 30 return count 31
32 # 头部添加元素
33 def add(self, data): 34 node = SingleNode(data) 35 node.next = self.__head
36 self.__head = node 37
38 # 尾部添加元素
39 def append(self, data): 40 node = SingleNode(data) 41 if self.is_empty(): 42 self.__head = node 43 else: 44 cur = self.__head
45 # 最后一个节点的next为None
46 while cur.next: 47 cur = cur.next 48 cur.next = node 49
50 # 指定位置插入
51 def insert(self, pos, data): 52 node = SingleNode(data) 53 cur = self.__head
54 count = 0 55 if self.length() >= pos >= 0: 56 while cur: 57 if count + 1 == pos: 58 node.next = cur.next 59 cur.next = node 60 break
61 # pos为0
62 elif count == pos: 63 self.add(data) 64 break
65 count += 1
66 cur = cur.next 67 elif pos < 0: 68 self.add(data) 69 else: 70 self.append(data) 71 # 如果列表中插入时没有元素
72 if not self.__head: 73 self.append(data) 74
75 # 遍历
76 def travel(self): 77 cur = self.__head
78 while cur: 79 print(cur.data) 80 cur = cur.next 81
82 # 移除出现的第一个元素
83 def remove(self, data): 84 if self.is_empty(): 85 return
86 node = self.__find(data) 87 count = 0 88 cur = self.__head
89 while cur: 90 # 如果要移除的元素是头节点
91 if cur.data == node.data: 92 self.__head = cur.next 93 break
94 elif cur.next.data == node.data: 95 cur.next = node.next 96 break
97 count += 1
98 cur = cur.next 99
100 # 私有方法,用于查找节点
101 def __find(self, data): 102 cur = self.__head
103 node = SingleNode(data) 104 while cur: 105 if cur.data == data: 106 node.next = cur.next 107 break
108 cur = cur.next 109 return node 110
111 # 查找,找不到返回-1,找到则返回索引
112 def search(self, data): 113 index = -1
114 cur = self.__head
115 count = 0 116 while cur: 117 if cur.data == data: 118 index = count 119 break
120 count += 1
121 cur = cur.next 122 return index 123
124
125 def main(): 126 ssl = SingleLinkedList() 127 print(ssl.is_empty()) 128 print(ssl.length()) 129 # ssl.append(1)
130 # ssl.append(100)
131 # ssl.append(2)
132 # ssl.append(200)
133 # ssl.append(3)
134 # ssl.append(4)
135 print(ssl.is_empty()) 136 print(ssl.length()) 137
138 # 遍历
139 print("*" * 50) 140 # ssl.travel()
141
142 ssl.add(100) 143 # ssl.travel()
144 # 为负数时作为头节点
145 ssl.insert(-1, "sss") 146 ssl.travel() 147 print("*" * 50) 148 print(ssl.search("sss")) # 0
149 print("*" * 50) 150 ssl.remove(100) 151 ssl.travel() 152
153
154 if __name__ == '__main__': 155 main()
更多精彩
