# 3. 单链表

## 概念

**单链表**（Singly Linked List）是线性表的一种**链式存储**实现：用一组**任意**的存储单元存放数据元素，通过**指针**把元素按逻辑顺序串起来。每个结点包含数据域和指针域，指针域存放后继结点的地址。

- **逻辑结构**：线性结构（同顺序表）。
- **存储结构**：链式存储。结点在内存中不一定连续，逻辑相邻靠指针维持，因此只能**顺序存取**。
- **带头结点 vs 不带头结点**：头结点是位于第一个数据结点之前的辅助结点（数据域可空）。**带头结点**可以统一「空表/非空表」「表头/表中」的插入删除逻辑，推荐使用。本章采用带头结点。
- **特点**：
  - 优点：插入/删除**不需要移动元素**（已知结点时 O(1)）；表长动态可扩展；不要求大片连续内存。
  - 缺点：不能随机存取，查找第 i 个元素必须从头遍历 O(n)；每个结点额外存储一个指针，存储密度低；由于只存了后继指针，无法倒着访问。
- **适用场景**：频繁插入/删除、表长动态变化、不需要按下标随机访问。

> **与顺序表对比**：顺序表「随机存取 O(1)、插入删除 O(n)」；单链表「插入删除 O(1)（已知位置）、查找 O(n)」。二者互补。

## 核心操作

| 操作     | 说明                                                    |
| -------- | ------------------------------------------------------- |
| 初始化   | 创建头结点，指针域置 NULL                               |
| 判空     | 头结点 next 是否为 NULL（链表动态分配，**无判满**概念） |
| 按位查找 | 从头结点开始计数，返回第 i 个结点（O(n)）               |
| 按值查找 | 从头遍历，返回第一个值为 x 的结点                       |
| 按位插入 | 找到第 i-1 个结点，在其后插入新结点（O(n)）             |
| 按值插入 | 在第一个值为 x 的结点之后插入新结点                     |
| 删除     | 找到第 i-1 个结点，绕过第 i 个结点并释放它（O(n)）      |
| 遍历打印 | 从头结点 next 开始依次输出                              |

> **头插法与尾插法**：建立链表时，头插法（每个新结点插在头结点之后）得到的链表与原顺序相反；尾插法保持原顺序，常需一个尾指针。

## 复杂度分析

| 操作         | 时间复杂度 | 空间复杂度 | 原因                                |
| ------------ | ---------- | ---------- | ----------------------------------- |
| 初始化       | O(1)       | O(1)       | 只创建头结点                        |
| 判空         | O(1)       | O(1)       | 只比较头结点指针                    |
| 按位查找     | O(n)       | O(1)       | 无法随机存取，需从前往后数          |
| 按值查找     | O(n)       | O(1)       | 最坏遍历全表                        |
| 按位插入     | O(n)       | O(1)       | 找第 i-1 个结点 O(n)，插入本身 O(1) |
| 已知结点后插 | O(1)       | O(1)       | 只需改两个指针                      |
| 删除         | O(n)       | O(1)       | 找前驱 O(n)，删除本身 O(1)          |
| 遍历打印     | O(n)       | O(1)       | 顺序扫描一遍                        |

> 关键理解：链表**「插入/删除快」**的前提是**已经知道操作位置**；若按位操作，找位置的过程本身就是 O(n)。这一点常被初学者忽略。

## 语言实现

### C

