单向链表的基本操作及实现(.c)
·
目录
前言
在仔细阅读本文章之后你将会感叹道：在单向链表中结构体，结构体指针，指针结构体（——储存指针的结构体），指针的意义，解指针的灵魂之处以及，你会对链表的基本结构有一个非常形象化的理解。
以下是作者温习单向链表之后的感悟：在学习链表（它深刻体现了结构体与指针的协作）时，务必牢记指针的三个核心问题。当你因指针使用混乱而感到困惑时，立刻停下来厘清：
- 这个指针变量本身是什么？ (它存储的是什么？—— 一个内存地址)
- 对这个指针进行解引用 (*ptr 或 ptr-> ) 操作意味着什么？ (你在访问这个地址指向的内存位置)
- 解引用后得到的结果是什么类型？ (你访问到的是地址(指针)，还是一个具体的数据值(基本类型或结构体实例)？)
时刻区分你当前操作的是 指针本身(地址)、指针指向的内存(数据)，还是 指向另一个指针的指针，至关重要。混淆它们极易导致严重错误。
无论遇到多复杂的指针难题，只要冷静下来，反复追问并明确这三个问题的答案，思路就会豁然开朗，问题往往迎刃而解。
链表中的指针，结构体
在确保你能感受到链表将指针结构体运用的灵魂之处前你应该要预热一下有关于链表的一些指针和结构体的储存行为以及运用的形象化
结构体指针的强大之处在于它能访问其指向结构体中的任何成员，无论这些成员是基本数据类型还是其他结构体类型（甚至是指向它们自己同类型的指针）。
然而，普通基本数据类型的指针（如 int*）则不具备这种直接访问“指针的指针”的能力。如果你想用一个基本类型指针来存储另一个指针的地址，你必须使用更高级别的指针：
- 二级指针（如 int**）用于存储一级指针的地址。
- 三级指针（如 int***）用于存储二级指针的地址。
- 同理，如果一个结构体指针成员需要存储指向相同类型结构体的指针（例如 链表或节点），它也必须被定义为该结构体类型的指针（如 struct Node* next;）比如带链表中节点的结构：
这种机制——结构体指针灵活访问嵌套成员，以及指针层级间严格的数据地址存储关系——是理解指针本质的关键，也是实现链式存储（如链表、树）等数据结构的核心基础。
链表的概述
逻辑：物理非连续，逻辑连续
- 物理存储：数据元素（节点）分散在内存各处，不像数组连续存放。
- 逻辑关系：通过指针将节点按顺序链接，形成逻辑上的线性序列。
- 类比：像寻宝游戏，每个藏宝点（节点）记录下一个地点的线索（指针），最终连成一条路径。
- 该表可以进行增删等操作
优势 vs 顺序表
| 场景 | 顺序表 | 链表 |
|---|---|---|
| 大小调整 | 固定 | 动态伸缩 |
| 插入/删除 | O(n) | O(1)（定位后） |
| 空间利用率 | 高 | 较低（含指针） |
链表结构 ——头指针VS头节点
这里先可以不用关头指针（其运用得多），因为头节点是为了更好的理解节点这一核心部分；理解了带头节点的链表自然会理解带头指针的链表。
- 头指针（简化链表操作，同时清除表头空间的利用，加强对空间的利用）
- 定义：指向链表第一个节点的指针（无论是否有头节点）。
- 作用：是链表的入口，丢失头指针等于丢失整个链表。
- 类比：像导游手中的旗帜，指向队伍起点。
- 头节点（使构建链表操作的逻辑更加的简单不易弄杂）
- 定义：链表起点附加的非数据节点，数据域通常为空（或存链表长度）。
- 存在意义：
适合学习理解链表。
统一操作——空表和非空表操作逻辑一致（头指针永不指向NULL）。
简化插入/删除——首元节点的操作与其他节点相同，无需特殊处理。
实现带头结点的单向链表结构的代码
我们以带头节点的单向链表为例子（后面会讲到为什么以带头结点为例子——其方便链表的增删改查的逻辑构建）
// 表示在表中的元素（试例规定储存int类型）
typedef int Element_t;
// 1.定义链表的节点结构
typedef struct node_t
{
Element_t value;
struct node_t *next;
}node_t;
// 2.定义链表整体结构 = size 个 node_t（节点）
// 也就是说 Linklist_t 包含 n个(节点)node_t。
typedef struct Linklist_t
{
node_t headNode; // 表示头节点
int size; // 表示存储总量
}linklist_t;
形象化模型：
实现带头结点的单向链表操作的思路和代码
插入操作的本质：创建一个新节点，把新节点插进去确保前一个节点能访问并且后一个节点也能安全访问。可以说链表其实就是火车，插入操作其实就是把火车的长度加一并且插入一个车厢，还要保证该车厢与上一个车厢和下一个车厢的连接是否连接到位。
int posInsert_linklist(linklist_t *linklist,int pos, Element_t value)
{
// 保证插入位置 pos 是合理的
if(pos < 0 || pos > linklist->size)
{
printf("insert pos invalid!\n");
return 0;
}
// 找到 (pos - 1) 的首地址
node_t* p = linklist->headNode.next;
for(int i=0;i<pos - 1 - 1;i++)
{
p = p->next;
}
// 判断是否 pos 是否溢出
if (p == NULL)
{
printf("insert pos is too big!\n");
return 0;
}
/* 插入操作 */
node_t* new_node = malloc(sizeof(node_t));
*new_node = *p;
new_node->value = value;
p->next = new_node;
linklist->size++;
return 1;
}
删除操作的本质：先用 p 找到要删除数据的上一个数据的地址 ,接着用一个临时指针 temp 储存要删除数据的地址，把要删除数据的上一个数据地址与要删除数据的下一个数据地址连接起来，最后用 free() 释放 temp 指针即可，防止内存泄露（注意使用 free() 释放指针是指释放指针所指向的空间全部归——没有使用权限，并且将指向的指针 temp 初始化为NULL）。
- 具体代码：
int delate_Element_linklist(Element_t value,linklist_t *linklist)
{
//便利查找需要删除的元素的前一个元素
node_t* p = &(linklist->headNode);
while(p->next)
{
if (p->next->value == value)
{
break;
}
p = p->next;
}
if (p->next == NULL)
{
printf("%d no find!\n",value);
return 0;
}
//将要删除的node节点 p->next 的地址备份到 temp 指针中，
node_t* temp = p->next;
//将前一个数的下一个节点的地址 更新p->next 为 temp后的节点
p->next = temp->next;
//直接释放 temp 即可
free(temp);
linklist->size--;
return 1;
}
实现带头结点的单向链表的基本操作的全部代码
头文件 linkList.h
//
// Created by LENOVO on 25-6-6.
//
/*
需求：设计并实现一个带头点节点的单向链表，实现头插法、任意位置插入法，按照值来删除某个元素，显示整个链表数据
*/
#ifndef LINKLIST_H
#define LINKLIST_H
// 表示在表中的元素（试例规定储存int类型）
typedef int Element_t;
// 1.定义链表的节点结构
typedef struct node_t
{
Element_t value;
struct node_t *next;
}node_t;
// 2.定义链表整体结构 = size 个 node_t（节点）
// 也就是说 Linklist_t 包含 n个(节点)node_t。
typedef struct Linklist_t
{
node_t headNode; // 表示头节点
int size; // 表示存储总量
}linklist_t;
//=======================功能接口实现=================================
// 创建一个链表
linklist_t *create_linklist();
// 表示从头节点(headNode_t)后插入元素
int headInsert_linklist(linklist_t *linklist, Element_t value);
// 表示从指定位置 pos 依次元素
int posInsert_linklist(linklist_t *linklist, int pos, Element_t value);
// 表示删除表中的指定元素
int delate_Element_linklist(Element_t value,linklist_t *linklist);
// 查看链表中的所有元素
void showlinklist(const linklist_t *linklist);
// 释放链表
void release_linklist(linklist_t *list);
#endif //LINKLIST_H
- Element_t：定义了链表中元素的类型，这里使用 int 类型。
- node_t：定义了链表的节点结构，包含一个元素值 value 和一个指向下一个节点的指针 next。
- linklist_t：定义了链表的整体结构，包含一个头节点 headNode 和一个表示链表大小的整数 size。
- 声明链表操作的函数，包括创建链表、头插法、任意位置插入、按值删除元素、显示链表元素和释放链表
源文件 linkList.c
//
// Created by LENOVO on 25-6-6.
//
#include <stdio.h>
#include "linkList.h"
#include <stdlib.h>
linklist_t *create_linklist()
{
linklist_t *Table = malloc(sizeof(linklist_t));
if (Table == NULL)
{
fprintf(stderr, "malloc Tablehead fault\n");
return NULL;
}
//初始化链表
Table->headNode.value = 0;
Table->headNode.next = NULL; // 开始的时候只有头结点，用下一节点的地址为空来表示
Table->size = 0;
return Table;
}
int headInsert_linklist(linklist_t *Table, Element_t value)
{
node_t* new_node = malloc(sizeof(node_t));
if (new_node == NULL)
{
fprintf(stderr, "malloc new_node fault\n");
return 0;
}
/* 插入操作 */
// new_node->next = Table->headNode.next; 和33行作用相同，描述操作更加仔细
*new_node = Table->headNode;
new_node->value = value;
Table->headNode.next = new_node;
Table->size++;
return 1;
}
int posInsert_linklist(linklist_t *linklist,int pos, Element_t value)
{
// 保证插入位置 pos 是合理的
if(pos < 0 || pos > linklist->size)
{
printf("insert pos invalid!\n");
return 0;
}
// 找到 (pos - 1) 的首地址
node_t* p = linklist->headNode.next;
for(int i=0;i<pos - 1 - 1;i++)
{
p = p->next;
}
// 判断是否 pos 是否溢出
if (p == NULL)
{
printf("insert pos is too big!\n");
return 0;
}
/* 插入操作 */
node_t* new_node = malloc(sizeof(node_t));
*new_node = *p;
new_node->value = value;
p->next = new_node;
linklist->size++;
return 1;
}
int delate_Element_linklist(Element_t value,linklist_t *linklist)
{
//便利查找需要删除的元素的前一个元素
node_t* p = &(linklist->headNode);
while(p->next)
{
if (p->next->value == value)
{
break;
}
p = p->next;
}
if (p->next == NULL)
{
printf("%d no find!\n",value);
return 0;
}
//将要删除的node节点 p->next 的地址备份到 temp 指针中，
node_t* temp = p->next;
//将前一个数的下一个节点的地址 更新p->next 为 temp后的节点
p->next = temp->next;
//直接释放 temp 即可
free(temp);
linklist->size--;
return 1;
}
void showlinklist(const linklist_t *linklist)
{
// 创建一个专门用来访问节点的指针 p
node_t* p = linklist->headNode.next;
printf("linklist size = %d\n", linklist->size);
while (p != NULL)
{
printf("%d\t",p->value);
p = p->next;
}
}
void release_linklist(linklist_t *list)
{
// 由于头结点的数据可以用 list->headNode.____ 访问，而之后的数据想释放得需要依次访问
// 如此，我们先用循环依次释放头结点之后的数据，再用free直接释放最后的表头
if(list)
{
// 创建一个指针遍历，用临时指针temp释放(因为释放过程中被释放的指针会为 NULL )
node_t* p = list->headNode.next;
node_t* temp = NULL;
while(p->next)
{
temp = p->next;
// 保存后面节点的连接防止内存泄漏
p->next = temp->next ;
free(temp);
list->size--;
}
if(list->size == 0)
{
printf("linklist_t size = %d",list->size);
free(list);
}
else
{
printf("release linklist error,need fix!\n");
}
}
}
函数详解
- create_linklist()：
使用 malloc 函数为链表分配内存。
初始化头节点的 value 为 0，next 为 NULL，链表大小 size 为 0。
返回指向链表的指针。 - headInsert_linklist()：
使用 malloc 函数为新节点分配内存。
将新节点的 value 设置为要插入的值。
将新节点插入到头节点之后。
链表大小 size 加 1。
返回 1 表示插入成功。 - posInsert_linklist()：
检查插入位置 pos 是否合法。
找到插入位置的前一个节点。
使用 malloc 函数为新节点分配内存。
将新节点插入到指定位置。
链表大小 size 加 1。
返回 1 表示插入成功。 - delate_Element_linklist()：
遍历链表，找到要删除元素的前一个节点。
如果找到，将该节点的 next 指针指向要删除节点的下一个节点。
释放要删除的节点。
链表大小 size 减 1。
返回 1 表示删除成功。 - showlinklist()：
从链表的第一个节点开始遍历，依次输出每个节点的 value。
输出链表的大小 size。 - release_linklist()：
遍历链表，依次释放每个节点的内存。
最后释放链表的内存。
主函数文件 main.c（测试接口文件）
//
// Created by LENOVO on 25-5-30.
//
#include<stdio.h>
#include "linkList.h"
void test1()
{
linklist_t* LinkTable = create_linklist();
if(LinkTable == NULL)
{
return ;
}
for(int i = 0; i < 10; i++)
{
headInsert_linklist(LinkTable,i+100);
}
posInsert_linklist(LinkTable,3,520);
showlinklist(LinkTable);
printf("\n=====Here it indicates that the function showlinklist has been executed====================\n");
delate_Element_linklist(520,LinkTable);
showlinklist(LinkTable);
printf("\n=====Here it indicates that the function delate_Element_linklist has been executed=========");
release_linklist(LinkTable);
}
int main()
{
test1();
return 1;
}
测试流程
- 创建一个链表。
- 使用头插法插入 10 个元素。
- 在位置 3 插入元素 520。
- 显示链表元素。
- 删除元素 520。
- 再次显示链表元素。
- 释放链表。
测试结果
实践建议
- 建议读者亲自编写代码实现链表操作，并尝试以下拓展练习：
- 实现按位置删除节点的功能
- 添加链表反转操作
- 设计链表的查找与统计功能
- 比较带头节点与不带头节点链表的实现差异
实现带头指针的单向链表结构的代码
// 表示在表中的元素（试例规定储存int类型）
typedef int Element_t;
// 1.定义链表的节点结构
typedef struct node_t
{
Element_t value;
struct node_t *next;
}node_t;
// 2.定义带头指针的单向链表的头结构
typedef struct
{
node_t*header;
int size;
}chainLink;
形象化模型：
实现带头结点单向链表操作的思路和代码
插入操作(头插法和指定位置插法):
// 指定位置插入可以不用使用 dummy 栈节点，是由于分支较少但也要注意分支。
int insertNode_fromHead(chainLink* table, Element_t value)
{
// 创建并插入带指定插入值的节点
node_t* new_node = malloc(sizeof(node_t));
if (new_node == NULL)
{
fprintf(stderr, "malloc new_node fault\n");
return 0;
}
new_node->value = value;
if(table->header == NULL)
{
table->header = new_node;
new_node->next = NULL;
}
else
{
new_node->next = table->header;
table->header = new_node;
}
table->size++;
return 1;
}
// 指定位置插入就要使用 dummy 节点，是因为分支过多操作复杂容易遗漏
int insertNode_fromPos(chainLink* table, Element_t value, int pos)
{
// 保证插入位置 pos 是合理的
if(pos < 0 || pos > table->size + 1)
{
printf("insert pos invalid!\n");
return 0;
}
node_t dummy;
dummy.next = table->header;
// 用这个 dummy 的节点，最好的地方是不需要管头指针指向的元素是否改变（因为最后一步: table->header = dummy.next;）
node_t* p = &dummy;
for(int i=0;i<pos - 1;i++)
{
// 找到 (pos - 1) 的首地址
p = p->next;
}
/* 插入操作 */
node_t* new_node = malloc(sizeof(node_t));
*new_node = *p;
new_node->value = value;
p->next = new_node;
table->size++;
table->header = dummy.next;
return 1;
}
删除操作（指定删除一个值为"value"的元素, value为在有限范围的整数）
int deleteChainLinkElement(chainLink* table,Element_t value)
{
node_t dummy;
dummy.next = table->header;
node_t* p = &dummy;
while(p->next && p->next->value != value)
{
p = p->next;
}
if (p->next == NULL)
{
printf("element not found!\n");
return 0;
}
//将要删除的node节点 p->next 的地址备份到 temp 指针中，
node_t* temp = p->next;
//将前一个数的下一个节点的地址 更新p->next 为 temp后的节点
p->next = temp->next;
//直接释放 temp 即可
free(temp);
table->size--;
table->header = dummy.next;
return 1;
}
dummy 节点的作用概述
在处理带头指针的单向链表时，链表为空时插入第一个节点、删除头节点以及在链表头部插入新节点这三种特殊情况会使代码逻辑变得复杂，容易出错。dummy 节点（虚拟节点）的引入可以简化这些操作的逻辑，避免对头指针进行特殊处理，使代码更加简洁和健壮。
特殊情况（如果不用 dummy）分析及 dummy 节点的作用
- 链表为空时插入第一个节点
当链表为空时，插入第一个节点需要特别处理头指针。如果没有 dummy 节点，需要判断头指针是否为空，然后更新头指针。使用 dummy 节点后，插入操作可以统一处理，无需考虑头指针是否为空。 - 删除头节点时需要更新头指针
删除头节点时，如果没有 dummy 节点，需要单独更新头指针。使用 dummy 节点后，删除操作可以统一处理，最后通过 table->header = dummy.next; 来更新头指针，避免了对头指针的特殊处理。 - 在链表头部插入新节点时需要更新头指针
在链表头部插入新节点时，如果没有 dummy 节点，需要更新头指针。使用 dummy 节点后，插入操作可以统一处理，最后通过 table->header = dummy.next; 来更新头指针，避免了对头指针的特殊处理。
由于带头指针的 链表 在词形插入或者说删除的操作行为当中会非常的麻烦——需要考虑逻辑的完备性。（如果这里的逻辑完备性想不出来的话就只要记住：只要带头指针的链表）这里引入dummy节点，放入栈。
引入 Dummy 节点简化操作
借鉴带头结点链表的思想，我们可以在操作过程中临时引入一个 Dummy（哨兵）节点来解决上述问题：
- 原理： 在遍历链表进行操作之前，创建一个临时的 Dummy 节点——相当于打开列表变成一个临时带头结点的链表，并让它的 next 指针指向当前的头节点（dummy->next = head）。
简化逻辑：
-
插入： 无论插入位置在头部、中间还是尾部，也无论链表是否为空，都可以在 Dummy 节点之后开始寻找插入位置。插入操作本身只需要修改前驱节点的 next 指针，永远不需要修改头指针本身。
-
删除： 同样从 Dummy 节点之后开始查找目标节点。删除操作（即使是删除原来的头节点）也只需要修改前驱节点（可能是 Dummy）的 next 指针。操作完成后，头指针只需要更新为 dummy->next 即可（如果链表为空，dummy->next 自然为 NULL）。这完全统一了删除任何位置节点的逻辑，消除了对头节点删除的特殊判断。
从带头指针的单向链表的角度看——带头指针 与 带头结点
-
带头指针链表： 结构简洁，节省一个节点的空间（头指针本身不占用节点空间）。但在实现插入/删除接口时，逻辑相对复杂。
-
带头结点链表： 头结点永久存在（data 域通常不用），其 next 指向第一个有效节点。它天生就避免了头指针更新的问题，接口实现通常更简单直接。
-
借鉴与升级： 通过在接口实现中临时使用 Dummy 节点，带头指针链表借鉴了带头结点链表的核心优势（统一操作逻辑），同时保持了自身结构上的空间节省。可以说，这种结合了 Dummy 节点技巧的带头指针链表实现，在接口复杂度上达到了与带头结点链表相当的简洁性，而在空间效率上则优于永久带头结点的链表。
实现带头指针的单向链表的基本操作的全部代码
头文件 no_HNode_LinkList.h
//
// Created by LENOVO on 25-6-16.
//
#ifndef NO_HNODE_LINKLIST_H
#define NO_HNODE_LINKLIST_H
// 表示在表中的元素（试例规定储存int类型）
typedef int Element_t;
// 1.定义链表的节点结构
typedef struct node_t
{
Element_t value;
struct node_t *next;
}node_t;
// 2.定义带头指针的单向链表的头结构
typedef struct
{
node_t*header;
int size;
}chainLink;
// 3.为了灵活运用多文件编程：
// 这里我们将 该链表放入数据区——也就是全局变量
void initChainLink(chainLink* table); // 我们接着初始化即可
void destroyChainLink(chainLink* table); // 销毁所有节点为后面的释放，头指针做准备
int insertNode_fromHead(chainLink* table, Element_t value); // 从头指针往后插入元素
int insertNode_fromPos(chainLink* table, Element_t value, int pos); // 指定任意位置插入
int deleteChainLinkElement(chainLink* table,Element_t value); // 删除链表中的指定元素
void showChainLink(chainLink* table);
#endif //NO_HNODE_LINKLIST_H
源文件 no_HNode_LinkList.c
//
// Created by LENOVO on 25-6-16.
//
#include "no_HNode_LinkList.h"
#include <stdio.h>
#include <stdlib.h>
// 初始化图指针初始化、链表的大小
void initChainLink(chainLink* table)
{
table->header = NULL;
table->size = 0;
}
void destroyChainLink(chainLink* table)
{
while(table->header)
{
node_t *temp = table->header;
table->header = temp->next;
free(temp);
table->size--;
}
}
// 指定位置插入可以不用使用 dummy 栈节点，是由于分支较少但也要注意分支。
int insertNode_fromHead(chainLink* table, Element_t value)
{
// 创建并插入带指定插入值的节点
node_t* new_node = malloc(sizeof(node_t));
if (new_node == NULL)
{
fprintf(stderr, "malloc new_node fault\n");
return 0;
}
new_node->value = value;
if(table->header == NULL)
{
table->header = new_node;
new_node->next = NULL;
}
else
{
new_node->next = table->header;
table->header = new_node;
}
table->size++;
return 1;
}
// 指定位置插入就要使用 dummy 节点，是因为分支过多操作复杂容易遗漏
int insertNode_fromPos(chainLink* table, Element_t value, int pos)
{
// 保证插入位置 pos 是合理的
if(pos < 0 || pos > table->size + 1)
{
printf("insert pos invalid!\n");
return 0;
}
node_t dummy;
dummy.next = table->header;
// 用这个 dummy 的节点，最好的地方是不需要管头指针指向的元素是否改变（因为最后一步: table->header = dummy.next;）
node_t* p = &dummy;
for(int i=0;i<pos - 1;i++)
{
// 找到 (pos - 1) 的首地址
p = p->next;
}
/* 插入操作 */
node_t* new_node = malloc(sizeof(node_t));
*new_node = *p;
new_node->value = value;
p->next = new_node;
table->size++;
table->header = dummy.next;
return 1;
}
int deleteChainLinkElement(chainLink* table,Element_t value)
{
node_t dummy;
dummy.next = table->header;
node_t* p = &dummy;
while(p->next && p->next->value != value)
{
p = p->next;
}
if (p->next == NULL)
{
printf("element not found!\n");
return 0;
}
//将要删除的node节点 p->next 的地址备份到 temp 指针中，
node_t* temp = p->next;
//将前一个数的下一个节点的地址 更新p->next 为 temp后的节点
p->next = temp->next;
//直接释放 temp 即可
free(temp);
table->size--;
table->header = dummy.next;
return 1;
}
void showChainLink(chainLink* table)
{
node_t *p = table->header;
while(p)
{
printf("%d ", p->value);
p = p->next;
}
printf("\n");
printf("%d",table->size);
printf("\n");
}
主函数文件 main.c（测试接口文件）
//
// Created by LENOVO on 25-5-30.
//
#include<stdio.h>
#include "no_HNode_linkList.h"
//===============================带头指针的单向链表接口测试===========================================================
void test1()
{
// 创建带头指针的单向链表并将其初始化
chainLink table;
initChainLink(&table);
// 插入借口测试
for(int i = 0; i < 10; i++)
{
insertNode_fromHead(&table,i+100);
}
insertNode_fromPos(&table,520,11);
// 展示插入借口是否成功
showChainLink(&table);
printf("==================================================================================\n");
// 删除接口测试
deleteChainLinkElement(&table,109);
// 展示删除接口是否成功
showChainLink(&table);
printf("==================================================================================\n");
// 释放结果测试
destroyChainLink(&table);
printf("chainLink table have %d node\n",table.size);
printf("==================================================================================\n");
}
int main()
{
test1();
return 1;
}
测试结果
总结
单向带头指针链表可以看作是升级版的单向带头结点链表。它借鉴了带头结点链表的思想，通过引入 dummy 节点简化了插入和删除操作的逻辑，同时在表头结构上节省了空间，因为不需要额外的头节点来存储信息。但在实现过程中，需要更加注意逻辑的完备性，以处理各种特殊情况。
更多推荐
35
0- 0
已为社区贡献1条内容
所有评论(0)