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