链表中删除节点

简介: 链表中删除节点

在链表中删除节点是另一个常见的操作。与插入节点类似,删除节点也可以有不同的方式,包括删除头部节点、删除尾部节点和删除指定位置的节点。

一、引言

链表是一种重要的数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。在链表中删除节点时,我们需要找到要删除的节点,并更新其前一个节点的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

·如果链表为空(即headNone),则抛出异常,因为无法删除不存在的节点。

·否则,将头指针head指向下一个节点

删除尾部节点(Tail Deletion):删除链表中的最后一个节点。这种删除方式需要遍历链表直到找到倒数第二个节点,因此时间复杂度为O(n),其中n是链表的长度。

删除指定位置的节点(Indexed Deletion):删除链表中指定位置的节点。这种删除方式需要遍历链表直到找到指定位置的前一个节点,因此时间复杂度也是O(n)。

相关文章
|
2月前
|
算法
【优选算法专栏】专题九:链表--------两两交换链表中的节点
【优选算法专栏】专题九:链表--------两两交换链表中的节点
26 0
|
2月前
|
存储 Python
链表中插入节点
链表中插入节点
|
2月前
|
存储 Python
删除链表节点详解
删除链表节点详解
|
29天前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
2月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
41 6
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
32 1
|
1月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
|
1月前
|
存储
删除链表的节点
删除链表的节点
16 0
|
1月前
|
存储 SQL 算法
|
1月前
|
SQL 算法 数据挖掘
力扣题目 19:删除链表的倒数第N个节点 【python】
力扣题目 19:删除链表的倒数第N个节点 【python】