Python中链表的插入和删除操作详解
链表是一种常见的数据结构，其中每个节点包含数据和指向下一个节点的指针。Python中可使用类或字典等方式实现链表。以下是链表的插入和删除操作的详细解释和示例代码。
- 插入操作
链表插入操作往往需要指定插入位置和插入的数据。以下是在链表末尾插入新节点的示例代码：
class Node: def __init__(self, data=None): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node
上述代码中，我们定义了两个类：Node和LinkedList。Node类表示链表中的节点，包含数据部分和指向下一个节点的指针。LinkedList类则表示整个链表，并提供了一个方法append()，将数据插入到链表末尾。
如果链表为空（即self.head为None），则直接将新节点作为头节点。否则，从头节点开始遍历到链表末尾的最后一个节点，将新节点插入末尾。
以下是将新节点插入链表中间位置的示例代码：
class LinkedList: # 如上方定义 def insert(self, prev_node, data): if not prev_node: print("Previous node is not in the list") return new_node = Node(data) new_node.next = prev_node.next prev_node.next = new_node
在insert()方法中，我们需要指定插入位置——即要插入节点的前一个节点。如果前一个节点不存在（即prev_node为None），则打印错误信息并返回。否则，创建一个新节点，将其next指针指向prev_node的下一个节点，再将prev_node的next指针指向新节点，即完成插入操作。
以下是插入“pidancode.com”节点到头节点后面的示例代码：
linked_list = LinkedList() linked_list.head = Node("笔记") node2 = Node("应用") node3 = Node("教程") linked_list.head.next = node2 node2.next = node3 new_node = Node("pidancode.com") new_node.next = linked_list.head.next linked_list.head.next = new_node # 输出链表 curr_node = linked_list.head while curr_node: print(curr_node.data) curr_node = curr_node.next
输出：
笔记 pidancode.com 应用 教程
- 删除操作
链表的删除操作同样需要指定节点位置。以下是删除链表中某个节点的示例代码：
class LinkedList: # 如上方定义 def delete_node(self, key): curr_node = self.head if curr_node and curr_node.data == key: self.head = curr_node.next curr_node = None return prev_node = None while curr_node and curr_node.data != key: prev_node = curr_node curr_node = curr_node.next if curr_node is None: return prev_node.next = curr_node.next curr_node = None
在delete_node()方法中，我们遍历链表，找到要删除的节点并将其从中删除。首先判断头节点是否为要删除节点，如果是，则将头节点指向下一个节点。如果不是，再遍历到对应节点并删除。
以下是删除“皮蛋编程”节点的示例代码：
linked_list = LinkedList() linked_list.head = Node("笔记") node2 = Node("应用") node3 = Node("皮蛋编程") linked_list.head.next = node2 node2.next = node3 linked_list.delete_node("皮蛋编程") # 输出链表 curr_node = linked_list.head while curr_node: print(curr_node.data) curr_node = curr_node.next
输出：
笔记 应用
通过以上示例代码，我们可以学会链表的插入和删除操作，这是学习Python数据结构和算法的重要基础之一。
相关文章