说明
1、每个节点包括两个域、一个信息域(元素域)和一个连接域,该链接指向链接表的下一个节点,最后一个节点的链接指向空值。
2、表要素elem用于存储具体数据。链接域next用于存管下一个节点的位置
变量P指向链表头节点(首节点)的位置,可以从P出发找到表中的任意节点。
实例
class Node(object): def __init__(self, elem): """ :param elem: 表元素域 next:下一结点链接域 cursor(cur):游标 """ self.elem = elem # 定义next指向空 self.next = None class SingleLinkList(object): """ 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一一个节点,而最后-个节点的链接域则指向一个空值。 表元素域elem用来存放具体的数据。 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。 """ def __init__(self, node=None): self.__head = node # node.elem node.next def is_empty(self): """链表是否为空 """ return self.__head is None def length(self): """链表长度""" # cur游标,用来移动遍历节点 cur = self.__head count = 0 while cur is not None: count += 1 cur = cur.next # count 记录数量 return count def travel(self): """遍历整个链表""" cur = self.__head while cur is not None: print(cur.elem, end=' ') cur = cur.next def add(self, item): """链表头部添加元素:头插法""" node = Node(item) node.next = self.__head self.__head = node def append(self, item): """链表尾部添加元素:尾插法""" node = Node(item) # 下一结点链接域不为空 if self.is_empty(): self.__head = node else: cur = self.__head while cur.next is not None: cur = cur.next cur.next = node 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): """删除元素""" # 考虑删除头部、尾部、中间节点 cur = self.__head pre = None while cur is not None: if cur.elem == item: # 先判断是否是头节点 if cur == self.__head: self.__head = cur.next else: pre.next = cur.next break else: pre = cur cur = cur.next def search(self, item): """查找节点是否存在""" # 1. 创建游标 cur = self.__head # 2. 遍历游标 while cur is not None: # 3. cur.elem = item if cur.elem == item: return True else: cur = cur.next return False if __name__ == '__main__': ll = SingleLinkList() 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免费测试