动态单链表 (Linked List) 的实现
[cite_start]在学习了顺序表（数组）之后，我们发现顺序表在执行插入和删除操作时，需要大量移动元素，时间复杂度高达 $O(n)$。为了解决这个问题，我们引入了非连续存储的线性数据结构——链表 [cite: 4281-4284]。
[cite_start]链表由一系列节点（Node）组成，每个节点包含两部分：数据域（存放数据）和指针域（指向下一个节点的地址） [cite: 4285]。
1. 节点的定义与动态申请
[cite_start]在实际开发中，我们不能使用局部变量来创建节点，因为局部变量随作用域结束就会被销毁，这违背了链表持久存储的初衷 [cite: 4304][cite_start]。我们需要使用动态内存管理主动控制每一个节点的生命周期 [cite: 4305]。
[cite_start]struct Node { // [cite: 4306]int data; [cite_start]// [cite: 4307]Node* next; [cite_start]// [cite: 4308]
}; [cite_start]// [cite: 4309]// 将节点的创建封装为函数，方便重复调用
[cite_start]Node* create_node(int d) { // [cite: 4391]Node* p = new Node; [cite_start]// [cite: 4393]p->data = d; [cite_start]// [cite: 4394]p->next = NULL; [cite_start]// [cite: 4395]return p; [cite_start]// [cite: 4396]
[cite_start]} // [cite: 4397]
2. 链表的核心操作与易错点解析
头部插入 (PushFront)
🚨 核心易错点：指针的引用传递
[cite_start]在封装头部插入函数时，如果直接传递指针变量 ph（按值传递），函数内部对 ph 的修改不会影响到主函数中的 phead [cite: 4409][cite_start]。必须使用指针的引用 (Node*& ph)，或者传递二级指针 (Node** ph) [cite: 4410, 4436-4440]。
[cite_start]void PushFront(Node*& ph, int d) { // [cite: 4407][cite_start]if (ph == NULL) { // [cite: 4411]ph = create_node(d); [cite_start]// [cite: 4413][cite_start]} else { // [cite: 4415]Node* pn = create_node(d); [cite_start]// [cite: 4417-4418]// 顺序很重要：先利用头指针中存的地址连上老链表，再改变头指针！pn->next = ph; [cite_start]// [cite: 4419]ph = pn; [cite_start]// [cite: 4420][cite_start]} // [cite: 4421]
[cite_start]} // [cite: 4422]
尾部插入 (PushBack)
🚨 核心易错点：必须构建中间变量
[cite_start]在尾部插入时，我们需要遍历链表找到最后一个节点。由于 ph 是对 phead 的直接引用，绝对不能用 ph 去做循环遍历（这会导致链表头指针丢失） [cite: 4494][cite_start]。必须创建一个临时变量 tem 来代劳 [cite: 4493-4494]。
[cite_start]void PushBack(Node*& ph, int d) { // [cite: 4495]Node* p_new = create_node(d); [cite_start]// [cite: 4497][cite_start]if (ph == NULL) { // [cite: 4498]ph = p_new; [cite_start]// [cite: 4500][cite_start]} else { // [cite: 4502]Node* tem = ph; [cite_start]// 创建中间变量进行遍历 [cite: 4503][cite_start]while (tem->next != NULL) { // [cite: 4504]tem = tem->next; [cite_start]// [cite: 4506][cite_start]} // [cite: 4507]tem->next = p_new; [cite_start]// [cite: 4508]}
}
头部删除 (PopFront)
头部删除的逻辑分为三步：
- [cite_start]声明临时指针保存要删除的头节点的地址（因为要释放它的空间） [cite: 4519, 4522]。
- [cite_start]让
phead指针向后移，指向第二个节点 [cite: 4520, 4523]。 - [cite_start]
delete释放刚才保存的临时节点空间，并置空防野指针 [cite: 4521, 4524-4525]。
尾部删除 (PopBack)
尾部删除需要考虑三种情况：
- [cite_start]链表为空 [cite: 4537-4539]。
- [cite_start]链表只有一个节点：直接
delete头指针并置空 [cite: 4541-4547]。 - [cite_start]链表有多个节点：需要遍历找到倒数第二个节点（判断条件为
tem->next->next != NULL） [cite: 4551][cite_start]。释放最后一个节点（delete tem->next;），并将倒数第二个节点的next置空（tem->next = NULL;） [cite: 4555-4556]。
3. 面向对象（OOP）方式重构链表
[cite_start]纯粹的 C 语言函数传递指针容易出错且不安全。在 C++ 中，我们可以使用 struct 或 class 将链表封装起来，利用构造函数和析构函数实现更高级的内存管理 [cite: 4578]。
[cite_start]struct list { // [cite: 4584]Node* phead; [cite_start]// 成员变量记录头指针 [cite: 4587]// 1. 构造函数：初始化空链表[cite_start]list() { // [cite: 4590]phead = NULL; [cite_start]// [cite: 4592][cite_start]} // [cite: 4593]// 2. 将增删查改封装为成员函数 (无需再传递头指针形参)// void PushHead(int d) { ... }// void PopFront() { ... }// 3. 析构函数：在对象销毁时，自动释放所有节点内存，杜绝内存泄漏！[cite_start]~list() { // [cite: 4668][cite_start]while (phead != NULL) { // [cite: 4670]popback(); [cite_start]// 或 PopFront() [cite: 4672-4673][cite_start]} // [cite: 4674][cite_start]} // [cite: 4675]// 🚨 遍历函数的致命易错点！[cite_start]void show_list() { // [cite: 4615]// 必须创建副本 tem！// 如果直接在成员变量 phead 上使用 phead = phead->next 循环，// 会导致整个链表的头指针永久改变，链表数据丢失！Node* tem = phead; [cite_start]// [cite: 4617-4619][cite_start]while (tem) { // [cite: 4620]cout << tem->data << " "; [cite_start]// [cite: 4622]tem = tem->next; [cite_start]// [cite: 4623][cite_start]} // [cite: 4624][cite_start]} // [cite: 4626]
}; [cite_start]// [cite: 4678]
4. 附：C 语言的动态内存申请 (malloc / free)
[cite_start]如果在纯 C 语言环境下开发，动态内存申请不使用 new，而是使用 <malloc.h> (或 <stdlib.h>) 中的 malloc 函数 [cite: 4703-4705]。
[cite_start]用法：指针 = (类型强制转换 *) malloc(需要的字节数); [cite: 4708, 4717]。
struct Student* p; [cite_start]// [cite: 4715]
p = (struct Student*)malloc(sizeof(struct Student)); [cite_start]// [cite: 4716-4717]
p->no = 10; [cite_start]// [cite: 4718]
p->next = NULL; [cite_start]// [cite: 4719]
声明：本博客由gemini基于laobie本地obsidian笔记转写，意在将obsidian内置图片转化为了纯文本或表格描述，便于博客上传