说明
1、当实例化一个单向循环链表时,该链表是一个空链表,在将节点依次链接之后,链表中才会出现节点和数据。
2、在链表中,为了找到链表的某个节点,需要从链表的头节点开始,依次搜索。
因此,在实例单向循环链表中,必须定义链表的头。当添加头节点时,链表的头指向头节点。
实例
class Node(object): def __init__(self, elem): """ :param elem: 表元素域 next:下一结点链接域 cursor(cur):游标 """ self.elem = elem # 定义next指向空 self.next = None class SingleCircularLinkList(object): """ 单向循环链表:单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为none,而是指向链表的头节点 """ def __init__(self, node=None): self.__head = node # node.elem node.next if node: node.next = node def is_empty(self): """链表是否为空 """ return self.__head is None def length(self): """链表长度""" if self.is_empty(): return 0 # cur游标,用来移动遍历节点 cur = self.__head count = 1 while cur.next != self.__head: count += 1 cur = cur.next # count 记录数量 return count def travel(self): """遍历整个链表""" if self.is_empty(): return cur = self.__head while cur.next != self.__head: print(cur.elem, end=' ') cur = cur.next # 退出循环,cur指向尾结点,但尾节点的元素未打印 print(cur.elem) def add(self, item): """链表头部添加元素:头插法""" node = Node(item) if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next # 退出循环,cur指向尾结点 node.next = self.__head self.__head = node # 方式1:cur.next = node cur.next = self.__head # 方式2 def append(self, item): """链表尾部添加元素:尾插法""" node = Node(item) # 下一结点链接域不为空 if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next # 方式1: # node.next = cur.next # cur.next = node # 方式2: cur.next = node node.next = self.__head def insert(self, pos, item): """ pos: pos从0开始 pre:指定节点前一节点,相当于游标 node:插入的指定节点 指定位置添加元素 """ # if pos<=0 头插法 if pos <= 0: self.add(item) # elif pos>(self.length()-1) 尾插法 elif pos > (self.length() - 1): self.append(item) # else 插入法 else: pre = self.__head count = 0 # 当循环退出后,pre指向pos-1 while count < (pos - 1): count += 1 pre = pre.next node = Node(item) node.next = pre.next pre.next = node def remove(self, item): """删除元素""" # 考虑删除头部、尾部、中间节点 if self.is_empty(): return cur = self.__head pre = None while cur.next != self.__head: if cur.elem == item: # 先判断是否是头节点 if cur == self.__head: # 找到尾节点 rear = self.__head while rear.next != self.__head: rear = rear.next self.__head = cur.next rear.next = self.__head else: # 中间节点 pre.next = cur.next return else: pre = cur cur = cur.next # 退出循环,cur指向尾结点 if cur.elem == item: if cur == self.__head: # 链表只有一个节点 self.__head = None else: pre.next = cur.next def search(self, item): """查找节点是否存在""" if self.is_empty(): return False # 1. 创建游标 cur = self.__head # 2. 遍历游标 while cur.next != self.__head: # 3. cur.elem = item if cur.elem == item: return True else: cur = cur.next # 对于最后一个元素或只有一个元素 if cur.elem == item: return True return False if __name__ == '__main__': ll = SingleCircularLinkList() ll.is_empty() l1 = ll.length() print(l1) ll.append(55) ll.is_empty() l2 = ll.length() print(l2) ll.append(2) ll.add(8) ll.append(3) ll.append(4) ll.append(5) # 55 1 8 2 3 4 ll.insert(-1,9) # 9 8 55 2 1 8 2345 ll.insert(2,100) #9 8 100 55 2 1 8 2345 ll.travel()
神龙|纯净稳定代理IP免费测试>>>>>>>>天启|企业级代理IP免费测试>>>>>>>>IPIPGO|全球住宅代理IP免费测试