链表

链表结构

class Node: def __init__(self, item, next_): self.item = item # 数据域 self.next_ = next_ # 指针域（指向下一个节点） class LinkList: # 初始化 def __init__(self): # 初始化头结点 self.head: Node = Node(None, None) # 初始化链表长度 self.length: int = 0 # 清空链表 def clear(self): self.head.next_ = None self.length = 0 # 获取长度 def get_length(self) -> int: return self.length # 判断链表是否为空 def is_empty(self): return self.length == 0 # 获取指定位置的元素 def get_item(self, index): node_t: Node = self.head.next_ # 从头结点开始 for i in range(index): node_t = node_t.next_ # 依次向后跳index次即可 return node_t.item # 追加元素 def append(self, item): # 找到最后一个节点 node_t: Node = self.head while node_t.next_ is not None: # 循环查找直到指针域为空为最后节点 node_t = node_t.next_ # 创建新节点，保存元素 node_new: Node = Node(item, None) # 最后一个节点指向新节点 node_t.next_ = node_new # 长度+1 self.length += 1 # 任意位置插入元素 def insert(self, item, index): node_pre: Node = self.head.next_ # 找到插入位置的前一个节点 for i in range(index - 1): # 向后跳index-1次即可 node_pre = node_pre.next_ # 找到插入位置的节点 node_curr = node_pre.next_ # 创建新节点，指向插入位置的节点 node_new: Node = Node(item, node_curr) # 插入位置的前一个节点指向新节点 node_pre.next_ = node_new # 长度+1 self.length += 1 # 删除指定位置的元素，返回该元素 def delete(self, index): # 找到当前位置的前一个节点 node_pre: Node = self.head for i in range(index - 1): node_pre = node_pre.next_ # 找到当前位置的节点 node_curr: Node = node_pre.next_ # 找到当前位置的后一个节点 node_next: Node = node_curr.next_ # 将前一个节点的指针指向后一个节点 node_pre.next_ = node_next # 长度-1 self.length -= 1 return node_curr.item # 查找元素的位置 def get_index(self, item): # 从头节点开始遍历每一个节点，比较item node_t: Node = self.head # 记录位置 index = 0 while node_t.next_ is not None: node_t = node_t.next_ # 节点后跳 if node_t.item == item: return index index += 1 # 计数+1 return -1 # 遍历打印链表 def show_items(self): node_t: Node = self.head if self.length > 0: while node_t.next_ is not None: node_t = node_t.next_ print(node_t.item, end=' ') print() else: print('empty') # 反转全部节点 def reverse(self): # 判断是否为空链表 if self.is_empty(): return else: self.reverse_node(self.head.next_) # 从头节点的下一个节点开始反转 # 反转单个节点 def reverse_node(self, curr: Node): # 递归出口, 遍历到最后一个节点时，不需要继续反转curr的下一个节点 if curr.next_ is None: # 如果递归遍历到最后一个节点 self.head.next_ = curr # 头节点指向最后一个节点 return curr # 返回反转后的节点 # 需要将当前节点的下一个节点反转 # 递归反转curr的下一个节并返回 pre = self.reverse_node(curr.next_) # 反转后的节点指向当前节点，反转后的节点在前，当前节点在后 pre.next_ = curr # 当前节点在后，指针域为空 curr.next_ = None # 返回反转后的节点 return curr if __name__ == '__main__': link = LinkList() link.append('node1') link.append('node2') link.append('node3') link.show_items() link.insert('insert item', 2) link.show_items() print(link.get_index('node3')) print(link.get_item(2)) print(link.delete(1)) link.show_items() link.reverse() link.show_items() print(link.is_empty()) link.clear() print(link.is_empty())