链表操作

链表操作是数据结构与算法中的核心基础内容，它通过节点间的动态链接实现高效的数据存储与操作。本文将系统讲解链表的基本概念、操作实现、应用场景及常见问题。

链表简介

链表（Linked List）是一种线性数据结构，由一系列节点（Node）通过指针（或引用）连接而成。与数组不同，链表的内存分配是动态的，节点可以分散在内存中的任意位置。链表的类型包括：

• 单链表（Singly Linked List）：每个节点包含数据和指向下一个节点的指针。
• 双链表（Doubly Linked List）：节点额外包含指向前一个节点的指针。
• 循环链表（Circular Linked List）：尾节点指向头节点形成环。

基本结构

graph LR A[Data|Next] --> B[Data|Next] --> C[Data|Next] --> D[Null]

• 单链表节点结构：

  
class Node:  
    def __init__(self, data):  
        self.data = data  
        self.next = None

基本操作

以下是链表的五种核心操作及其实现。

1. 遍历链表

遍历链表即按顺序访问每个节点。

  
def traverse(head):  
    current = head  
    while current is not None:  
        print(current.data, end=" -> ")  
        current = current.next  
    print("None")

示例输入/输出： 输入：`1 -> 2 -> 3 -> None` 输出：`1 -> 2 -> 3 -> None`

2. 插入节点

插入操作分为头部、中间和尾部插入。

头部插入

  
def insert_at_head(head, data):  
    new_node = Node(data)  
    new_node.next = head  
    return new_node

尾部插入

  
def insert_at_tail(head, data):  
    new_node = Node(data)  
    if head is None:  
        return new_node  
    current = head  
    while current.next is not None:  
        current = current.next  
    current.next = new_node  
    return head

3. 删除节点

删除指定值的节点：

  
def delete_node(head, key):  
    if head is None:  
        return None  
    if head.data == key:  
        return head.next  
    current = head  
    while current.next is not None:  
        if current.next.data == key:  
            current.next = current.next.next  
            return head  
        current = current.next  
    return head

4. 反转链表

反转链表是常见面试题，需调整指针方向：

  
def reverse_list(head):  
    prev = None  
    current = head  
    while current is not None:  
        next_node = current.next  
        current.next = prev  
        prev = current  
        current = next_node  
    return prev

复杂度分析：时间复杂度为$O(n)$，空间复杂度为$O(1)$。

实际应用案例

1. 操作系统：内存管理中的空闲块链表。 2. 浏览器历史记录：使用双链表实现前进/后退功能。 3. LRU缓存：结合哈希表与双链表实现高效淘汰策略。

常见问题与优化

• 问题：单链表无法快速访问前驱节点。
• 解决方案：使用双链表或维护额外指针。
• 边界条件：处理空链表、单节点链表等特殊情况。

总结

链表操作是算法设计的基石，掌握其核心逻辑（如指针操作）对解决复杂问题（如合并链表、检测环）至关重要。建议通过LeetCode等平台练习相关题目以巩固知识。