数据结构与算法 / 系统课时

单链表的插入与删除

单链表的插入与删除

单链表插入和删除的核心不是移动元素,而是重新连接节点引用。本课将用一个链表类处理头部、尾部和中间位置,重点保证原后继不会丢失,并统一校验索引与维护长度。

学习目标

  • 掌握按位置插入和删除节点
  • 理解引用修改顺序与节点可达性的关系
  • 分析定位节点和修改连接的复杂度

引用修改规则

在前驱 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)。

python
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()

预期输出:

text
[10, 20, 30, 40]
20
[10, 30, 40]
3

复杂度与易错点

定位第 index 个节点需要从头遍历,成本为 O(n);找到前驱后,真正修改连接只需常数次赋值,是 O(1)。若额外维护 tail,尾部追加可降为 O(1),但删除尾节点仍需寻找前驱。

常见错误包括先覆盖 prev.next 导致原后继丢失、忘记更新 size、把删除位置 size 误判为合法,以及头部操作仍尝试访问不存在的前驱。删除后将 removed.next 设为 None 不是结构正确性的必要条件,但便于调试并减少误用旧节点的风险。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

单链表的插入与删除

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通