单链表

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

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. 查找效率更高

链表插入与删除随机访问存储密度

解题思路:

本题考查单链表相对顺序表的优劣。答题时抓住链表的本质特点——结点分散存放、靠指针相连——逐项判定四个选项是否成立。

详细步骤:

  1. 链表插入删除只需修改相关结点的指针域,不需要像顺序表那样整体搬移元素,因此插入删除操作效率高,选项 B 正确。
  2. 选项 A 错误:链表结点不连续存放,无法直接算出下标地址,不支持随机访问。
  3. 选项 C 错误:链表每个结点都要额外存储一个指针域,存储密度反而低于顺序表。
  4. 选项 D 错误:查找指定元素必须从头结点沿指针逐个遍历,时间复杂度为 O(n)O(n)。

最终答案:

B。

习题 2

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

单链表插入操作删除操作指针修改

解题思路:

本题考查单链表插入与删除的基本思想。两者都以“先找到前驱结点”为前提,区别在于:是先把新结点接到后继上再改前驱的指针,还是直接让前驱跨过被删结点。

详细步骤:

  1. 插入操作:新建结点 s,先将 s->next 指向插入位置的后继结点,再将前驱结点的 next 指向 s,即“先接后断”。
  2. 删除操作:找到被删结点 q 的前驱 p,令 p->next 指向 q 的后继,跳过 q 后释放 q 的内存。
  3. 两者都只改动常数个指针域,无需移动其他元素结点,因此在已定位前驱的前提下时间复杂度均为 O(1)O(1)。

最终答案:

插入:新建结点 s,先将 s->next 指向插入位置的后继结点,再将前驱结点的 next 指向 s(先接后断)。删除:找到被删结点 q 的前驱 p,令 p->next 指向 q 的后继,跳过 q 后释放 q 的内存。

发现内容有问题?

告诉我们哪里需要改进。