Logo

单链表

单链表用指针连接结点，插入、删除无需移动元素，但查找需从头遍历。

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

单链表的插入

在第 i 个结点后插入新结点 s：先让 s 指向后继，再让前驱指向 s。顺序不能颠倒。

// 在第 i 个位置插入结点 s（前插）
bool ListInsert(LinkList &L, int i, int x) {
    LNode *p = L;  // 头结点
    int j = 0;
    while (p != NULL && j < i - 1) {  // 找到第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;  // ① 新结点指向后继
    p->next = s;        // ② 前驱指向新结点
    return true;
}

单链表的删除

删除第 i 个结点，只需让前驱结点指向被删结点的后继。

bool ListDelete(LinkList &L, int i, int &e) {
    LNode *p = L;
    int j = 0;
    while (p->next != NULL && j < i - 1) {  // 找到第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p->next == NULL) return false;  // 第 i 个结点不存在
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;  // 跳过被删结点
    free(q);
    return true;
}

复杂度推导

  • 插入/删除：定位需 O(n)O(n)，但定位后的指针修改仅 O(1)O(1)。若已知插入位置的前驱，插入/删除为 O(1)O(1)。
  • 按值查找：需从表头逐个比较，最坏 O(n)O(n)。
  • 按位查找：需遍历，最坏 O(n)O(n)。

习题

习题 1

单链表相对于顺序表的优点是（ ）

A. 支持随机访问 B. 插入删除操作效率高 C. 存储密度更高 D. 查找效率更高

答案与解析

答案：B

解析：链表插入删除只需修改指针，无需移动元素，效率高。但它不支持随机访问（A 错）、存储密度低（C 错）、查找需遍历（D 错）。

习题 2

单链表插入和删除操作的基本思想是什么？

答案与解析

插入：新建结点 s，先将 s->next 指向插入位置的后继结点，再将前驱结点的 next 指向 s（先接后断）。

删除：找到被删结点 q 的前驱 p，令 p->next 指向 q 的后继，跳过 q 后释放 q 的内存。

上一章节顺序表顺序表的存储结构、插入删除操作与时间复杂度推导。
下一章节其他链表双向链表、循环链表与静态链表的特点和适用场景。
数据结构