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

（数据结构）线性表（中）：SLIst单链表

news 2025/7/22 7:23:17

链表

链表是线性表的一种。链表⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
逻辑结构线性，物理结构（绝大多数情况下）非线性。
结构：链表是由结点组成的，而结点=存储数据+指向下一数据的指针
在这里插入图片描述

单链表的构建

  • 思考的角度：前提条件、基本实现方法、需要特殊考虑的情况、什么代码可以复用
  • 测试时调用函数关注一下参数有没有传错！

结点

typedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;

注意：C语言是向上编译的，所以在取别名SLTNode前就使用这个别名会导致报错，因为使用之前并没有取好别名！所以定义next指针还是要写struct SListNode* next

遍历与打印单链表

void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur != NULL) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

初始化新结点

//向操作系统申请一个新结点并初始化
SLTNode* SLTBuyNode(SLTDataType x) {//创建新结点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("Malloc fail!");exit(1);}//将数据存入新节点newnode->data = x;newnode->next = NULL;return newnode;
}

尾插

注意要点：

  1. 当头节点是空指针时，需要修改指针本身的值，使其指向创建的新结点，所以注意要进行传址传参，即参数是二级指针SLTNode** pphead，同时因为代码中要用到*pphead，注意到NULL不可以解引用的原则，增加断言assert(pphead)
    3. 要对尾结点进行操作，需要找到的是ptail->next的这个点，而不是ptail=NULL的点，这个点已经越过了。
void SLTPushBack(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL) {*pphead = newnode;}else {SLTNode* ptail = *pphead;while (ptail->next) {//等价于ptail->next！=NULL，即遍历到尾节点ptail = ptail->next;}ptail->next = newnode;}
}

为什么我们遍历的时候，总是重新定义一个新指针SLTNode* ptail = *pphead; ``SLTNode* pcur = phead来进行遍历？
因为我们要保留好头节点的地址，防止后续还要使用到前面的数据时出现困难。

头插

看参数传的是一级还是二级指针，就思考方法是否要改变指针本身的指向，即其本身的值
注意：

  1. phead永远指向头结点
  2. 初始链表为空时让phead直接指向新结点
    在单链表中，头插的时间复杂度仅为O(1)
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode=SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

尾删

  1. 当链表为空时（*pphead=NULL)，删除操作就没有意义，所以把这个条件加入assert中判断,同时pphead仍然不能为NULL。
  2. 当链表中只有一个结点时，即删除的是头节点时，要改变phead的指向，所以函数参数仍然是二级指针pphead。
    ->操作符优先级高于*操作符，所以条件注意写成（*pphead)->next==NULL
  3. 当链表中有多个结点时，首先要找到尾结点的前一个结点指针prev，将prev->next=NULL（直接释放尾节点，prev->next会成为野指针）才能释放尾节点。
  4. 删除操作需要注意的点：关注野指针，free+置空
//尾删
void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead);//只有一个结点的情况if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next) {prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;//free完任何指针以后都要置空！}
}

头删

  1. 每一个结点一一相连，所以头结点不能直接释放掉，而是要先找到第二个结点存起来，再释放掉第一个结点。
  2. 检验当链表中只有一个结点时，和有多个结点的方法可以通用。
//头删
void SLTPopFront(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

查找

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* pcur = phead;//注意这里是遍历链表，而不是找到尾结点！//所以条件是pcur而不是pcur->next！！！while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}//未找到return NULL;
}

在指定位置之前插入数据

  1. 链表为空或pos为NULL时功能没有意义
  2. 链表的位置用结点的指针表示
  3. 分只有一个结点和有多个结点两种情况
  4. 有多个结点时，先找到pos的前一个结点，用prev存储
//在pos前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {//传入的结点位置为空是没有意义的assert(pphead&&pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead) {//pos是头结点时，等价于头插SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

在指定位置之后插入数据

先让newnode接上pos->next，再让pos->next指向newnode，直接调换顺序是不行的

//在pos后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;//注意这两步不能直接调换！
}