```c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;            // 数据域
    struct Node *next;   // 指针域：指向后继
} Node, *LinkList;

// 初始化：创建带头结点的空链表
LinkList initList(void) {
    LinkList L = (Node *)malloc(sizeof(Node));  // 头结点
    if (L == NULL) exit(1);
    L->next = NULL;
    return L;
}

// 判空
int isEmpty(LinkList L) {
    return L->next == NULL;
}

// 按位查找：返回第 i 个结点（i 从 1 开始），找不到返回 NULL
Node *getNode(LinkList L, int i) {
    if (i < 1) return NULL;
    Node *p = L->next;      // 第 1 个数据结点
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找：返回第一个值为 x 的结点，找不到返回 NULL
Node *locateNode(LinkList L, int x) {
    Node *p = L->next;
    while (p && p->data != x)
        p = p->next;
    return p;
}

// 按位插入：在第 i 个位置插入 x（找到第 i-1 个结点后插）
int insertList(LinkList L, int i, int x) {
    if (i < 1) return 0;
    Node *pre = L;          // 从头结点开始找第 i-1 个
    int j = 0;
    while (pre && j < i - 1) {
        pre = pre->next;
        j++;
    }
    if (pre == NULL) return 0;  // 位置非法（i 超过长度+1）

    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL) exit(1);
    s->data = x;
    s->next = pre->next;    // 后插
    pre->next = s;
    return 1;
}

// 按值插入：在第一个值为 x 的结点之后插入 y
int insertAfter(LinkList L, int x, int y) {
    Node *p = locateNode(L, x);
    if (p == NULL) return 0;
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL) exit(1);
    s->data = y;
    s->next = p->next;      // 后插
    p->next = s;
    return 1;
}

// 删除第 i 个结点，用 e 带回其值
int deleteList(LinkList L, int i, int *e) {
    if (i < 1) return 0;
    Node *pre = L;          // 找第 i-1 个结点
    int j = 0;
    while (pre && j < i - 1) {
        pre = pre->next;
        j++;
    }
    if (pre == NULL || pre->next == NULL) return 0;  // 第 i 个不存在

    Node *q = pre->next;    // 待删除结点
    *e = q->data;
    pre->next = q->next;    // 绕过 q
    free(q);                // 释放
    return 1;
}

// 遍历打印
void printList(LinkList L) {
    if (isEmpty(L)) {
        printf("空链表\n");
        return;
    }
    Node *p = L->next;
    while (p) {
        printf("%d", p->data);
        if (p->next) printf(" -> ");
        p = p->next;
    }
    printf("\n");
}

int main(void) {
    LinkList L = initList();
    printf("初始状态: ");
    printList(L);
    printf("判空=%d\n", isEmpty(L));

    // 尾插法建立 10 20 30
    insertList(L, 1, 10);
    insertList(L, 2, 20);
    insertList(L, 3, 30);
    insertList(L, 2, 15);      // 按位插入：第 2 位
    insertAfter(L, 20, 25);    // 按值插入：20 之后
    printList(L);

    Node *p = getNode(L, 3);   // 按位查找
    printf("第3个结点=%s\n", p ? "存在" : "不存在");
    if (p) printf("  其值为 %d\n", p->data);

    p = locateNode(L, 25);     // 按值查找
    printf("值为25的结点=%s\n", p ? "存在" : "不存在");

    int e;
    if (deleteList(L, 2, &e))  // 删除第 2 个
        printf("删除元素=%d\n", e);
    printList(L);

    // 释放全部结点
    Node *q = L;
    while (q) {
        Node *t = q->next;
        free(q);
        q = t;
    }
    return 0;
}
```

### C++

```C++
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int d) : data(d), next(nullptr) {}
};

class LinkList {
private:
    Node *head;   // 头结点

public:
    // 初始化
    LinkList() { head = new Node(0); }

    ~LinkList() {  // 析构：释放所有结点
        Node *p = head;
        while (p) {
            Node *t = p->next;
            delete p;
            p = t;
        }
    }

    bool isEmpty() const { return head->next == nullptr; }

    // 按位查找：返回第 i 个结点指针（i 从 1 开始），无则 nullptr
    Node *getNode(int i) const {
        if (i < 1) return nullptr;
        Node *p = head->next;
        int j = 1;
        while (p && j < i) { p = p->next; j++; }
        return p;
    }

    // 按值查找
    Node *locateNode(int x) const {
        Node *p = head->next;
        while (p && p->data != x) p = p->next;
        return p;
    }

    // 按位插入
    bool insertList(int i, int x) {
        if (i < 1) return false;
        Node *pre = head;   // 找第 i-1 个
        int j = 0;
        while (pre && j < i - 1) { pre = pre->next; j++; }
        if (!pre) return false;
        Node *s = new Node(x);
        s->next = pre->next;
        pre->next = s;
        return true;
    }

    // 按值插入：在第一个值为 x 的结点之后插入 y
    bool insertAfter(int x, int y) {
        Node *p = locateNode(x);
        if (!p) return false;
        Node *s = new Node(y);
        s->next = p->next;
        p->next = s;
        return true;
    }

    // 按位删除
    bool deleteList(int i, int &e) {
        if (i < 1) return false;
        Node *pre = head;
        int j = 0;
        while (pre && j < i - 1) { pre = pre->next; j++; }
        if (!pre || !pre->next) return false;
        Node *q = pre->next;
        e = q->data;
        pre->next = q->next;
        delete q;
        return true;
    }

    // 遍历打印
    void print() const {
        if (isEmpty()) { cout << "空链表" << endl; return; }
        Node *p = head->next;
        while (p) {
            cout << p->data;
            if (p->next) cout << " -> ";
            p = p->next;
        }
        cout << endl;
    }
};

int main() {
    LinkList L;
    cout << "初始状态: ";
    L.print();
    cout << "判空=" << L.isEmpty() << endl;

    L.insertList(1, 10);
    L.insertList(2, 20);
    L.insertList(3, 30);
    L.insertList(2, 15);      // 按位插入
    L.insertAfter(20, 25);    // 按值插入
    L.print();

    Node *p = L.getNode(3);
    cout << "第3个结点=" << (p ? "存在" : "不存在");
    if (p) cout << ", 值=" << p->data;
    cout << endl;

    cout << "值为25的结点=" << (L.locateNode(25) ? "存在" : "不存在") << endl;

    int e;
    if (L.deleteList(2, e))
        cout << "删除元素=" << e << endl;
    L.print();
    return 0;
}
```

### Java

