动态数据的艺术：揭开单链表的面纱
·
目录
一、引言
单链表（Singly Linked List）是数据结构中最基础且广泛应用的链式结构之一。与数组不同，单链表在内存中的元素不需要连续存储，每个元素（节点）通过指针连接到下一个节点。这种非连续存储结构，使得单链表在动态内存管理、插入和删除操作上有着明显的优势。它在处理动态数据或需要频繁插入删除的场景中尤为高效，因此在许多算法和应用中扮演着重要角色。
本文将全面介绍单链表的概念、结构和常见操作，提供完整的代码实现，并详细讲解每个操作的核心思想。通过本文的学习，你将能够深入理解单链表的特点及其在编程中的实际应用。
二、单链表的基本概念与结构
1. 概念
单链表是一种链式存储的数据结构，由一系列节点（Node）组成。每个节点包含两部分：
-
数据域（Data）：存储实际的数据内容。
-
指针域（Next）：指向链表中的下一个节点的地址。
链表的特点是节点在内存中不需要连续存储，这与数组不同，数组的元素是连续存储在内存中的。由于这一特点，链表的插入和删除操作不涉及大量的元素移动，因此操作非常灵活、高效，尤其适合动态数据的管理。通过指针的连接，链表能够动态扩展，存储任意数量的节点，而不会像数组一样受到固定容量的限制。
链表结构示意图如下：
2. 基本结构
单链表的基本结构由节点和指针组成。每个节点包含数据部分和指向下一个节点的指针。下面是C语言中单链表节点的定义：
typedef int DataType;
typedef struct ListNode
{
DataType data;//数据域
struct ListNode* next;//指针域,指向下一个节点
}LN;每个节点通过 next 指针连接到下一个节点，最后一个节点的 next 指针为空（即指向 NULL），表示链表的终点。整个链表的入口称为头指针（Head Pointer），它指向第一个节点的位置。如果链表为空，头指针为 NULL。
三、单链表的优缺点
1. 优点
-
动态内存管理： 单链表在内存中不要求节点的连续存储，可以根据需求动态分配或释放内存，适应动态数据变化。
-
高效的插入和删除操作： 在链表的任意位置进行插入或删除操作时，只需调整相关节点的指针即可，时间复杂度为 O(1)，比数组的O(n)更加高效。
-
灵活性强： 单链表不需要在创建时就确定存储空间的大小，适合数据量不确定的场景。
2. 缺点
-
额外的内存开销： 每个节点需要存储一个指针，增加了内存使用。
-
访问效率低： 访问链表中的第 n 个元素时，需要从头节点开始依次遍历，时间复杂度为 O(n)，无法像数组那样通过下标快速访问。
-
不支持反向遍历： 单链表只能从头节点开始向后遍历，无法直接从尾部向前遍历。
四、单链表的常见操作
单链表的常见操作包括节点的插入、删除、查找、遍历和销毁。以下将详细介绍这些操作的实现方法，并提供相应的代码示例。
1. 创建节点
每个节点是链表的基本组成部分。以下代码用于创建一个新节点，并初始化节点中的数据和指针：
// 创建一个新节点
LN* CreateNode(DataType x) {
// 分配一个新的链表节点内存
LN* newnode = (LN*)malloc(sizeof(LN));
if (newnode == NULL) { // 判断内存分配是否成功
perror("malloc fail"); // 输出错误信息
exit(-1); // 程序退出，表示分配失败
}
newnode->data = x; // 设置节点的数据域
newnode->next = NULL; // 将节点的 next 指针置为 NULL
return newnode; // 返回新创建的节点
}2. 初始化（创建头节点）
链表的头节点作为链表的入口，初始化链表时，通常会先创建一个头节点（头节点的数据部分可以存储不使用的数据或空值）。以下代码用于初始化链表并创建头节点：
// 初始化链表，创建一个头节点
LN* ListInit() {
LN* headnode = CreateNode(0); // 创建一个头节点，数据域初始化为 0
return headnode; // 返回头节点
}3. 头插法
在链表的头部插入新节点（即在第一个元素之前插入新节点），时间复杂度为 O(1)：
// 在链表的头部添加节点
void ListPushHead(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* newnode = CreateNode(x); // 创建一个新节点
newnode->next = phead->next; // 新节点的 next 指向原头节点的下一个节点
phead->next = newnode; // 头节点的 next 指向新节点
}4. 尾插法
在链表的尾部插入新节点，时间复杂度为 O(n)：
// 在链表的末尾添加节点
void ListPushBack(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* newnode = CreateNode(x); // 创建一个新节点
LN* pcur = phead;
while (pcur->next != NULL) { // 遍历到链表的末尾
pcur = pcur->next;
}
pcur->next = newnode; // 将新节点添加到链表的末尾
}5. 头删法
删除链表头部的第一个节点，时间复杂度为 O(1)：
// 删除链表的头部节点
void ListDelHead(LN* phead) {
assert(phead); // 确保链表头节点不为空
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空，无法进行删除操作！\n");
return;
}
LN* temp = phead->next; // 保存头部节点
phead->next = phead->next->next; // 头节点的 next 指向原头部节点的下一个节点
free(temp); // 释放原头部节点的内存
}6. 尾删法
删除链表尾部的最后一个节点，时间复杂度为 O(n)：
// 删除链表的尾部节点
void ListDelBack(LN* phead) {
assert(phead); // 确保链表头节点不为空
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空，无法进行删除操作！\n");
return;
}
LN* pcur = phead;
while (pcur->next->next != NULL) { // 找到倒数第二个节点
pcur = pcur->next;
}
free(pcur->next); // 释放最后一个节点的内存
pcur->next = NULL; // 将倒数第二个节点的 next 置为 NULL
}
7. 查找
在链表中查找值为 x 的节点：
// 查找链表中值为 x 的节点
LN* ListFind(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead->next;
while (pcur) { // 遍历链表
if (pcur->data == x) { // 如果找到数据域等于 x 的节点
return pcur; // 返回该节点
}
pcur = pcur->next;
}
return NULL; // 没有找到则返回 NULL
}8. 指定位置前插入
在指定节点 pos 之前插入新节点：
// 在指定节点前插入新节点
void ListInsertFront(LN* phead, LN* pos, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead;
if (pos == NULL) { // 判断插入位置是否合法
printf("插入位置非法\n");
return;
}
while (pcur->next != pos) { // 找到 pos 的前一个节点
pcur = pcur->next;
}
LN* newnode = CreateNode(x); // 创建新节点
newnode->next = pos; // 新节点的 next 指向 pos
pcur->next = newnode; // 前一个节点的 next 指向新节点
}9. 指定位置后插入
在指定节点 pos 之后插入新节点：
// 在指定节点后插入新节点
void ListInsertBack(LN* pos, DataType x) {
if (pos == NULL) { // 判断插入位置是否合法
printf("插入位置非法\n");
return;
}
LN* newnode = CreateNode(x); // 创建新节点
newnode->next = pos->next; // 新节点的 next 指向 pos 的下一个节点
pos->next = newnode; // pos 的 next 指向新节点
}
10. 指定位置删除
删除指定位置 pos 处的节点：
// 删除指定位置的节点
void ListErase(LN* phead, LN* pos) {
assert(phead); // 确保链表头节点不为空
if (pos == NULL) { // 判断删除位置是否合法
printf("删除位置非法\n");
return;
}
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空，无法进行删除操作！\n");
return;
}
LN* pcur = phead;
while (pcur->next != pos) { // 找到 pos 的前一个节点
pcur = pcur->next;
}
pcur->next = pos->next; // 前一个节点的 next 指向 pos 的下一个节点
free(pos); // 释放 pos 的内存
}11. 打印链表
遍历并打印链表中的所有元素：
// 打印链表中的所有节点
void ListPrint(LN* phead) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead->next;
while (pcur) { // 遍历链表中的每个节点
printf("%d->", pcur->data); // 打印当前节点的数据
pcur = pcur->next;
}
printf("NULL\n"); // 链表结束时打印 NULL
}12. 销毁链表
释放链表中所有节点的内存，防止内存泄漏：
// 销毁链表，释放所有节点的内存
void ListDestroy(LN** pphead) {
LN* pcur = *pphead;
LN* temp = NULL;
while (pcur) { // 遍历链表并释放每个节点
temp = pcur->next;
free(pcur);
pcur = temp;
}
*pphead = NULL; // 将头指针置为 NULL
}五、完整代码
完整代码包括以下三部分：List.h、List.c 和 test.c，分别是链表的定义、链表操作函数的实现以及测试用例。
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct ListNode
{
DataType data;//数据域
struct ListNode* next;//指针域,指向下一个节点
}LN;
//创建节点
LN* CreateNode(DataType x);
// 初始化链表（创建头节点）
LN* ListInit();
//尾插
void ListPushBack(LN* phead, DataType x);
//头插
void ListPushHead(LN* phead, DataType x);
//尾删
void ListDelBack(LN* phead);
//头删
void ListDelHead(LN* phead);
//打印链表
void ListPrint(LN *phead);
//查找
LN* ListFind(LN* phead, DataType x);
//指定位置前插入
void ListInsertFront(LN* phead, LN*pos,DataType x);
//指定位置后插入
void ListInsertBack(LN* pos, DataType x);
//指定位置节点删除
void ListErase(LN*phead,LN*pos);
//销毁
void ListDestroy(LN**pphead);List.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
// 创建一个新节点
LN* CreateNode(DataType x) {
// 分配一个新的链表节点内存
LN* newnode = (LN*)malloc(sizeof(LN));
if (newnode == NULL) { // 判断内存分配是否成功
perror("malloc fail"); // 输出错误信息
exit(-1); // 程序退出，表示分配失败
}
newnode->data = x; // 设置节点的数据域
newnode->next = NULL; // 将节点的 next 指针置为 NULL
return newnode; // 返回新创建的节点
}
// 初始化链表，创建一个头节点
LN* ListInit() {
LN* headnode = CreateNode(0); // 创建一个头节点，数据域初始化为 0
return headnode; // 返回头节点
}
// 在链表的末尾添加节点
void ListPushBack(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* newnode = CreateNode(x); // 创建一个新节点
LN* pcur = phead;
while (pcur->next != NULL) { // 遍历到链表的末尾
pcur = pcur->next;
}
pcur->next = newnode; // 将新节点添加到链表的末尾
}
// 在链表的头部添加节点
void ListPushHead(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* newnode = CreateNode(x); // 创建一个新节点
newnode->next = phead->next; // 新节点的 next 指向原头节点的下一个节点
phead->next = newnode; // 头节点的 next 指向新节点
}
// 删除链表的尾部节点
void ListDelBack(LN* phead) {
assert(phead); // 确保链表头节点不为空
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空，无法进行删除操作！\n");
return;
}
LN* pcur = phead;
while (pcur->next->next != NULL) { // 找到倒数第二个节点
pcur = pcur->next;
}
free(pcur->next); // 释放最后一个节点的内存
pcur->next = NULL; // 将倒数第二个节点的 next 置为 NULL
}
// 删除链表的头部节点
void ListDelHead(LN* phead) {
assert(phead); // 确保链表头节点不为空
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空，无法进行删除操作！\n");
return;
}
LN* temp = phead->next; // 保存头部节点
phead->next = phead->next->next; // 头节点的 next 指向原头部节点的下一个节点
free(temp); // 释放原头部节点的内存
}
// 打印链表中的所有节点
void ListPrint(LN* phead) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead->next;
while (pcur) { // 遍历链表中的每个节点
printf("%d->", pcur->data); // 打印当前节点的数据
pcur = pcur->next;
}
printf("NULL\n"); // 链表结束时打印 NULL
}
// 查找链表中值为 x 的节点
LN* ListFind(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead->next;
while (pcur) { // 遍历链表
if (pcur->data == x) { // 如果找到数据域等于 x 的节点
return pcur; // 返回该节点
}
pcur = pcur->next;
}
return NULL; // 没有找到则返回 NULL
}
// 在指定节点前插入新节点
void ListInsertFront(LN* phead, LN* pos, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead;
if (pos == NULL) { // 判断插入位置是否合法
printf("插入位置非法\n");
return;
}
while (pcur->next != pos) { // 找到 pos 的前一个节点
pcur = pcur->next;
}
LN* newnode = CreateNode(x); // 创建新节点
newnode->next = pos; // 新节点的 next 指向 pos
pcur->next = newnode; // 前一个节点的 next 指向新节点
}
// 在指定节点后插入新节点
void ListInsertBack(LN* pos, DataType x) {
if (pos == NULL) { // 判断插入位置是否合法
printf("插入位置非法\n");
return;
}
LN* newnode = CreateNode(x); // 创建新节点
newnode->next = pos->next; // 新节点的 next 指向 pos 的下一个节点
pos->next = newnode; // pos 的 next 指向新节点
}
// 删除指定位置的节点
void ListErase(LN* phead, LN* pos) {
assert(phead); // 确保链表头节点不为空
if (pos == NULL) { // 判断删除位置是否合法
printf("删除位置非法\n");
return;
}
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空，无法进行删除操作！\n");
return;
}
LN* pcur = phead;
while (pcur->next != pos) { // 找到 pos 的前一个节点
pcur = pcur->next;
}
pcur->next = pos->next; // 前一个节点的 next 指向 pos 的下一个节点
free(pos); // 释放 pos 的内存
}
// 销毁链表，释放所有节点的内存
void ListDestroy(LN** pphead) {
LN* pcur = *pphead;
LN* temp = NULL;
while (pcur) { // 遍历链表并释放每个节点
temp = pcur->next;
free(pcur);
pcur = temp;
}
*pphead = NULL; // 将头指针置为 NULL
}test.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test1()
{
LN* phead = ListInit();//创建头节点，头指针指向头节点
ListPushHead(phead, 1);
ListPushHead(phead, 2);
ListPushHead(phead, 3);
//ListDelBack(phead);
//ListDelHead(phead);
//测试查找
LN * find = ListFind(phead,2);
/*if (find == NULL)
{
printf("没有找到!\n");
}
else
{
printf("找到了!\n");
}*/
//ListInsertFront(phead, find, 99);
//ListInsertBack(find,88);
//ListErase(phead, find);
ListPrint(phead);
//ListDestroy(&phead);
}
int main()
{
test1();
return 0;
}六、总结
单链表是一种简单而强大的数据结构，适用于动态数据存储和管理。通过本文，我们介绍了单链表的基本概念、常见操作及其实现。掌握单链表的操作可以帮助我们更好地解决实际编程问题，特别是在需要频繁插入和删除操作的场景中。
希望这篇博客对你理解和使用单链表有所帮助。如果你有任何问题或想进一步了解更多高级用法，请随时留言讨论！
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
85
0- 0
已为社区贡献2条内容
所有评论(0)