单链表
单链表用指针连接结点,插入、删除无需移动元素,但查找需从头遍历。
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;
}
- 插入/删除:定位需 ,但定位后的指针修改仅 。若已知插入位置的前驱,插入/删除为 。
- 按值查找:需从表头逐个比较,最坏 。
- 按位查找:需遍历,最坏 。
习题 1
单链表相对于顺序表的优点是( )
A. 支持随机访问 B. 插入删除操作效率高 C. 存储密度更高 D. 查找效率更高
解题思路:
本题考查单链表相对顺序表的优劣。答题时抓住链表的本质特点——结点分散存放、靠指针相连——逐项判定四个选项是否成立。
详细步骤:
- 链表插入删除只需修改相关结点的指针域,不需要像顺序表那样整体搬移元素,因此插入删除操作效率高,选项 B 正确。
- 选项 A 错误:链表结点不连续存放,无法直接算出下标地址,不支持随机访问。
- 选项 C 错误:链表每个结点都要额外存储一个指针域,存储密度反而低于顺序表。
- 选项 D 错误:查找指定元素必须从头结点沿指针逐个遍历,时间复杂度为 。
最终答案:
B。
习题 2
单链表插入和删除操作的基本思想是什么?
解题思路:
本题考查单链表插入与删除的基本思想。两者都以“先找到前驱结点”为前提,区别在于:是先把新结点接到后继上再改前驱的指针,还是直接让前驱跨过被删结点。
详细步骤:
- 插入操作:新建结点 s,先将 s->next 指向插入位置的后继结点,再将前驱结点的 next 指向 s,即“先接后断”。
- 删除操作:找到被删结点 q 的前驱 p,令 p->next 指向 q 的后继,跳过 q 后释放 q 的内存。
- 两者都只改动常数个指针域,无需移动其他元素结点,因此在已定位前驱的前提下时间复杂度均为 。
最终答案:
插入:新建结点 s,先将 s->next 指向插入位置的后继结点,再将前驱结点的 next 指向 s(先接后断)。删除:找到被删结点 q 的前驱 p,令 p->next 指向 q 的后继,跳过 q 后释放 q 的内存。
