---

---

二、链表

暂时到这一步你就理解为：假如一个节点断了，其实就连不上了。

2.1 链表初始化

#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}int main(int argc, char const *argv[]){Node *list = initList();return 0;
}

解释上述代码：

typedef struct node{ElemType data;struct node *next;
}Node;

首先这是一个结构体，并且还使用了关键字typedef。
ElemType data; 表示的是data是一个int类型，用来存储该节点的数据，

最关键的就是struct node * next; 这是什么意思？
这是一个指针，指向的是一个类型为struct node类型的指针，并且这里必须是一个指针，因为若直接包含结构体本身（而非指针），会导致逻辑矛盾：

// 错误写法！编译失败
typedef struct node {ElemType data;struct node next;  // 直接包含自身类型
} Node;

存在的问题​：结构体 node 内部又包含一个完整的 node，后者再包含另一个 node……形成无限嵌套，内存大小无法确定。

解决办法​：改用指针 struct node *next。
→ ​指针的本质是地址​（固定占4或8字节），仅存储下一个节点的内存起始位置，而非完整节点内容。
→ 物理上节点分散在内存各处，逻辑上通过指针串联成链。

需要注意的是为什么内部要用 struct node 而非 Node？
这是因为在结构体定义内部，别名 Node ​尚未生效​（编译器按顺序解析）
**使用完整结构体名 struct node *next，明确告知编译器这是一个指向相同结构类型的指针。
结构体自引用​：结构体内部用 struct node *next 声明指针（而非 Node *next），因类型别名 Node 在结构体定义后才生效

struct node *next 的核心意义

• 功能​：作为“链”，指向下一个同类型节点，实现动态连接。
• ​必要性​：
  • 避免结构体无限嵌套 → 用指针代替自身类型。
  • 确保类型安全 → 必须指向 struct node 类型。
• ​操作优势​：插入/删除节点只需修改指针，无需移动数据（数组的劣势）。

这个其实就产生了联系，因为这个地方存储的是一个指针，表示的就是下一个节点的其实位置，因此就逐渐串联起来了。

接下来就看这个链表初始化：

Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}

Node* initList() 表示的是这个函数返回的是一个指针类型变量，该指针类型变量是Node* 类型，而Node* 类型又是什么类型指针变量，
Node*: 是一个结构体，链表结构体，返回值类型为 Node*（指向节点的指针），即返回链表的头节点地址。
此函数无需外部参数，仅通过内部逻辑创建头节点。

头节点

• 作用​：头节点是链表的起点，​不存储有效数据​（其 data 字段常作为预留位置或存储链表长度）。
• ​指针域​：head->next = NULL 表示链表初始为空，无后续节点

这个函数不仅分配了头结点的内存地址，还完成了以下关键操作：

1. ​内存分配​：malloc(sizeof(Node)) 动态申请了一个节点所需的内存空间
2. ​数据初始化​：设置头结点的数据域为固定值 0（头结点通常不存储用户数据）
3. ​指针初始化​：明确将头结点的 next 指针设为 NULL，表示空链表状态
4. ​返回头指针​：将初始化后的头结点地址返回给调用方

这实现了链表的"哨兵节点"设计模式：头结点作为固定存在的哨兵节点，简化后续操作（插入/删除时无需特殊处理链表为空的情况）。

2.2 单链表

2.2.1 单链表—头插法

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}int main(int argc, char const *argv[])
{Node *list = initList();insertHead(list, 10);insertHead(list, 20);return 0;
}

使用头插法，一定要注意的是，创建的新的节点一定要先把他指向的内容给确定了，他指向的内容就是原本头节点指向的下一个节点，为什么要这样？
首先我们可以假设一下，如果我们先将头节点指向我们插入的节点，这个很简单，因为我们新的节点的地址很容易就能知道，这是我们这一行代码

Node *p = (Node*)malloc(sizeof(Node));

我们使用的是malloc在堆内存里面申请一个空间，因此直接在申请的时候就能指导，那么我们其实要做的就是直接将这个地址，赋值给原本蓝色块里面存放地址的那个指针变量，但是需要注意的是我们会直接覆盖点原本蓝色块存储的指向70这个数据的地址（这是因为我们没有用变量保存这个地址），这样我们在想给新创建的这个数据里面的存放70这个数据的地址是没有办法的，因为我们找不到了，被覆盖了。因此为了避免这种情况，我们可以使用一个变量进行保存，但是这样就会很麻烦。那么我们可以换一个思路，那就是将顺序改变，我们先从蓝色快里面存储的地址给复制到新创建数据节点存储地址的指针变量，这样相较于第一种思路我们就减少了一个保存地址的环节，接着我们在将新创建的地址在复制给蓝色块里面存放地址的那个指针变量，这样就完成了头插法。

所以一定要牢记，一定是新的节点，先指向原本头节点指向的那个节点，然后再让头节点指向这个新的节点。

2.2.2 单链表—单链表遍历

void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d　", p->data);p = p->next;}printf("\n");
}

对于刚接触链表可能有一点绕，因为逐行看这一段代码，

Node *p = L->next;

