单链表

复习定位

链表与顺序表互补——顺序表用连续内存可随机存取——链表用离散内存(每个节点通过指针链接)不能随机存取但插入/删除只需修改指针。头结点是链表中一个常用的技巧——使针对空链表和一般链表的操作代码统一。

单链表的定义

链表每个结点包含两部分：

• 数据域(data)——存储该结点的数据(可以是任意类型)
• 指针域(next)——存储下一个结点的地址

头指针head指向链表的第一个结点。如果链表为空——头指针为NULL。最后一个结点的next指针为NULL——表示链表结束。

头结点是在第一个实际数据结点之前额外附加的一个结点——它的data域可以是空或链表长度等附加信息——但核心作用：让在链表头部插入和删除操作的代码与中间结点的操作统一——不需要区分"插入到第一个结点之前"和"插入到其他结点之前"的特殊情况。

单链表的操作

查找——从head开始——沿next指针移动——直到找到目标或到达NULL(表示不存在)。无法通过下标直接访问。

Node* getElem(LinkList L, int i) {
    int j = 1;
    Node *p = L->next; // 头结点后的实际第一个
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

插入——在结点p之后插入新结点：

newNode->next = p->next;
p->next = newNode;

在p之前插入——通常不能O(1)地做到——需要从头遍历寻找p的前驱——O(n)。也可以先插在p之后——然后交换p和newNode的数据(技巧——适用于数据域很小的场景)。

删除——删除p之后的下一个结点：

q = p->next;
p->next = q->next;
free(q);

如果知道被删除结点本身而不带前驱——可以通过将后继结点的数据复制到本结点再删除后继实现"变通删除"——但破坏数据稳定性。

头插法与尾插法

头插法：新结点插入到头结点之后——每插入一个结点就成为第一个元素——因此链表元素的顺序与插入顺序相反。常用于链表的逆置：将原链表逐结点用头插法插入新链表即可。

尾插法：维护一个尾指针r始终指向当前链表的最后一个结点——新结点插入到r之后并更新r。元素顺序与插入顺序相同。动态建链表时最常用。

单链表与顺序表的对比

操作	顺序表	单链表
按位查找	O(1)	O(n)
按值查找(有序)	O(log n)	O(n)
头部插入	O(n)(移动)	O(1)(改指针)
尾部插入(已知尾指针)	O(1)(均摊)	O(1)
已知位置的中间插入	O(n)(移动)	O(1)(改指针)
空间利用	紧凑	每个结点多存指针8B

复习检查

1. 头结点和头指针的区别——LinkList L一般表示头指针还是头结点？L->next是第一个元素还是头结点本身？

2. 头插法建链——输入序列1,2,3,4依次头插——链表中的数据顺序是什么？解释为什么输入的1最终排在了链表尾部。

3. 双链表和单链表的删除操作差异——在单链表中删除已知节点p——为什么无法直接O(1)找到前驱？

4. 尾指针在尾插法建链中的作用——如果不维护尾指针，每次尾插都要从开头遍历找到尾部——这会如何影响建链的时间复杂度：

5. 循环链表的尾指针的next指向头结点——使用循环链表的优势在哪些场景——(从任一结点出发可遍历全链表)的明显优势？