单向链表（Singly Linked List）[编辑 | 编辑源代码]

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

核心特性[编辑 | 编辑源代码]

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

节点结构[编辑 | 编辑源代码]

用伪代码表示节点结构：

class Node:
    def __init__(self, data):
        self.data = data  # 数据域
        self.next = None  # 指针域

基本操作[编辑 | 编辑源代码]

1. 创建链表[编辑 | 编辑源代码]

// Java实现
public class LinkedList {
    Node head;  // 头节点

    static class Node {
        int data;
        Node next;
        Node(int d) { data = d; }
    }
}

2. 插入操作[编辑 | 编辑源代码]

插入位置

时间复杂度

代码示例

头部

O(1)

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;
}

尾部

O(n)

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

指定位置

O(n)

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;
}

3. 删除操作[编辑 | 编辑源代码]

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);
}

实际应用案例[编辑 | 编辑源代码]

浏览器历史记录：使用单向链表实现"前进"功能（虽然需双向链表实现完整前进后退，但简化版本可用单向链表）：

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

复杂度分析[编辑 | 编辑源代码]

操作	时间复杂度	空间复杂度
访问	O(n)	O(1)
搜索	O(n)	O(1)
插入	O(1)（头插） / O(n)（其他）	O(1)
删除	O(1)（头删） / O(n)（其他）	O(1)

进阶技巧[编辑 | 编辑源代码]

快慢指针法（检测环/找中点）：

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

数学表示：链表长度计算： $L = \sum_{i = 1}^{n} 𝕀 (n o d e_{i} \neq null)$ 其中 $𝕀$ 为指示函数。

常见问题[编辑 | 编辑源代码]

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

页面模块:Message box/ambox.css没有内容。

练习题[编辑 | 编辑源代码]

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

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