[算法通关村] 1.2 链表的插入

**链表的插入**

在数据结构中，链表是一种常见的线性数据结构。它由一系列的结点组成，每个结点包含一个值和一个指向下一个结点的引用。在链表中，插入新元素是非常重要的一步操作。

**链表的基本概念**

首先，我们需要了解链表的基本概念：

* **结点（Node）**: 每个结点包含一个值和一个指向下一个结点的引用。
* **头结点（Head Node）**: 链表的第一个结点，通常作为链表的入口。
* **尾结点（Tail Node）**: 链表的最后一个结点。

**链表的插入**

现在，我们来讨论如何在链表中插入新元素。有两种常见的方法：

###1. 在头部插入在头部插入新元素时，我们需要将新元素作为头结点，并更新所有其他结点的引用。

**示例代码**

class Node:
 def __init__(self, value):
 self.value = value self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def insert_at_head(self, value):
 new_node = Node(value)
 if self.head is None:
 self.head = new_node else:
 new_node.next = self.head self.head = new_node# 创建一个链表linked_list = LinkedList()

# 在头部插入新元素linked_list.insert_at_head(5)

# 打印链表中的值while linked_list.head is not None:
 print(linked_list.head.value)
 linked_list.head = linked_list.head.next

class Node:
 def __init__(self, value):
 self.value = value self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def insert_at_tail(self, value):
 new_node = Node(value)
 if self.head is None:
 self.head = new_node else:
 current_node = self.head while current_node.next is not None:
 current_node = current_node.next current_node.next = new_node# 创建一个链表linked_list = LinkedList()

# 在尾部插入新元素linked_list.insert_at_tail(5)

# 打印链表中的值current_node = linked_list.headwhile current_node is not None:
 print(current_node.value)
 current_node = current_node.next

class Node:
 def __init__(self, value):
 self.value = value self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def insert_at_position(self, position, value):
 new_node = Node(value)
 if position ==0:
 new_node.next = self.head self.head = new_node else:
 current_node = self.head for _ in range(position -1):
 current_node = current_node.next new_node.next = current_node.next current_node.next = new_node# 创建一个链表linked_list = LinkedList()

# 在任意位置插入新元素linked_list.insert_at_position(2,5)

# 打印链表中的值current_node = linked_list.headwhile current_node is not None:
 print(current_node.value)
 current_node = current_node.next