数据结构与算法 / 系统课时
单链表的插入与删除
单链表的插入与删除
单链表插入和删除的核心不是移动元素,而是重新连接节点引用。本课将用一个链表类处理头部、尾部和中间位置,重点保证原后继不会丢失,并统一校验索引与维护长度。
学习目标
- 掌握按位置插入和删除节点
- 理解引用修改顺序与节点可达性的关系
- 分析定位节点和修改连接的复杂度
引用修改规则
在前驱 prev 后插入 new_node 时,应先执行 new_node.next = prev.next 保存原后继,再执行 prev.next = new_node 让前驱接入新节点。
删除 prev 后的目标节点时,先用 removed = prev.next 保存目标,再执行 prev.next = removed.next,让前驱直接跨过目标节点。
头部没有真实前驱,因此插入和删除都需要直接更新 head。这些操作的先后关系决定后半段链表是否仍然可达。

索引边界
若链表长度为 size,插入位置允许 0 <= index <= size。index = 0 表示头部插入,index = size 表示尾部追加。
删除位置只允许 0 <= index < size,因为最后一个有效节点下标是 size - 1。公开方法应先完成边界检查,再调用内部定位方法,避免在多个位置重复处理非法输入。
主示例
下面的实现维护 head 和 size。按位置操作需要先找到前驱节点,因此整体最坏复杂度为 O(n)。
from dataclasses import dataclass
from typing import Optional
@dataclass
class ListNode:
value: int
next: Optional["ListNode"] = None
class SinglyLinkedList:
def __init__(self) -> None:
self.head: Optional[ListNode] = None
self.size = 0
def insert(self, index: int, value: int) -> None:
if index < 0 or index > self.size:
raise IndexError("插入位置越界")
new_node = ListNode(value)
if index == 0:
new_node.next = self.head
self.head = new_node
else:
prev = self._node_at(index - 1)
# 先保留原后继,再让前驱接入新节点
new_node.next = prev.next
prev.next = new_node
self.size += 1
def delete(self, index: int) -> int:
if index < 0 or index >= self.size:
raise IndexError("删除位置越界")
if index == 0:
assert self.head is not None
removed = self.head
self.head = removed.next
else:
prev = self._node_at(index - 1)
assert prev.next is not None
removed = prev.next
prev.next = removed.next
removed.next = None
self.size -= 1
return removed.value
def _node_at(self, index: int) -> ListNode:
current = self.head
for _ in range(index):
assert current is not None
current = current.next
assert current is not None
return current
def to_list(self) -> list[int]:
result: list[int] = []
current = self.head
while current is not None:
result.append(current.value)
current = current.next
return result
def main() -> None:
linked = SinglyLinkedList()
linked.insert(0, 20)
linked.insert(0, 10)
linked.insert(2, 40)
linked.insert(2, 30)
print(linked.to_list())
print(linked.delete(1))
print(linked.to_list())
print(linked.size)
if __name__ == "__main__":
main()预期输出:
[10, 20, 30, 40]
20
[10, 30, 40]
3复杂度与易错点
定位第 index 个节点需要从头遍历,成本为 O(n);找到前驱后,真正修改连接只需常数次赋值,是 O(1)。若额外维护 tail,尾部追加可降为 O(1),但删除尾节点仍需寻找前驱。
常见错误包括先覆盖 prev.next 导致原后继丢失、忘记更新 size、把删除位置 size 误判为合法,以及头部操作仍尝试访问不存在的前驱。删除后将 removed.next 设为 None 不是结构正确性的必要条件,但便于调试并减少误用旧节点的风险。