python编程语法基础笔记（4.10）(数据结构与算法)
在数据结构的学习中，单链表是最基础且核心的线性表结构之一，本文将结合代码实现，详细拆解单链表的定义、核心操作及指针移动逻辑，帮助彻底掌握单链表的底层原理。
一、单链表的核心概念
单链表（单向链表）由节点和链表头指针组成，是一种非连续的存储结构，其核心特征如下：
1. 节点结构
每个节点包含两个核心域：
元素域（item）：存放具体的业务数据（如数字、字符串等）；
链接域（next）：存放「下一个节点」的内存地址（指针），是链表实现 “链式” 连接的核心；
链表最后一个节点的 next 指向 None，表示链表结束。
2. 头节点（head）
链表的「头指针」，指向链表的第一个节点。从 head 出发，通过遍历每个节点的 next，可以访问到链表中所有节点。
3. 单链表的特点
无需连续内存空间，节点可分散存储；
访问节点需从头部遍历，无法随机访问（如不能直接通过索引获取节点）；
增删节点只需修改指针指向，效率高于数组（无需移动大量元素）。
二、单链表的代码实现（Python）
以下基于 Python 实现单链表的核心类及操作，先定义「节点类」和「链表类」，再实现判空、长度、遍历、增删改查等核心方法。
1. 节点类（SingleNode）
class SingleNode(object): def __init__(self, item): self.item = item # 元素域：存储数据 self.next = None # 链接域：初始指向None2. 链表类（SingleLinkList）
class SingleLinkList(object): def __init__(self, node=None): 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]：
步骤1：new_node.next = head → [1|next] → [2|next]
步骤2：head = 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]：
步骤1：cur = head，遍历至cur.next=None（cur指向[2|None]）
步骤2：cur.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:5）：
head → [1|next] → [2|next] → [5|None]
步骤1：遍历找到索引1的节点（前驱节点，cur指向[2|next]）
步骤2：new_node.next = cur.next → [6|next] → [5|None]
步骤3：cur.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]
步骤1：pre=None，cur=head，遍历至cur.item=2（pre指向[1|next]，cur指向[2|next]）
步骤2：pre.next = cur.next → [1|next] → [3|None]
def remove(self, item): if self.is_empty(): raise IndexError("Can't 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("Can't 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 指向；
特殊场景处理：空链表、头节点 / 尾节点的增删需单独判断。