在链表中插入节点是一个常见的操作，特别是在处理动态数据时。在单向链表中，我们可以在链表的开头（头部）、结尾（尾部）或指定位置插入新节点。以下是关于如何在Python中的单向链表中插入节点的详细解释和代码实现：
一、引言
链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组相比，链表在插入和删除操作上具有更高的灵活性，因为链表不需要预先分配连续的内存空间。在链表中插入节点时，我们需要确定插入的位置，并相应地更新节点的指针。
二、插入节点的类型
头部插入（Head Insertion）：在链表的开头插入新节点。这种插入方式的时间复杂度为O(1)，因为无论链表有多长，我们总是可以直接访问到头部节点。
尾部插入（Tail Insertion）：在链表的结尾插入新节点。这种插入方式需要遍历链表直到找到尾部节点，因此时间复杂度为O(n)，其中n是链表的长度。
指定位置插入（Indexed Insertion）：在链表的指定位置插入新节点。这种插入方式需要遍历链表直到找到指定位置的前一个节点，因此时间复杂度也是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 insert_at_head(self, data): new_node = Node(data) if not self.head: self.head = new_node else: new_node.next = self.head self.head = new_node # 尾部插入 def insert_at_tail(self, data): new_node = Node(data) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node # 指定位置插入 def insert_at_index(self, index, data): if index < 0: raise IndexError("Negative index") new_node = Node(data) if index == 0: self.insert_at_head(data) return current = self.head current_index = 0 while current and current_index < index - 1: current = current.next current_index += 1 if not current: raise IndexError("Index out of range") new_node.next = current.next current.next = new_node # 遍历链表并显示节点数据 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.insert_at_head(1) linked_list.insert_at_tail(2) linked_list.insert_at_index(1, 3) linked_list.display() # 输出: [1, 3, 2]
四、插入节点操作的详细解析
头部插入（insert_at_head）
·创建一个新节点new_node，并将其数据字段设置为要插入的数据。
·如果链表为空（即head为None），则将新节点设置为头节点。
·否则，将新节点的next指针指向当前的头节点，并将头节点指向新节点。这样，新节点就成为了新的头节点。
尾部插入（Tail Insertion）：在链表的结尾插入新节点。这种插入方式需要遍历链表直到找到尾部节点，因此时间复杂度为O(n)，其中n是链表的长度。
指定位置插入（Indexed Insertion）：在链表的指定位置插入新节点。这种插入方式需要遍历链表直到找到指定位置的前一个节点，因此时间复杂度也是O(n)。
