编辑“︁单向链表（Singly Linked List）”︁

{{Note|本文适用于编程初学者及需要巩固线性数据结构基础的程序员。所有示例均提供可运行的代码及分步解析。}}

= 单向链表（Singly Linked List） =
'''单向链表'''是一种线性数据结构，由一系列通过指针单向连接的节点组成。每个节点包含两个部分：存储数据的'''数据域'''和指向下一个节点的'''指针域'''。与数组不同，链表在内存中非连续存储，因此能高效处理动态数据操作。

== 核心特性 ==
* '''单向性'''：节点仅指向后继节点（无前驱指针）
* '''动态大小'''：运行时自由增删节点
* '''O(1)插入/删除'''：在已知位置操作时效率高于数组
* '''O(n)随机访问'''：必须从头节点开始顺序查找

<mermaid>
graph LR
    A[Head] --> B[Data|Next]
    B --> C[Data|Next]
    C --> D[Data|Next]
    D --> E[Null]
</mermaid>

== 节点结构 ==
用伪代码表示节点结构：
<syntaxhighlight lang="python">
class Node:
    def __init__(self, data):
        self.data = data  # 数据域
        self.next = None  # 指针域
</syntaxhighlight>

== 基本操作 ==
=== 1. 创建链表 ===
<syntaxhighlight lang="java">
// Java实现
public class LinkedList {
    Node head;  // 头节点

    static class Node {
        int data;
        Node next;
        Node(int d) { data = d; }
    }
}
</syntaxhighlight>

=== 2. 插入操作 ===
{| class="wikitable"
|-
! 插入位置 !! 时间复杂度 !! 代码示例
|-
| 头部 || O(1) || 
<syntaxhighlight lang="c">
void push(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
</syntaxhighlight>
|-
| 尾部 || O(n) || 
<syntaxhighlight lang="python">
def append(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return
    last = self.head
    while last.next:
        last = last.next
    last.next = new_node
</syntaxhighlight>
|-
| 指定位置 || O(n) || 
<syntaxhighlight lang="javascript">
insertAfter(prev_node, new_data) {
    if (prev_node === null) return;
    let new_node = new Node(new_data);
    new_node.next = prev_node.next;
    prev_node.next = new_node;
}
</syntaxhighlight>
|}

=== 3. 删除操作 ===
<syntaxhighlight lang="cpp">
void deleteNode(Node** head_ref, int key) {
    Node *temp = *head_ref, *prev;
    
    // 删除头节点
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    // 查找要删除的节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}
</syntaxhighlight>

== 实际应用案例 ==
'''浏览器历史记录'''：使用单向链表实现"前进"功能（虽然需双向链表实现完整前进后退，但简化版本可用单向链表）：
<syntaxhighlight lang="python">
class BrowserHistory:
    def __init__(self, homepage):
        self.current = Node(homepage)
    
    def visit(self, url):
        new_page = Node(url)
        new_page.next = self.current
        self.current = new_page
    
    def back(self, steps):
        while steps > 0 and self.current.next:
            self.current = self.current.next
            steps -= 1
        return self.current.data
</syntaxhighlight>

== 复杂度分析 ==
{| class="wikitable"
|-
! 操作 !! 时间复杂度 !! 空间复杂度
|-
| 访问 || O(n) || O(1)
|-
| 搜索 || O(n) || O(1)
|-
| 插入 || O(1)（头插） / O(n)（其他） || O(1)
|-
| 删除 || O(1)（头删） / O(n)（其他） || O(1)
|}

== 进阶技巧 ==
'''快慢指针法'''（检测环/找中点）：
<syntaxhighlight lang="python">
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
</syntaxhighlight>

'''数学表示'''：
链表长度计算：
<math>
L = \sum_{i=1}^{n} \mathbb{I}(node_i \neq \text{null})
</math>
其中<math>\mathbb{I}</math>为指示函数。

== 常见问题 ==
* '''内存泄漏'''：删除节点后未释放内存（C/C++）
* '''野指针'''：未正确设置next指针为null
* '''边界条件'''：处理空链表/单节点链表时的特殊情况

{{Warning|在并发环境下操作链表需加锁，否则可能导致指针错乱。}}

== 练习题 ==
1. 反转单向链表（迭代/递归两种方法）
2. 合并两个有序链表
3. 删除链表的倒数第N个节点
4. 实现LRU缓存淘汰算法

通过掌握单向链表，学习者将为理解更复杂的[[双向链表]]和[[树结构]]奠定重要基础。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]