表示的是这个链表的头节点（就是不存储实际数据的节点）赋值给我们创建的一个中间指针变量（该指针变量的类型就是节点类型的结构体），那么我们首先要看看这个头节点链接了下一个数据节点，如果没有连接，那么里面的指针变量就是NULL，相反如果链接了就不是NULL，那么就会进入while循环，

printf("%d　", p->data);
p = p->next;

此时我们指导，指针p存储的就是当前第一个节点（存储有效数据节点）存储的数据，

接着就是

p = p->next;

这一步理解起来就是相当于for循环里面的变量 i，就是将p里面现在存储的下一个节点地址在赋值给p，循环使用这个p，就像循环使用变量 i 一样，只不过这个地方的是指针，看起来要绕一点或者是难以理解一点，这是因为刚开始结束，因此就显得有点绕，但是问题不大，随着长时间对指针的使用这种就会形成固化的思路，就会简单很多。

• Node *p = L->next;
  • L 是头节点指针​（通常不存储实际数据）
  • L->next 指向链表的第一个实际数据节点​
  • p 被赋值为第一个实际节点的地址
• while(p != NULL) 循环：
  • 循环条件检查 p 是否指向有效节点
  • 当 p 指向第一个节点时，执行的是 printf("%d　", p->data)
  • 因此输出的是第一个实际节点的数据，而非头节点的数据

头节点 [L] → 指向第一个实际节点
↓
实际节点1 [p] → 实际节点2 → … → NULL
↓
data (被打印)

值得注意的是：
头插法的顺序和排列的顺序是相反的。

2.2.3 单链表—尾插法

其实尾插法的总体思路和头插法思路是一样的，但是我们需要找到链表的最后一个数据，怎么找到这个数据，截止到目前，我能想到的其实还是使用遍历的思想。

头插法是很容易找到头的，这是因为我们给的就是链表的头节点，这是本身的结构决定了头插法速度很快，这是因为我们天然的就可以获取到链表头节点的地址，从而完成对应的数据插入。

但是尾插法不一样，因为我们不是太容易找到链表的最后一个数据，找到最后一个节点储存地址的指针变量里面存储的是一个NULL指针。

void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d　", p->data);p = p->next;}printf("\n");
}

上述是遍历的思路，我们可以在这个基础上进行使用。

void listNode(Node* L)
{Node *p = L->next;while(p != NULL){p = p->next;}/* 接着进行相关尾插相关操作 */
}

对于以上就是我本人的思路，我想当然的就在这个函数里面直接就处理了关于尾插法的一些操作，这个思路固然是没有错的，但是我们忘记了一件事，那就是我们在开发过程中有一个原则，那就是：一个函数仅完成一件功能。如果一个函数实现多个功能给开发、使用、维护都带来很大的困难。将没有关联或者关联很弱的语句放到同一函数中，会导致函数职责不明确，难以理解，难以测试和改动。
另一个原因我们忘记了C语言中return的使用。

基于上述的原则，我们要明确一个函数就干一个事情，例如上述的函数我们的目的就是找到尾节点，因此我们就需要保证这个函数的功能就是找尾节点，为什么呐，这是因为在其他地方或者是多个链表的时候，可能有时候只需要找到尾节点就行了，因为我们要把这个函数的功能给独立出来。

这个地方其实也是自己在梳理开发思路，因为开发过程中逻辑很复杂，我们要抽丝剥茧的去分解任务，分解相关逻辑，那其实就是将一个应用分解为无数个功能模块，而每一个功能模块又要分解为不同的任务函数，只需要在对应的函数预留出对应的接口，这样才是多人协同工作效率最高的办法，这也是我们所追求的。

以下是我用AI搜到的关于在嵌入式软件工程师招聘过程中要求较强的文档编写能力解释：
在嵌入式开发领域，“较强的文档编写能力”并不仅仅指会写文字，而是指能够通过专业、系统、清晰的文档将技术方案、设计决策、接口规范等关键信息结构化地沉淀下来，确保项目可维护、可协作、可追溯。这种能力是嵌入式工程师技术素养的重要体现，也是团队协作和产品质量的保障。下

工程师如何提升文档能力？

1. ​复用模板​：
   • 需求文档 → 参考中的功能/非功能需求结构
   • 设计文档 → 采用的模块化描述框架
2. ​工具协同​：
   • 用Doxygen自动生成代码接口文档
   • 使用PlantUML绘制状态机/时序图嵌入文档
3. ​语言技巧​：
   • 多用被动语态（“数据被采集”而非“我们采集数据”）
   • 动词明确（“配置”“校验”“触发”替代“处理”“操作”）

以上仅作为一个参考，带有个人的主管臆测。

回归正题，那么关于获取尾节点正确的写法就是

Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}

其实这一快最不习惯的就是

Node*  get_tail(Node  *L)

因为我们一般会使用

int get_tail(Node  *L) 等等

但是关于这种指针变量，并且还是使用typedef关键字给重新命名的指针变量还需要进一步习惯和固化。

2.2.4 单链表—在指定位置插入数据

==这里就跟头插法分析的一样，一定不能搞错指向顺序，==
**一定是先把70这个节点存储的80节点地址赋值给新的节点存储下一个节点地址的变量。虽然有点绕，但是这个很关键的因素。这是插入的核心思想，一定不能错。牢记于心！！！！！！**

int insertNode(Node *L, int pos, ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历链表找到插入位置的前驱节点while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}//要插入的新节点Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}

Node *p = L;

这个地方就是将头结点先给p，也就是只有找到链表的其实位置才能进行查找依次查找嘛，毕竟链表是开始。

还有就是我们需要明白的是我们插入的位置，如果是想在位置5插入，那么我们就需要知道位置4节点结构体里面存储下一个节点的地址，因此在while循环的时候，其实就是找的就是前一个节点。

Node *list = initList();Node *tail = get_tail(list);tail  = insertTail(tail, 10);tail  = insertTail(tail, 20);tail  = insertTail(tail, 30);listNode(list);insertNode(list, 3, 15);listNode(list);return 0;

原本是：10 20 30
我想在第二个位置插入15，其实就是10和20之间
需要说明的是：

• 若链表有头结点，则：
  • 头结点 → 位置1（10） → 位置2（20） → 位置3（30）
  • ​在第二个位置插入​ = 在 10 和 20 之间插入。
• 若链表无头结点，则：
  • 位置1（10） → 位置2（20） → 位置3（30）
  • ​在第二个位置插入​ = 在 10 和 20 之间插入。
    可以看出不管是有没有头结点，我们都把有效存储数据的节点成为第一个位置。

2.2.5 单链表—删除指定位置节点

其实可以看出来道理是相同的，但是需要注意的是我们一定要释放内存。

因为这个里面的都是在堆内存中，找到的位置，如果删除，就一定要释放。

找到要删除节点的前置节点 p
用指针 q记录要删除的节点
通过改变 p的后继节点实现删除
释放删除节点的空间

//删除节点int deleteNode(Node *L, int pos)
{//要删除节点的前驱Node *p = L;int i = 0;//遍历链表，找到要删除节点的前驱。while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}//q指向要删除的节点Node *q = p->next;//让要删除节点的前驱指向要删除节点的后继p->next = q->next;//释放要删除节点的内存空间free(q);return 1;
}

同样可以看出如果想删除，一定也要找到删除节点的前一个节点。

我们p节点里面的存储的节点指针其实就是我们即将删除的节点信息，因此需要先将这个信息找一个中间量，将这个删除节点里面的信息给保存下来，注意这个指针变量一定要声明称和节点保持一致，如果不一样就这个指针就不能保存这个删除节点的信息，那么就会导致无法连接后面没有删除的节点。

因此呐，我们就将这个节点信息保存给q，同事我们紧接着就是将q里面存储的指向写一个节点的信息给存储到我们找到的前一个位置节点p里面，这样节点p就完成了后续节点的连接，让这个链表给连接起来了。

最后就是使用 free(q); 进行内存释放。

2.2.6 单链表—获取链表长度

//获取链表长度int listLength(Node *L){Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;}

较为简单不需要详细降解。

2.2.7 单链表—释放链表

//释放链表void freeList(Node *L){Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}

释放链表，但是头结点是不释放的，这个一定要注意！！！！！！！！！

指针 p指向头节点后的第一个节点

判断指针 p 是否指向空节点

如果 p不为空，用指针q记录指针p的后继节点。

释放指针 p指向的节点

指针 p和指针p指向同一个节点，循环上面的操作。

其实这些指针看起来还是不是那么自在这是因为不熟悉指针的使用。

next在结构体里面是一直是下一个的地址

这个地方还是想多说几句，就是我们一定要理解，next存放的是下一个节点的结构体的地址，因此我们的这三行代码

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

逻辑如下：
首先我将现在p里面指向下一个节点的地址给取出来，存在q里面，这个q现在存储的是一个结构体指针变量，接下来我就先释放q，最后我在将q这个结构体地址给赋值给p，然后进行一个循环，因为此时的p又变成了一个结构体，因此可以使用 q = p->next;

在这里释放内存，就是释放原来这个地方内存。

---

区别于顺序表
链表在插入数据、删除数据快速。 但是读取速度慢，因为需要遍历，通过指向进行逐个循环。
顺序表：找东西很快，相当于是数组。

---

文章源码获取方式：
如果您对本文的源码感兴趣，欢迎在评论区留下您的邮箱地址。我会在空闲时间整理相关代码，并通过邮件发送给您。由于个人时间有限，发送可能会有一定延迟，请您耐心等待。同时，建议您在评论时注明具体的需求或问题，以便我更好地为您提供针对性的帮助。

【版权声明】
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议。这意味着您可以自由地共享（复制、分发）和改编（修改、转换）本文内容，但必须遵守以下条件：
署名：您必须注明原作者（即本文博主）的姓名，并提供指向原文的链接。
相同方式共享：如果您基于本文创作了新的内容，必须使用相同的 CC 4.0 BY-SA 协议进行发布。

感谢您的理解与支持！如果您有任何疑问或需要进一步协助，请随时在评论区留言。