第八节 单向循环链表简单介绍和python代码实现

  1 class Node():
  2     ‘‘‘节点类‘‘‘
  3     def __init__(self, elem):
  4         ‘‘‘节点的两个参数，本身值elem以及指向下一个节点的地址next‘‘‘
  5         self.elem = elem
  6         self.next = None
  7         # self.prev = None
  8 
  9 
 10 class SingCycleLinkList():
 11     ‘‘‘双链表‘‘‘
 12     def __init__(self, node = None):
 13         self.__head = node
 14         if node:
 15             node.next = node
 16 
 17     def sing_append(self, elem):
 18         ‘‘‘链表尾部添加元素‘‘‘
 19         node = Node(elem)
 20         if self.is_empty():
 21             self.__head = node
 22             node.next = node
 23         else:
 24             cur = self.__head
 25             while cur.next != self.__head:
 26                 cur = cur.next
 27             cur.next = node
 28             node.next = self.__head
 30 
 31     def is_empty(self):
 32         ‘‘‘判断链表是否为空，第一次传入数据以后self.__head将永远指向node1对象‘‘‘
 33         return self.__head is None
 34 
 35     def sing_length(self):
 36         ‘‘‘链表长度‘‘‘
 37         if self.is_empty():
 38             return 0
 39         cur = self.__head
 40         # 将第一个元素的node实例赋值给cur，
 41         count = 1
 42         while cur.next != self.__head:
 43             count+=1
 44             cur = cur.next
 45         return count
 46 
 47     def sing_travel(self):
 48         ‘‘‘遍历整个列表‘‘‘
 49         if self.is_empty():
 50             return
 51         cur = self.__head
 52         # 即将node1对象赋值给cur
 53         while cur.next != self.__head:
 54             print(cur.elem)
 55             cur = cur.next
 56         # 退出循环后最后一个节点不会再循环体内打印出来
 57         print(cur.elem)
 58 
 59     def sing_add(self, item):
 60         node = Node(item)
 61         if self.is_empty():
 62             self.__head = node
 63             node.next = node
 64             return
 65         cur = self.__head
 66         while cur.next != self.__head:
 67             cur = cur.next
 68         node.next = self.__head
 69         self.__head = node
 70         cur.next = node
 71 
 72     def sint_insert(self, pos, item):
 73         if pos <= 0:
 74             self.sing_add(item)
 75         elif pos > self.sing_length()-1:
 76             self.sing_append(item)
 77         else:
 78             cur = self.__head
 79             count = 0
 80             while count < pos:
 81                 count += 1
 82                 cur = cur.next
 83             node = Node(item)
 84             node.next = cur.next
 85             cur.next = node
 86 
 88     def sing_search(self,item):
 89         if self.is_empty():
 90             return False
 91         cur = self.__head
 92         while cur.next != self.__head:
 93             if item == cur.elem:
 94                 return True
 95             else:
 96                 cur = cur.next
 97         # 退出循环是判断尾结点
 98         if cur.elem == item:
 99             return True
100         return False
101 
102     def sing_remove(self, item):
103         if self.is_empty():
104             return
105         cur = self.__head
106         pre = None
107         while cur.next != self.__head:
108             if item == cur.elem:
109                 # 判断是否为头节点
110                 if cur == self.__head:
111                     rear = self.__head
112                     while rear.next != self.__head:
113                         rear = rear.next
114                     self.__head = cur.next
115                     rear.next = self.__head
116                 else:
117                     # 中间节点
118                     pre.next = cur.next
119                 return
120             else:
121                 pre = cur
122                 cur = cur.next
123         if cur.elem == item:
124             # 尾结点
125             if cur == self.__head:
126                 self.__head = None
127             else:
128                 pre.next = cur.next
129 
130 
131 if __name__ == "__main__":
132     ll = SingCycleLinkList()
133     ll.sing_append(1)
134     ll.sing_append(2)
135     # ll.sing_add(8)
136     ll.sing_append(3)
137     ll.sint_insert(-1,5)
138     ll.sing_travel()
139     print(ll.sing_search(5))
140     ll.sing_remove(5)
141     ll.sing_travel()