定义：
链表是一种 线性数据结构，它由一系列 节点（nodes）组成，其中每个节点包含两个部分：
- 数据部分：存储节点的数据。
- 指针部分：存储指向下一个节点的地址。
链表种类
-
单向链表
- 定义：每个节点只包含一个指针部分，指向下一个节点。
- 特点：只能从头节点开始，逐步访问每个节点，最后到达尾节点，尾节点指向
null。 - 应用场景：简单队列、动态数据管理。
-
双向链表
- 定义：每个节点包含两个指针部分，分别指向前一个节点和下一个节点。
- 特点：可以从任意节点向前或向后访问，提供双向遍历能力。
- 应用场景：双端队列、复杂缓存机制。
-
循环链表
- 定义：链表的尾节点指向头节点，从而形成一个循环结构。
- 特点：遍历链表时可以无限循环，适合需要循环访问的场景。
- 应用场景：约瑟夫环问题、音乐播放器的循环播放列表。
-
带头节点的链表
- 定义：链表的第一个节点是一个虚拟节点（头节点），不存储实际数据，只作为链表的起点。
- 特点：头节点简化了对链表首部的操作（如插入和删除）。
- 应用场景：链表的边界操作统一化。
-
不带头节点的链表
- 定义：链表直接从存储实际数据的第一个节点开始，头节点也包含数据。
- 特点：实现简单，但需要特殊处理链表首部的插入或删除操作。
- 应用场景：小型或简单场景。
Python实现链表操作
通常需要定义一个 ListNode 类来表示链表的节点，并创建一系列的方法来操作链表（如插入、删除、查找、遍历等）。下面是常见的链表操作及其代码实现：
1. 定义链表节点
链表节点类通常包含两个属性：val（存储数据）和 next（指向下一个节点）。
class ListNode:def __init__(self, x):self.val = x # 存储数据self.next = None # 指向下一个节点
2. 创建链表
链表的创建可以通过逐个节点进行连接：
# 创建一个链表 1 -> 2 -> 3 -> 4 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
3. 遍历链表
遍历链表时，我们从头节点开始，依次访问每个节点。
def traverse_list(head):current = headwhile current:print(current.val, end=" -> ")current = current.nextprint("None")# 输出链表内容
traverse_list(head)
4. 插入节点
可以在链表的头部或尾部插入节点，也可以在指定位置插入节点。
在头部插入节点
def insert_at_head(head, value):new_node = ListNode(value)new_node.next = head # 新节点指向当前头节点return new_node # 新节点成为新的头节点# 在链表头部插入 0
head = insert_at_head(head, 0)
traverse_list(head) # 输出：0 -> 1 -> 2 -> 3 -> 4 -> None
在尾部插入节点
def insert_at_tail(head, value):new_node = ListNode(value)if not head:return new_nodecurrent = headwhile current.next:current = current.nextcurrent.next = new_nodereturn head # 返回修改后的链表头# 在链表尾部插入 5
head = insert_at_tail(head, 5)
traverse_list(head) # 输出：0 -> 1 -> 2 -> 3 -> 4 -> 5 -> None
在指定位置插入节点
def insert_at_position(head, value, position):new_node = ListNode(value)if position == 0:return insert_at_head(head, value)current = headindex = 0while current and index < position - 1:current = current.nextindex += 1if current: # 找到指定位置的前一个节点new_node.next = current.nextcurrent.next = new_nodereturn head# 在位置 2 插入 99
head = insert_at_position(head, 99, 2)
traverse_list(head) # 输出：0 -> 1 -> 99 -> 2 -> 3 -> 4 -> 5 -> None
5. 删除节点
删除指定值的节点
def delete_node(head, value):# 如果头节点的值就是要删除的值if head and head.val == value:return head.next # 删除头节点，返回头节点的下一个节点current = headwhile current and current.next:if current.next.val == value:current.next = current.next.next # 删除节点return headcurrent = current.nextreturn head # 如果未找到值，返回原链表# 删除值为 99 的节点
head = delete_node(head, 99)
traverse_list(head) # 输出：0 -> 1 -> 2 -> 3 -> 4 -> 5 -> None
6. 查找节点
查找链表中是否有某个值
def find_value(head, value):current = headwhile current:if current.val == value:return Truecurrent = current.nextreturn False# 查找链表中是否包含值 3
print(find_value(head, 3)) # 输出：True
print(find_value(head, 99)) # 输出：False
总结：
链表在 Python 中的基本操作包括创建、插入、删除、遍历、查找、反转和合并等。通过链表的节点指针可以灵活地进行各种操作，同时也能高效地进行插入和删除操作，特别是在链表的开头或中间插入删除时，比数组更加高效，因为链表不需要移动大量元素。
