python编程语法基础笔记（4.10）(数据结构与算法)

在数据结构的学习中单链表是最基础且核心的线性表结构之一本文将结合代码实现详细拆解单链表的定义、核心操作及指针移动逻辑帮助彻底掌握单链表的底层原理。一、单链表的核心概念单链表单向链表由节点和链表头指针组成是一种非连续的存储结构其核心特征如下1. 节点结构每个节点包含两个核心域元素域item存放具体的业务数据如数字、字符串等链接域next存放「下一个节点」的内存地址指针是链表实现 “链式” 连接的核心链表最后一个节点的 next 指向 None表示链表结束。2. 头节点head链表的「头指针」指向链表的第一个节点。从 head 出发通过遍历每个节点的 next可以访问到链表中所有节点。3. 单链表的特点无需连续内存空间节点可分散存储访问节点需从头部遍历无法随机访问如不能直接通过索引获取节点增删节点只需修改指针指向效率高于数组无需移动大量元素。二、单链表的代码实现Python以下基于 Python 实现单链表的核心类及操作先定义「节点类」和「链表类」再实现判空、长度、遍历、增删改查等核心方法。1. 节点类SingleNodeclass SingleNode(object): def __init__(self, item): self.item item # 元素域存储数据 self.next None # 链接域初始指向None2. 链表类SingleLinkListclass SingleLinkList(object): def __init__(self, nodeNone): self.head node # 头指针默认指向None空链表三、单链表核心操作1. 判断链表是否为空is_empty逻辑只需判断头指针 head 是否指向 None。#2.1判断链表是否为空 def is_empty(self): #第一张判断方法 # if self.head is None: # return True # else: # return False #第二种判断方法 # return True if self.head is None else False #第三种方法 return self.head is None2. 计算链表长度length逻辑通过「游标cur」遍历链表每访问一个节点计数器 1直到游标指向 None。def length(self): cur self.head # 游标初始指向头节点 count 0 # 计数器初始为0 while cur is not None: count 1 cur cur.next # 游标移动到下一个节点 return count3. 遍历链表travel逻辑与计算长度逻辑一致遍历过程中打印节点的元素域。def travel(self): cur self.head while cur is not None: print(cur.item, end → ) cur cur.next print(None) # 标记链表结束4. 头部添加节点add核心先让新节点的 next 指向原头节点再将头指针指向新节点原链表 head → [2|next] → [3|None]添加新节点[1|None]步骤1new_node.next head → [1|next] → [2|next]步骤2head new_node → head → [1|next] → [2|next] → [3|None]def add(self, item): new_node SingleNode(item) # 创建新节点 new_node.next self.head # 新节点指向原头节点 self.head new_node # 头指针指向新节点5. 尾部添加节点append核心若链表为空直接让头指针指向新节点若不为空遍历到最后一个节点将其 next 指向新节点。原链表 head → [1|next] → [2|None]添加新节点[3|None]步骤1cur head遍历至cur.nextNonecur指向[2|None]步骤2cur.next new_node → [2|next] → [3|None]def append(self, item): new_node SingleNode(item) if self.is_empty(): # 空链表特殊处理 self.head new_node else: cur self.head while cur.next is not None: # 遍历到最后一个节点 cur cur.next cur.next new_node # 最后一个节点指向新节点6. 指定索引插入节点insert核心找到插入位置的「前驱节点」先让新节点指向前驱节点的下一个节点再让前驱节点指向新节点。原链表索引0:1索引1:2索引2:5head → [1|next] → [2|next] → [5|None]步骤1遍历找到索引1的节点前驱节点cur指向[2|next]步骤2new_node.next cur.next → [6|next] → [5|None]步骤3cur.next new_node → [2|next] → [6|next] → [5|None]def insert(self, index, item): if index 0 or index self.length(): raise IndexError(index out of range) if index 0: # 头部插入复用add方法 self.add(item) elif index self.length(): # 尾部插入复用append方法 self.append(item) else: cur self.head pre_index 0 while pre_index ! index - 1: # 找到前驱节点 cur cur.next pre_index 1 new_node SingleNode(item) new_node.next cur.next # 新节点指向前驱的下一个节点 cur.next new_node # 前驱节点指向新节点7. 删除指定值的节点remove核心遍历找到目标节点区分「目标节点是头节点」和「非头节点」两种情况修改前驱节点的 next 指向。原链表 head → [1|next] → [2|next] → [3|None]步骤1preNonecurhead遍历至cur.item2pre指向[1|next]cur指向[2|next]步骤2pre.next cur.next → [1|next] → [3|None]def remove(self, item): if self.is_empty(): raise IndexError(Cant delete empty list) cur self.head pre None # 记录前驱节点 while cur.item ! item: pre cur cur cur.next if cur is None: # 遍历完未找到目标节点 raise ValueError(f{item} not in list) if pre is None: # 目标节点是头节点 self.head cur.next else: # 目标节点是非头节点 pre.next cur.next8. 查找节点是否存在search逻辑遍历链表对比节点的元素域找到则返回 True否则返回 False。def search(self, item): if self.is_empty(): raise IndexError(Cant search empty list) cur self.head while cur is not None: if cur.item item: return True cur cur.next return False四、测试代码验证所有操作if __name__ __main__: # 初始化链表 link_list SingleLinkList() print(是否为空链表, link_list.is_empty()) # True print(链表长度, link_list.length()) # 0 # 尾部添加节点 link_list.append(1) link_list.append(2) link_list.append(5) link_list.travel() # 1 → 2 → 5 → None # 头部添加节点 link_list.add(4) link_list.travel() # 4 → 1 → 2 → 5 → None # 指定索引插入 link_list.insert(3, 6) link_list.travel() # 4 → 1 → 2 → 6 → 5 → None # 删除节点 link_list.remove(2) link_list.travel() # 4 → 1 → 6 → 5 → None # 查找节点 print(是否存在6, link_list.search(6)) # True print(是否存在2, link_list.search(2)) # False五、核心总结单链表的核心是「节点」和「指针」所有操作本质都是修改指针的指向遍历链表的通用逻辑通过游标 cur 从 head 出发逐次移动 cur cur.next 直到 None增删节点的关键新增节点先连后断避免丢失链表删除节点找到前驱节点修改其 next 指向特殊场景处理空链表、头节点 / 尾节点的增删需单独判断。