删除指定位置的结点

  • 已知指定位置结点时，什么时候要传入头结点？
    当需要找指定位置之前的结点时要传入，因为单链表只能从前往后找，而无法从后往前回找。
  • 可复用的代码尽量复用
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {//pphead为空、pos为空都没意义（不用特地强调链表为空，因为pos不为空显然链表就不会为空了）assert(pphead && pos);//如果删除的是头结点要单独讨论，否则下面代码会出错if (pos == *pphead) {SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

删除指定位置之后的结点

  1. 前提条件：pos之后的结点不能为空（删除一个空结点没有意义）
  2. 不需要传头结点了，因为这里只涉及pos及它之后的结点操作
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos) {//pos之后的结点若为空，这个功能也没有意义assert(pos && pos->next);//先储存要删除的pos的下一个结点，否则一会pos改变指向了找不到SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

销毁链表

//销毁链表
void SListDestroy(SLTNode** pphead) {assert(pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;//这是让函数外的头指针本身置空
}

完整代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;}SLTNode;//遍历并打印链表
void SLTPrint(SLTNode* phead);
//向操作系统申请一个新结点并初始化
SLTNode* SLTBuyNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur != NULL) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//向操作系统申请一个新结点并初始化
SLTNode* SLTBuyNode(SLTDataType x) {//创建新结点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("Malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL) {*pphead = newnode;}else {SLTNode* ptail = *pphead;while (ptail->next) {//等价于ptail->next！=NULL，即遍历到尾节点ptail = ptail->next;}ptail->next = newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode=SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead);//只有一个结点的情况if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next) {prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;//free完任何指针以后都要置空！}
}//头删
void SLTPopFront(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* pcur = phead;//注意这里是遍历链表，而不是找到尾结点！//所以条件是pcur而不是pcur->next！！！while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}//未找到return NULL;
}
//在pos前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {//传入的结点位置为空是没有意义的assert(pphead&&pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead) {//pos是头结点时，等价于头插SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}
//在pos后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;//注意这两步不能直接调换！
}
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {//pphead为空、pos为空都没意义（不用特地强调链表为空，因为pos不为空显然链表就不会为空了）assert(pphead && pos);//如果删除的是头结点要单独讨论，否则下面代码会出错if (pos == *pphead) {SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos) {//pos之后的结点若为空，这个功能也没有意义assert(pos && pos->next);//先储存要删除的pos的下一个结点，否则一会pos改变指向了找不到SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//销毁链表
void SListDestroy(SLTNode** pphead) {assert(pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;//这是让函数外的头指针本身置空
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"void test01() {SLTNode* plist=NULL;//创建头节点->创建空链表SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);
}void test02() {SLTNode* plist = NULL;//创建头节点->创建空链表SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopBack(&plist);SLTPopBack(&plist);SLTPrint(plist);
}
void test03() {SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);//SLTNode* ret=SLTFind(plist, 3);SLTNode* ret = SLTFind(plist, 333);if (ret!=NULL) {printf("找到了\n");}else {printf("没找到\n");}
}void test04() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTNode* pos1 = SLTFind(plist, 2);SLTInsert(&plist, pos1, 100);SLTPrint(plist); SLTNode* pos2 = SLTFind(plist, 4);SLTInsertAfter(pos2, 200);SLTPrint(plist);pos1 = SLTFind(plist, 2);SLTErase(&plist, pos1);SLTPrint(plist);//C 语言所有参数都是“按值传递”//	你传进去的是指针变量的值（也就是那块内存的地址），函数内部拿到的只是一个 副本。//	因此在函数里：//	c//	复制//	free(pos);   // 释放的是 p 指向的那块内存//  pos = NULL;  // 只把副本改成 NULL，外面的原指针依旧保留原来的地址值//结果：//	• 内存确实被释放了；//	• 外部变量pos1仍保存着 已释放的地址（野指针）；//	• 外部再解引用就是 未定义行为（可能崩溃、可能脏数据）。pos2 = SLTFind(plist, 4);SLTEraseAfter(pos2);SLTPrint(plist);
}int main() {test04();return 0;
}

总结

在完整实现顺序表和链表之后，我们可以对他们进行对比分析。

  • 链表在头部(O(1))和中间的插入删除时间复杂度小于顺序表
    在这里插入图片描述

  • 链表不需要进行增容，开一个用一个，没有额外的空间浪费

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

相关文章：

  • tcpdump 命令解析（随手记）
  • IOPaint+CPolar：零公网IP也能搭建专属AI图像编辑平台
  • 高级技术【Java】【反射】【注解】【动态代理】
  • 复习博客：JVM
  • 【Project】ELK 7.17.16 日志分析系统部署
  • 阿里云平台使用的ack创建的pod与服务器中的MongoDB不在同一网段如何解决
  • 【图像处理基石】什么是相机的内外参数？
  • 单表查询-分页提前获取数据
  • 自动化与安全 - 将 Terraform 集成到 CI/CD
  • 安装pytorch（cpu版）
  • 电科金仓2025发布会，国产数据库的AI融合进化与智领未来
  • 【Lucene】SimScorer
  • 【Spring AI】Advisors API—顾问（即拦截器）
  • 轨迹优化 | 基于边界中间值问题(BIVP)的路径平滑求解器(附C++/Python仿真)
  • 6.String、StringBuffer、StringBuilder区别及使用场景
  • C++学习笔记（六：数组）
  • AI Agent与MCP Service技术进展结构化分析报告（2025Q2）
  • 解决win10下Vmware虚拟机在笔记本睡眠唤醒后ssh连接不上的问题
  • 项目研发进度安排
  • 音视频学习（四十二）：H264帧间压缩技术
  • 【时时三省】(C语言基础)使用字符指针变量和字符数组的比较
  • Electron使用WebAssembly实现CRC-16 原理校验
  • Java 二叉树
  • C++11之右值引用与移动语义（提高效率）重要
  • 【Linux指南】Linux系统 -权限全面解析
  • Jetpack ViewModel LiveData：现代Android架构组件的核心力量
  • 病历数智化3分钟：AI重构医院数据价值链
  • AI+Python | 长时序植被遥感：动态·物候·变异归因·RSEI生态评估全流程[特殊字符]
  • C语言（20250718）
  • 车载电子电器架构 --- MCU信息安全相关措施