Python 中链表的基本操作“增删改查”可以通过定义一个 `Node` 类（节点）和一个 `LinkedList` 类（链表）来实现[ref_1]。虽然 Python 没有显式的指针概念，但通过对象的引用（`self.next`）可以完全模拟指针的功能来构建链表[ref_1][ref_3]。 ### 一、节点与链表的定义 链表的基础是节点，每个节点包含数据域（`data`）和指向下一个节点的引用（`next`）。 ```python class Node: """定义链表节点类""" def __init__(self, data): self.data = data # 节点存储的数据 self.next = None # 指向下一个节点的引用，初始为空 class SingleLinkedList: """定义单链表类""" def __init__(self): self.head = None # 链表头节点，初始为空链表 ``` ### 二、基本操作“增删改查”实现 以下将以 `SingleLinkedList` 类为基础，详细实现增、删、改、查操作。 #### 1. 查询操作 (Read/Check) 查询操作包括判断链表是否为空、获取链表长度、遍历打印以及查找特定元素是否存在。 ```python def is_empty(self): """判断链表是否为空""" return self.head is None def length(self): """获取链表的长度""" count = 0 current = self.head while current is not None: count += 1 current = current.next return count def travel(self): """遍历并打印整个链表""" current = self.head while current is not None: print(current.data, end=' -> ') current = current.next print('None') def search(self, item): """查找链表中是否存在值为item的节点""" current = self.head while current is not None: if current.data == item: return True current = current.next return False ``` #### 2. 增加操作 (Create/Insert) 增加操作根据插入位置的不同，可分为头部插入、尾部追加和指定位置插入[ref_3][ref_6]。 | 插入方法 | 描述 | 时间复杂度 | | :--- | :--- | :--- | | **头部插入** | 新节点成为新的头节点 | O(1) | | **尾部追加** | 新节点添加到链表末尾 | O(n) | | **指定位置插入** | 在指定索引位置插入新节点 | O(n) | ```python def add(self, item): """在链表头部添加节点（头插法）""" new_node = Node(item) new_node.next = self.head # 新节点指向原头节点 self.head = new_node # 更新头节点为新节点 def append(self, item): """在链表尾部追加节点（尾插法）""" new_node = Node(item) if self.is_empty(): # 如果链表为空，新节点即为头节点 self.head = new_node else: current = self.head while current.next is not None: # 移动到最后一个节点 current = current.next current.next = new_node # 最后一个节点的next指向新节点 def insert(self, pos, item): """在指定位置pos（从0开始）插入节点""" if pos <= 0: # 如果位置<=0，使用头插法 self.add(item) elif pos >= self.length(): # 如果位置超出链表长度，使用尾插法 self.append(item) else: new_node = Node(item) current = self.head for _ in range(pos - 1): # 移动到要插入位置的前一个节点 current = current.next # 调整节点引用关系 new_node.next = current.next current.next = new_node ``` #### 3. 删除操作 (Delete) 删除操作需要找到目标节点的前驱节点，修改其 `next` 引用以跳过目标节点[ref_4]。 ```python def remove(self, item): """删除第一个值为item的节点""" current = self.head prev = None # 用于记录当前节点的前一个节点 while current is not None: if current.data == item: # 找到要删除的节点 if prev is None: # 要删除的是头节点 self.head = current.next else: # 要删除的是中间或尾部节点 prev.next = current.next return True # 删除成功 # 未找到，继续向后移动 prev = current current = current.next return False # 链表中未找到该值，删除失败 ``` #### 4. 修改操作 (Update) 修改操作本质上是先查找到指定位置的节点，然后更新其数据域的值[ref_6]。 ```python def update(self, pos, new_item): """修改指定位置pos节点的值""" if pos < 0 or pos >= self.length(): raise IndexError("链表索引超出范围") current = self.head for i in range(pos): # 移动到目标位置节点 current = current.next current.data = new_item # 修改节点数据 ``` ### 三、完整示例与测试 将以上方法整合到 `SingleLinkedList` 类中，并进行功能测试。 ```python if __name__ == '__main__': # 1. 创建链表并测试“增” llist = SingleLinkedList() print("初始链表长度:", llist.length()) llist.append(10) # 尾部追加 llist.add(5) # 头部插入 llist.insert(1, 7) # 中间插入 print("插入元素后链表:") llist.travel() # 预期输出: 5 -> 7 -> 10 -> None # 2. 测试“查” print("链表是否为空:", llist.is_empty()) print("链表长度:", llist.length()) print("是否存在7:", llist.search(7)) print("是否存在99:", llist.search(99)) # 3. 测试“改” llist.update(1, 8) # 将位置1的节点值从7改为8 print("修改后链表:") llist.travel() # 预期输出: 5 -> 8 -> 10 -> None # 4. 测试“删” llist.remove(8) # 删除值为8的节点 print("删除8后链表:") llist.travel() # 预期输出: 5 -> 10 -> None llist.remove(5) # 删除头节点 print("删除5后链表:") llist.travel() # 预期输出: 10 -> None ``` ### 四、其他链表类型 以上实现的是最简单的**单向链表**。根据引用方向的不同，还有两种常见变体[ref_2][ref_4][ref_5]： | 链表类型 | 节点结构 | 特点 | 适用场景 | | :--- | :--- | :--- | :--- | | **单向链表** | `data`, `next` | 单向遍历，插入/删除需从头查找 | 简单数据序列，栈/队列实现 | | **双向链表** | `data`, `prev`, `next` | 可前向和后向遍历，删除操作更高效 | 需要频繁前向/后向遍历的场景 | | **循环链表** | `data`, `next` (尾指头) | 尾节点指向头节点，形成环 | 轮询调度、环形缓冲区 | 例如，一个简单的**双向链表**节点定义如下[ref_5]： ```python class DoublyNode: def __init__(self, data): self.data = data self.prev = None # 指向前驱节点的引用 self.next = None # 指向后继节点的引用 ``` **总结**：在 Python 中实现链表的增删改查，核心在于利用类属性（`self.next`）作为对象引用来模拟指针，从而串联各个节点。通过 `Node` 类和 `LinkedList` 类的封装，可以清晰、结构化地实现所有基本操作[ref_1][ref_6]。理解单向链表的实现是掌握更复杂的双向链表和循环链表的基础。在实际应用中，需要根据操作频次（如大量插入/删除）和遍历方向需求来选择合适的链表类型。