```java
public class LinkListDemo {
    // 单链表结点
    static class Node {
        int data;
        Node next;
        Node(int d) { data = d; }
    }

    // 带头结点的单链表
    static class LinkList {
        private final Node head;   // 头结点

        LinkList() {
            head = new Node(0);
        }

        boolean isEmpty() {
            return head.next == null;
        }

        // 按位查找：返回第 i 个结点（i 从 1 开始），无则 null
        Node getNode(int i) {
            if (i < 1) return null;
            Node p = head.next;
            int j = 1;
            while (p != null && j < i) { p = p.next; j++; }
            return p;
        }

        // 按值查找
        Node locateNode(int x) {
            Node p = head.next;
            while (p != null && p.data != x) p = p.next;
            return p;
        }

        // 按位插入
        boolean insertList(int i, int x) {
            if (i < 1) return false;
            Node pre = head;   // 找第 i-1 个
            int j = 0;
            while (pre != null && j < i - 1) { pre = pre.next; j++; }
            if (pre == null) return false;
            Node s = new Node(x);
            s.next = pre.next;
            pre.next = s;
            return true;
        }

        // 按值插入：在第一个值为 x 的结点之后插入 y
        boolean insertAfter(int x, int y) {
            Node p = locateNode(x);
            if (p == null) return false;
            Node s = new Node(y);
            s.next = p.next;
            p.next = s;
            return true;
        }

        // 按位删除，返回被删结点值；失败返回 null
        Integer deleteList(int i) {
            if (i < 1) return null;
            Node pre = head;
            int j = 0;
            while (pre != null && j < i - 1) { pre = pre.next; j++; }
            if (pre == null || pre.next == null) return null;
            Node q = pre.next;
            pre.next = q.next;
            return q.data;
        }

        // 遍历打印
        void print() {
            if (isEmpty()) { System.out.println("空链表"); return; }
            Node p = head.next;
            while (p != null) {
                System.out.print(p.data);
                if (p.next != null) System.out.print(" -> ");
                p = p.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        LinkList L = new LinkList();
        System.out.print("初始状态: ");
        L.print();
        System.out.println("判空=" + L.isEmpty());

        L.insertList(1, 10);
        L.insertList(2, 20);
        L.insertList(3, 30);
        L.insertList(2, 15);      // 按位插入
        L.insertAfter(20, 25);    // 按值插入
        L.print();

        Node p = L.getNode(3);
        System.out.println("第3个结点=" + (p != null ? "存在, 值=" + p.data : "不存在"));
        System.out.println("值为25的结点=" + (L.locateNode(25) != null ? "存在" : "不存在"));

        Integer e = L.deleteList(2);
        System.out.println("删除元素=" + e);
        L.print();
    }
}
```

### Python

```python
class Node:
    """单链表结点"""

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


class LinkList:
    """带头结点的单链表"""

    def __init__(self):
        # 初始化：创建头结点
        self._head = Node(None)

    def is_empty(self) -> bool:
        return self._head.next is None

    def get_node(self, i: int) -> Node:
        """按位查找：返回第 i 个结点（i 从 1 开始），无则返回 None"""
        if i < 1:
            return None
        p = self._head.next
        j = 1
        while p is not None and j < i:
            p = p.next
            j += 1
        return p

    def locate_node(self, x) -> Node:
        """按值查找：返回第一个值为 x 的结点"""
        p = self._head.next
        while p is not None and p.data != x:
            p = p.next
        return p

    def insert_list(self, i: int, x) -> bool:
        """按位插入：在第 i 个位置插入 x"""
        if i < 1:
            return False
        pre = self._head          # 找第 i-1 个结点
        j = 0
        while pre is not None and j < i - 1:
            pre = pre.next
            j += 1
        if pre is None:
            return False
        s = Node(x)
        s.next = pre.next
        pre.next = s
        return True

    def insert_after(self, x, y) -> bool:
        """按值插入：在第一个值为 x 的结点之后插入 y"""
        p = self.locate_node(x)
        if p is None:
            return False
        s = Node(y)
        s.next = p.next
        p.next = s
        return True

    def delete_list(self, i: int):
        """按位删除：删除第 i 个结点并返回其值，失败返回 None"""
        if i < 1:
            return None
        pre = self._head
        j = 0
        while pre is not None and j < i - 1:
            pre = pre.next
            j += 1
        if pre is None or pre.next is None:
            return None
        q = pre.next
        pre.next = q.next
        return q.data

    def print_list(self):
        if self.is_empty():
            print("空链表")
            return
        vals = []
        p = self._head.next
        while p is not None:
            vals.append(str(p.data))
            p = p.next
        print(" -> ".join(vals))


if __name__ == "__main__":
    L = LinkList()
    print("初始状态:", end=" ")
    L.print_list()
    print("判空 =", L.is_empty())

    L.insert_list(1, 10)
    L.insert_list(2, 20)
    L.insert_list(3, 30)
    L.insert_list(2, 15)        # 按位插入
    L.insert_after(20, 25)      # 按值插入
    L.print_list()

    p = L.get_node(3)
    print("第3个结点 =", "存在, 值 = " + str(p.data) if p else "不存在")
    print("值为25的结点 =", "存在" if L.locate_node(25) else "不存在")

    e = L.delete_list(2)
    print("删除元素 =", e)
    L.print_list()
```