Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/3.单链表.md

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

#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++

#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

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

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()