单链表的删除操作解析

# 1. 单链表的基本概念与实现

单链表作为一种常见的数据结构，在算法与数据结构中占据着重要的地位。本章将介绍链表的基本概念及实现方式。首先，我们会详细解释什么是链表，包括链表的定义、链表与数组的对比以及链表的种类。接着，我们将深入探讨单链表的实现，包括单链表节点结构、创建与插入操作以及遍历与查找操作。通过本章的内容，读者将对单链表有一个清晰的认识，为后续章节的学习打下坚实基础。在学习过程中，读者可以通过实例演示加深对单链表的理解，为进一步的内容做好铺垫。

# 2.1 删除节点的基本操作

在链表中，删除节点是一项基本操作，对应着删除操作的实现也是比较常见且重要的。通过本节的介绍，我们将深入了解如何完成链表中节点的删除操作，并分析其时间复杂度。

### 2.1.1 如何删除链表中的节点

删除链表中的节点主要涉及三个步骤：找到待删除节点、更新前驱节点指针、释放内存空间。首先需要遍历链表，找到目标节点，然后更新前一个节点的指针，使其指向待删除节点的下一个节点，最后释放待删除节点的内存空间。

def delete_node(self, value):
    cur = self.head
    pre = None
    while cur:
        if cur.val == value:
            if pre:
                pre.next = cur.next
            else:
                self.head = cur.next
            return
        pre = cur
        cur = cur.next

### 2.1.2 删除节点的时间复杂度分析

删除链表中的节点涉及遍历链表一次以定位目标节点，因此时间复杂度为O(n)，其中n为链表长度。值得注意的是，删除节点的过程中并未涉及数据的搬移，因此删除操作的时间复杂度相较于数组要低效得多。

### 2.1.3 实例演示：删除指定数值节点

假设给定链表为：1 -> 2 -> 3 -> 4 -> 5，我们要删除值为3的节点。按照上述删除节点的方法，找到值为3的节点后，更新指针，最终链表为：1 -> 2 -> 4 -> 5。

## 2.2 涉及删除的特殊情况

在实际应用中，除了基本的删除节点操作，还需要考虑特殊情况如何处理，例如删除头节点、尾节点或中间节点的操作流程。下面将对这些特殊情况进行详细讨论。

### 2.2.1 删除头节点的操作步骤

当需要删除头节点时，需将头节点指针指向下一个节点，然后释放原头节点的内存空间。

def delete_head(self):
    if self.head:
        self.head = self.head.next

### 2.2.2 删除尾节点的操作流程

对于尾节点的删除操作，需要先遍历找到尾节点的前一个节点，然后将其指针指向None，最后释放尾节点的内存空间。

def delete_tail(self):
    cur = self.head
    pre = None
    while cur.next:
        pre = cur
        cur = cur.next
    if pre:
        pre.next = None
    else:
        self.head = None

### 2.2.3 删除中间节点的处理方法

当需要删除中间节点时，同样需要遍历找到目标节点的前一个节点，更新指针连接至下一个节点，释放目标节点的内存空间。

def delete_middle(self, node):
    cur = self.head
    pre = None
    while cur:
        if cur == node: