一、前言：链表的简单介绍
链表（Linked List）是一种重要的线性数据结构，它以节点（Node）的形式存储数据，每个节点通过指针（或引用）指向下一个节点，从而形成一个动态的数据链条。与数组不同，链表的内存分配并不连续，因此具有更灵活的插入和删除操作，但在随机访问元素时效率相对较低。
链表通常分为单向链表（Singly Linked List）、双向链表（Doubly Linked List）和循环链表（Circular Linked List）等多种形式。每种形式在不同场景下发挥着独特的作用，比如单向链表适合栈或队列的实现，而双向链表则因支持双向遍历更适合需要频繁插入与删除的场景。
在本篇博客中，我们将聚焦单向链表，使用 C 语言实现其基本操作，包括节点插入、删除和遍历，帮助大家更直观地理解链表的构造与功能。通过本文，你将学会如何使用链表高效地管理和操作数据，为深入学习复杂数据结构打下坚实的基础。
二、代码具体实现与讲解
定义节点结构体
这部分是链表的基础，定义了链表节点的数据结构。
#include<stdio.h>
#include<stdlib.h>
// 定义节点结构体
typedef struct node
{
int data; // 存储数据
struct node* next; // 指向下一个节点的指针
} node;
代码说明：
- 该结构体
node包含两个成员：data：保存节点数据。next：指向下一个节点的指针。
- 通过这个结构，多个节点可以链接成链表。
创建新节点的函数
负责生成一个链表节点，并为其分配内存。
// 创建函数用于创建新节点
node* create_node(int data)
{
node *new_node = (node*)malloc(sizeof(node)); // 分配内存
if(new_node == NULL)
printf("Error!"); // 内存分配失败时打印错误
new_node->data = data; // 节点数据赋值
new_node->next = NULL; // 初始化指针为 NULL
return new_node;
}
代码详解：
函数定义与返回值类型：
-
node*：函数返回的是一个指向node类型的指针。这个指针会指向新创建的链表节点。 -
int data：这是传入的参数，表示新节点需要保存的数据。
分配内存：
-
malloc：用于动态分配内存。malloc(sizeof(node))表示为一个node结构体分配合适的内存空间。 -
(node*)：将malloc返回的void*类型指针转换为node*类型，方便操作。 -
new_node：保存分配的内存地址，即指向新创建的节点。
检查内存分配是否成功：
-
原因：内存分配可能会失败，比如系统内存不足时。
-
处理方式：如果
new_node是NULL，表示分配失败，程序会打印一条错误信息。
为节点成员赋值：
-
new_node->data：表示访问新节点的data成员。 -
data：将函数参数data的值赋给新节点的data，存储数据。
初始化指针为 NULL：
-
new_node->next：表示新节点的next指针。 -
NULL：此时新节点还没有连接其他节点，所以将next初始化为NULL，表示暂时是链表的末尾节点。
补充基础知识：
动态内存分配：
-
静态内存：例如数组，大小在编译时确定，不灵活。
-
动态内存：用
malloc按需分配内存，灵活但需要手动释放。
指针的作用：
-
用指针操作内存地址，可以在运行时动态管理数据结构（如链表）。
结构体中的指针：
-
链表节点的
next指针是链表的核心，通过它链接多个节点，形成链表结构。
总结：
这个函数的作用是创建一个包含指定数据的新链表节点，并返回指向该节点的指针。它动态分配内存，初始化数据，并将 next 设置为 NULL，为后续操作做准备。
在链表开头插入节点
将新节点插入到链表的开头。
// 插入一个新节点在链表开头
void insert_at_begin(node **head, int data)
{
node *new_node = create_node(data); // 创建新节点
new_node->next = *head; // 新节点指向当前头节点
*head = new_node; // 更新头指针
}
代码说明：
-
调用
create_node创建新节点。 -
新节点的
next指针指向原来的头节点。 -
更新头指针，使新节点成为链表的新头部。
在链表结尾插入节点
将新节点插入到链表的尾部。
// 插入一个新节点在链表结尾
void insert_at_end(node **head, int data)
{
node *new_node = create_node(data); // 创建新节点
if(*head == NULL) // 如果链表为空
{
*head = new_node; // 直接让新节点成为头节点
return;
}
node *current = *head; // 从头节点开始遍历
while(current->next != NULL) // 找到链表的最后一个节点
{
current = current->next;
}
current->next = new_node; // 将最后一个节点的 next 指向新节点
}
代码说明：
-
如果链表为空，新节点直接作为头节点。
-
如果链表非空，遍历链表找到最后一个节点，将其
next指针指向新节点。
删除节点
从链表中删除指定数据的节点。
// 删除一个节点从链表中
void delete_node(node **head, int data)
{
node *current = *head;
node *previous = NULL;
while (current != NULL) // 遍历链表
{
if(current->data == data) // 找到目标节点
{
if(previous == NULL) // 如果是头节点
{
*head = current->next; // 更新头指针
}
else // 如果是非头节点
{
previous->next = current->next;
}
free(current); // 释放节点内存
return;
}
previous = current; // 更新前驱指针
current = current->next; // 继续遍历
}
}
功能概述：
-
删除链表中存储指定数据的节点。
-
找到目标节点后，根据其位置（头节点、中间节点、尾节点）调整链表结构。
-
释放目标节点所占的内存。
逐行讲解：
1. 定义两个指针：
node *current = *head; // 当前节点指针
node *previous = NULL; // 前一个节点指针
-
current：用于遍历链表，指向当前检查的节点。 -
previous：记录当前节点的前驱节点，用于修改next指针。
2. 遍历链表：
while (current != NULL) // 遍历链表
-
从头节点开始，逐个检查节点。
-
当
current == NULL时，说明链表已经遍历完。
3. 检查当前节点是否是目标节点：
if(current->data == data) // 找到目标节点
-
current->data是当前节点的数据。 -
如果找到与
data参数匹配的节点，进入删除逻辑。
4. 删除节点逻辑：
(1) 如果是头节点：
if(previous == NULL) // 如果是头节点
{
*head = current->next; // 更新头指针
}
-
如果
previous == NULL，说明当前节点是头节点。 -
将头指针
*head更新为current->next，跳过当前节点。 -
这样原来的第二个节点成为新的头节点。
(2) 如果是中间或尾部节点：
else
{
previous->next = current->next; // 跳过目标节点
}
-
如果当前节点不是头节点，则用前驱节点的
next指针指向当前节点的下一个节点（current->next）。 -
这样，链表从逻辑上跳过了目标节点。
5. 释放目标节点的内存：
free(current); // 释放目标节点内存
- 用
free释放目标节点的动态内存，避免内存泄漏。
6. 提前结束函数：
return; // 节点删除后结束函数
- 删除完成后直接返回，避免继续遍历无意义的节点。
7. 更新指针，继续遍历：
previous = current; // 更新前驱指针
current = current->next; // 移动到下一个节点
-
如果当前节点不是目标节点，将
previous更新为当前节点。 -
将
current更新为下一个节点，继续遍历链表。
补充基础知识：
-
链表删除节点的核心思想：
-
删除节点实际上是修改链表结构，使前驱节点的
next跳过目标节点，指向目标节点的下一个节点。
-
-
删除头节点与其他节点的区别：
-
如果是头节点，直接修改头指针
*head。 -
如果是其他节点，需要借助前驱节点的
next指针。
-
-
动态内存释放（
free）：-
动态分配的内存需要手动释放，删除节点后一定要用
free回收内存。
-
-
指针双重间接访问（
**head）：-
**head是一个指针的指针，通过它可以在函数内部修改链表头节点。
-
示例操作：
假设当前链表内容为 1 -> 2 -> 3 -> 4，删除过程如下：
-
删除头节点（
1）：-
更新头指针为
2。 -
链表变为：
2 -> 3 -> 4。
-
-
删除中间节点（
3）：-
将前驱节点（
2）的next指向目标节点（3）的下一个节点（4）。 -
链表变为：
2 -> 4。
-
-
删除尾节点（
4）：-
将前驱节点（
2）的next指向NULL。 -
链表变为：
2。
-
打印链表
打印链表中所有节点数据
// 打印链表
void print_list(node *head)
{
node *current = head;
while(current != NULL) // 遍历链表
{
printf("%d ", current->data); // 打印当前节点数据
current = current->next; // 移动到下一个节点
}
printf("\n");
}
代码说明：
-
从头节点开始遍历，每次打印当前节点数据。
-
遍历结束后换行，便于输出清晰。
主函数
测试链表的核心功能
int main(void)
{
node *head = NULL; // 初始化空链表
insert_at_begin(&head, 1); // 插入数据
insert_at_begin(&head, 2);
insert_at_begin(&head, 3);
insert_at_begin(&head, 4);
insert_at_end(&head, 5);
insert_at_end(&head, 6);
printf("链表内容: ");
print_list(head); // 打印链表
delete_node(&head, 3); // 删除指定节点
delete_node(&head, 5);
printf("更新后的链表: ");
print_list(head); // 打印更新后的链表
return 0;
}
说明：
-
按顺序调用插入、删除、打印等函数。
-
测试链表操作的正确性。
三、整体代码展示
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct node {
int data; // 节点数据
struct node* next; // 指向下一个节点的指针
} node;
// 创建新节点函数
node* create_node(int data) {
// 动态分配内存
node* new_node = (node*)malloc(sizeof(node));
if (new_node == NULL) {
printf("Error: Memory allocation failed!\n");
return NULL;
}
// 初始化节点数据和指针
new_node->data = data;
new_node->next = NULL;
return new_node;
}
// 在链表头插入节点
void insert_at_begin(node** head, int data) {
node* new_node = create_node(data); // 创建新节点
if (new_node == NULL) return; // 内存分配失败直接返回
// 更新新节点的指针，链接到当前头节点
new_node->next = *head;
// 更新头指针
*head = new_node;
}
// 在链表尾插入节点
void insert_at_end(node** head, int data) {
node* new_node = create_node(data); // 创建新节点
if (new_node == NULL) return; // 内存分配失败直接返回
// 如果链表为空，直接更新头指针
if (*head == NULL) {
*head = new_node;
return;
}
// 遍历到链表末尾
node* current = *head;
while (current->next != NULL) {
current = current->next;
}
// 将新节点链接到链表末尾
current->next = new_node;
}
// 删除链表中指定值的节点
void delete_node(node** head, int data) {
node* current = *head; // 当前节点指针
node* previous = NULL; // 前一个节点指针
// 遍历链表，查找目标节点
while (current != NULL) {
if (current->data == data) { // 找到目标节点
if (previous == NULL) { // 如果是头节点
*head = current->next; // 更新头指针
} else { // 如果是中间或尾节点
previous->next = current->next;
}
free(current); // 释放目标节点内存
return; // 删除完成，结束函数
}
// 更新指针，继续遍历
previous = current;
current = current->next;
}
}
// 打印链表
void print_list(node* head) {
node* current = head;
while (current != NULL) {
printf("%d -> ", current->data); // 打印当前节点数据
current = current->next; // 移动到下一个节点
}
printf("NULL\n"); // 链表末尾
}
// 主函数
int main(void) {
node* head = NULL; // 初始化链表为空
// 在链表头插入节点
insert_at_begin(&head, 1);
insert_at_begin(&head, 2);
insert_at_begin(&head, 3);
insert_at_begin(&head, 4);
// 在链表尾插入节点
insert_at_end(&head, 5);
insert_at_end(&head, 6);
// 打印链表
printf("Initial linked list:\n");
print_list(head);
// 删除节点
delete_node(&head, 3);
delete_node(&head, 5);
// 打印链表
printf("Linked list after deletion:\n");
print_list(head);
return 0;
}
（代码若出现错误，欢迎大家批评指正）
四、总结
在本篇博客中，我们以链表为主题，从基本概念出发，详细讲解了链表的定义、核心操作以及相关实现代码，并针对每一个功能模块进行了逐行解析。通过这些内容，相信新手小白们已经能够初步理解链表这一基础数据结构的工作原理，掌握其创建、插入、删除和遍历等基本操作。
链表作为数据结构的经典代表之一，具有灵活性强、内存利用率高的特点。虽然它的实现可能看起来稍显复杂，但只要一步步拆解并多加练习，相信大家都能掌握其中的逻辑并运用到实际项目中。
最后，感谢大家耐心阅读这篇博客！如果内容中有不清楚或需要改进的地方，欢迎大家提出宝贵意见，我会虚心接受并不断改进。同时，希望这篇博客能为刚接触数据结构的小伙伴们带来一些启发和帮助。
如果你觉得内容有用，请多多支持，点个赞或留言评论，我会继续分享更多基础易懂的数据结构和算法内容！学习是一条漫长而充实的旅程，让我们一起努力，共同进步！
感谢你的支持，我们下次见！
标签：node,current,head,list,C语言,链表,next,节点 From： https://blog.csdn.net/morandi666/article/details/145284654