当前位置： 首页 > news >正文

（数据结构）链表

news 2025/8/9 10:19:17

1.单向链表

1.1单链表的认识

#pragma once
#include<stdio.h>
//SList.h
typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;void SListPrint(SLTNode* phead);

定义一个struct SListNode类型的结构体，这个结构体的变量名是SLTNode，这个结构体（节点）有两个成员，一个用来存放SLTDateType（这里是int类型，可以根据实际需求更改）类型的数据，另一个成员是一个struct SListNode类型的指针，存放下一个节点的地址，就是指向下一个struct SListNode类型的结构体，下一个结构体也有一个指向下下个结构体的指针。

打印链表：

首先定义一个STList类型的指针cur存放头节点（链表第一个结构体）的地址，通过cur指针可以找到头节点存放的数据以及下一个节点的地址，这样就可以打印出链表的数据，最后一个节点的地址为空。

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
//SList.c
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}
}

1.2尾插

在链表尾部插入一个节点：

1.首先找到要插入链表的最后一个节点，此时tail->next=NULL

2.新开辟一个节点，初始化这个节点，这个新节点的指针域指向NULL

3.令原先的最后一个节点指向这个新节点

//在链表的尾部插入一个新的节点
void SListPushBack(SLTNode* phead, SLTDateType x)
{SLTNode* tail = phead;while (tail->next != NULL){tail=tail->next;}SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;tail->next = newnode;
}

需要注意

plist的值拷贝给phead，但是phead的改变不会影响plist，他们不是同一块空间，phead出了函数之后被销毁，plist还是空指针

要改变int*，要传int**。

通俗一点来说就是，如果我有一个int类型的变量a，我想通过函数传参的方式改变a的值，因为形参是实参的临时拷贝,如果形参直接传int类型，形参相当于是内存新开一块空间拷贝实参的内容，你所定义的函数操作的实际上是操作这块新空间；

所以我们如果想改变实参，需要传实参的地址，现在形参相当于是内存新开一块空间存放实参的地址，我们在函数中对这个地址进行解引用就能找到实参；

使用实例：

//在链表的尾部插入一个新的节点
void SListPushBack(SLTNode** pphead, SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;if (*pphead == NULL){*pphead = newnode;}else{//找到最后一个节点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}        tail->next = newnode;}
}void test1()
{SLTNode* plist=NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);
}int main()
{test1();return 0;
}

下面我再举一个例子加深一下对这个问题的理解：

情况1：这相当于把p存的地址的值传给形参，形参相当于实参的临时拷贝，会再开一块空间存形参，函数相当于把形参的值改为NULL但是不影响实参

情况2：

//情况2
void x(int* j)
{*j = NULL;
}int main()
{int* p = 0x1234;x(p);
}

而对形参j解引用就找到了这块空间，而*j=NULL相当于把j指向这块空间的值置为0

情况3：

//情况3
void x(int** j)
{*j = NULL;
}int main()
{int* p = 0x1234;x(&p);
}

地址是假设的）这次传的是p的地址，对j解引用 就可以找到p，从而改变p

1.3头插

新建一个节点，这个节点的指针指向这个链表的头节点

//头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{//新建一个节点SLTNode* newnode = BuySTLNode(x);//这个是新建节点的函数if (newnode == NULL){exit(-1);}newnode->next = *pphead;*pphead = newnode;        
}

1.4尾删

先看一下存在问题的写法

//尾删
void SListPopBack(SLTNode** pphead)
{SLTNode* tail = *pphead;//while(tail->next) 两种写法是等价的while (tail->next != NULL){tail = tail->next;} free(tail);tail = NULL;
}

没有把前一个节点的指针置空，造成野指针问题

除此之外，我们还要考虑如果链表为空，或者只有一个节点的情况

//尾删
void SListPopBack(SLTNode** pphead)
{assert(*pphead != NULL);//满足括号中的条件才可以继续往下执行if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;//再定义一个指针//while(tail->next) 两种写法是等价的while (tail->next != NULL){prev = tail;//tail指向下一个节点之前，存放上一个节点的地址tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;//把前一个节点的指针置空}//这样写就可以少定义一个变量/*SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;*/
}

1.6寻找节点

//寻找数据x的节点
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}elsecur = cur->next;}return NULL;
}

1.7在pos位置之前插入一个节点

//在pos位置之前插入一个节点
void SListInsert_Front(SLTNode** pphead, SLTDateType* pos, SLTDateType x)
{SLTNode* newnode = BuySTLNode(x);SLTNode* posPrev = *pphead;if (*pphead == pos)//单独分析pos是头节点的情况{newnode->next = *pphead;*pphead = newnode;}else{//找到pos的前一个位置while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newnode;newnode->next = pos;}        
}

1.8在pos位置之后插入一个节点

//在pos位置之后插入一个节点
void SListInsert_Afert(SLTNode* pos, SLTDateType x)
{SLTNode* newnode = BuySTLNode(x);newnode->next = pos->next;pos->next = newnode;}

