在链表中删除节点是另一个常见的操作。与插入节点类似，删除节点也可以有不同的方式，包括删除头部节点、删除尾部节点和删除指定位置的节点。
一、引言
链表是一种重要的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在链表中删除节点时，我们需要找到要删除的节点，并更新其前一个节点的next指针，或者如果删除的是头部节点，则需要更新头指针。
二、删除节点的类型
删除头部节点（Head Deletion）：删除链表中的第一个节点。这种删除方式的时间复杂度为O(1)，因为我们可以直接访问到头部节点。
删除尾部节点（Tail Deletion）：删除链表中的最后一个节点。这种删除方式需要遍历链表直到找到倒数第二个节点，因此时间复杂度为O(n)，其中n是链表的长度。
删除指定位置的节点（Indexed Deletion）：删除链表中指定位置的节点。这种删除方式需要遍历链表直到找到指定位置的前一个节点，因此时间复杂度也是O(n)。
三、代码实现
1. 节点类（Node）
首先，我们定义一个节点类，用于表示链表中的每个节点。节点类通常包含两个属性：一个用于存储数据的数据字段和一个用于指向下一个节点的指针字段。
python复制代码
class Node: def __init__(self, data=None): self.data = data self.next = None
2. 链表类（LinkedList）
接下来，我们定义一个链表类，用于表示整个链表。链表类包含一个指向头节点的指针（head），以及一系列用于操作链表的方法（如删除头部节点、删除尾部节点和删除指定位置的节点等）。
python复制代码
class LinkedList: def __init__(self): self.head = None # 删除头部节点 def delete_head(self): if not self.head: raise IndexError("List is empty") self.head = self.head.next # 删除尾部节点 def delete_tail(self): if not self.head: raise IndexError("List is empty") if not self.head.next: self.head = None return current = self.head while current.next.next: current = current.next current.next = None # 删除指定位置的节点 def delete_at_index(self, index): if index < 0: raise IndexError("Negative index") if not self.head: raise IndexError("List is empty") if index == 0: self.delete_head() return current = self.head current_index = 0 while current and current_index < index - 1: current = current.next current_index += 1 if not current or not current.next: raise IndexError("Index out of range") current.next = current.next.next # 遍历链表并显示节点数据 def display(self): elements = [] current_node = self.head while current_node: elements.append(current_node.data) current_node = current_node.next print(elements) # 使用链表 linked_list = LinkedList() linked_list.head = Node(1) second = Node(2) third = Node(3) linked_list.head.next = second second.next = third linked_list.display() # 输出: [1, 2, 3] # 删除头部节点 linked_list.delete_head() linked_list.display() # 输出: [2, 3] # 删除尾部节点 linked_list.delete_tail() linked_list.display() # 输出: [2] # 删除指定位置的节点（索引为0） linked_list.delete_at_index(0) linked_list.display() # 输出: []
四、删除节点操作的详细解析
删除头部节点（delete_head）
·如果链表为空（即head为None），则抛出异常，因为无法删除不存在的节点。
·否则，将头指针head指向下一个节点
删除尾部节点（Tail Deletion）：删除链表中的最后一个节点。这种删除方式需要遍历链表直到找到倒数第二个节点，因此时间复杂度为O(n)，其中n是链表的长度。
删除指定位置的节点（Indexed Deletion）：删除链表中指定位置的节点。这种删除方式需要遍历链表直到找到指定位置的前一个节点，因此时间复杂度也是O(n)。