2.双向链表

链表的结构

哨兵位的头节点不存储有效数据

1.无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2.带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

LTNode* ListInit()
{//哨兵位头节点，单单改变形参不能让plist拿到头节点，可以用二级指针，也可以返回地址LTNode* phead = (LTNode*)malloc(sizeof(LTNode));phead->next = phead;phead->prev = phead;return phead;
}void ListPushBack(LTNode* phead, LTDateType x)
{assert(phead);LTNode* tail = phead->prev;//画图理解LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;tail->next = newnode; //前一个节点的尾指向新节点newnode->prev = tail; //新节点的头指向前一个节点的尾newnode->next = phead; //新节点的尾指针指向哨兵位phead->prev = newnode; //哨兵位的头指针指向新节点
}

这里指针指向的都是结构体（即节点），不是结构体的某个成员，如tail->next = newnode; 意思是前一个节点的尾指向新节点，而不是新节点的前节点指针域newnode->prev；

不改变phead，不用传二级指针

以下是双向链表的尾插，头插，尾删，头删等操作，和单向链表相差无几，重要的是学会画图分析

//List.h
typedef int LTDateType;typedef struct ListNode
{LTDateType data;struct ListNode* next;struct ListNode* prev;
}LTNode;
//双向链表初始化
LTNode* ListInit();
//打印双向链表，从哨兵位的下一个节点开始打印，到哨兵位结束打印
void ListPrint(LTNode* phead);//尾插
void ListPushBack(LTNode* phead, LTDateType x);
//尾删
void ListPopBack(LTNode* phead);
//头插
void ListPushFront(LTNode* phead, LTDateType x);
//头删
void ListPopFront(LTNode* phead);
//寻找x的节点
LTNode* ListFind(LTNode* phead, LTDateType x);
//pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x);
//删除pos位置
void ListErase(LTNode* pos);
void ListDestroy(LTNode* phead)；
//尾删
void ListPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;LTNode* tailnode = tail;tail = tail->prev;phead->prev = tail;tail->next = phead;free(tailnode);
}
//头插
void ListPushFront(LTNode* phead, LTDateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}
//头删
void ListPopFront(LTNode* phead)
{//记录头节点地址LTNode* headnode = phead->next;headnode->next->prev = phead;phead->next = headnode->next;free(headnode);
}//寻找x的节点
LTNode* ListFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}}return NULL;
}
//pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;pos->prev->next = newnode;newnode->prev = pos->prev;pos->prev = newnode;newnode->next = pos;
}
//删除pos位置
void ListErase(LTNode* pos)
{LTNode* prevnode = pos->prev;prevnode->next = pos->next;pos->next->prev = prevnode;free(pos);
}
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

有错误欢迎在评论区指出。

上一篇：

（数据结构）顺序表实现-增删查改-CSDN博客

http://www.lryc.cn/news/614365.html

相关文章：

  • 从零开始构建【顺序表】：C语言实现与项目实战准备
  • Autosar AP中Promise和Future的异步消息通信的详细解析
  • 深入理解VideoToolbox：iOS/macOS视频硬编解码实战指南
  • FreeRTOS入门知识（初识RTOS）（二）
  • 2025-08-08 李沐深度学习11——深度学习计算
  • 【网络运维】Linux：MariaDB 数据库介绍及管理
  • duxapp 2025-06-04 更新 UI库导出方式更新
  • Java学习Collection单列集合中的三种通用遍历方法
  • 【洛谷题单】--分支结构(二)
  • [GESP202506 五级] 最大公因数
  • 豆包新模型矩阵+PromptPilot：AI开发效率革命的终极方案
  • 矩阵中的最长递增路径-记忆化搜索
  • Maven/Gradle常用命令
  • STM32CubeMX（十二）SPI驱动W25Qxx（Flash）
  • 恶臭气体在线监测仪器：实时、连续监测环境中恶臭气体浓度
  • c++初学day1（类比C语言进行举例,具体原理等到学到更深层的东西再进行解析）
  • （已解决）IDEA突然无法使用Git功能
  • 杂谈 001 · VScode / Copilot 25.08 更新
  • 关于“致命错误：‘https://github.com/....git/‘ 鉴权失败”
  • Spring Boot 结合 CORS 解决前端跨域问题
  • 《常见高频算法题 Java 解法实战精讲（3）：排序与二叉树》
  • 2025小程序怎么快速接入美团核销，实现自动化核销
  • Ignite 资源注入核心：GridResourceProcessor 详解
  • Nestjs框架: 接口安全与响应脱敏实践 --- 从拦截器到自定义序列化装饰器
  • PEV2(PostgreSQL Explain Visualizer 2)
  • Windows 定时开关机终极指南
  • 为什么通过CreateThread创建的线程调用C/C++运行库函数不稳定
  • 代码随想录刷题Day26
  • 【Git】企业级使用
  • 路由器不能上网的解决过程