您现在的位置是：首页 >学无止境 >单向链表——C语言实现网站首页学无止境
单向链表——C语言实现
简介单向链表——C语言实现
哈喽，大家好，今天我们学习的是数据结构里的链表，这里主要讲的是不带哨兵卫头节点的单向链表，下篇将会继续带大家学习双向链表。
目录
1.链表的概念
在上篇文章，我们已经学习了顺序表，不知大家有没有发现顺序表在一定程度上是存在缺陷的，比如说：
- 空间不够了的时候需要扩容，扩容需要付出代价（特别是异地扩空间）
- 为了避免频繁扩容，我们满了基本都是扩2倍，可能会导致一定的空间浪费
- 顺序表要求数据从开始位置连续存储，那么我们在头部或者中间位置插入删除数据就需要挪动数据，效率不高
针对顺序表的缺陷，就有了链表来存储数据
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表的定义：
这里的data就是要存放的数据
2.单向链表接口的实现
下面是要介绍的常用到的链表接口函数以及实现方法：
//打印
void SListPrint(SLTNode* phead);
//创建新节点
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//头删
void SListPopBack(SLTNode** pphead);
//尾删
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//删除
void SListErase(SLTNode** pphead, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pphead);
2.1动态申请一个节点
由于我们每次给链表插入数据时，都需要动态开辟空间来申请节点，所以我们把这个过程封装成一个函数，方便后续操作。
动态申请一个节点的步骤是先向计算机内存申请一块空间，这里我们将申请的空间用指针变量newnode来存储，然后将newnode中的data赋值，因为这是新开辟的节点，所以暂时将newnode中的next指向空。
注意：为了提高程序的可靠性，我们在动态内存申请后记得检查是否申请失败了，如果申请失败了输出提示信息，并退出程序。
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)//如果动态内存申请失败就退出程序
{
printf("malloc fail
");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}2.2单链表打印
打印链表就是一个遍历链表的过程，我们首先定义一个指针(cur)指向链表的头节点，然后输出该节点的值，然后将指针指向下一个节点（cur=cur->next),依次进行，直到cur为空指针时停止
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;//将cur指向下一个节点
}
printf("NULL
");
}2.3单链表尾插
尾插，就是先找到链表中最后一个节点，然后将数据插入到最后。
但是，我们要先判断链表是否为空，如果链表为空，我们直接直接将链表的头指针赋予要插入的数据。
由于尾插要改变链表，所以传参要用二级指针，包括下面的尾插，尾删，头删等都要用二级指针传参
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}2.4单链表头插
头插是比较简单的一种操作，只需要申请新节点，将新节点的next指向链表的头，再让新节点成为链表的头即可。
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}2.5单链表尾删
尾删：每次找到链表的最后一个节点和倒数第二个节点，然后释放最后一个节点所占的看空间并将最后一个节点置空，同时将倒数第二个节点的next指向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 != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}2.6单链表头删
头删是将第一个节点释放然后指向第二个节点，在此之前需要定义一个指针next来保存第二个节点的地址。
void SListPopFront(SLTNode** pphead)
{
//保证链表不是空链表
assert(*pphead != NULL);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}2.7在pos位置插入x
在pos位置插入x分为两种情况，一种是在pos前位置插入x ，另一种是在pos后位置插入x，下面将分别为大家介绍：
2.7.1在pos位置前插入x
在pos位置前插入x,只需要找到pos的前一个位置，我们把pos的前一个位置命名为posPrev，然后创建一个新节点newnode，将posPrev的下一个节点指向newnode，newnode的下一个节点指向pos即可，如下图：
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead != NULL);
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
//找到pos的前一个位置
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
}2.7.2在pos位置后插入x
在pos位置后插入x比在pos位置前插入x要简单，不需要遍历链表即可完成
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}2.8删除pos位置值
删除pos位置值也需要先找到pos的前一个节点，因此也要考虑pos是链表的头节点的情况
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead != NULL);
assert(pos != NULL);
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}2.9 查找x的地址
查找x的地址，如果查找到了x，则返回该节点的地址，否则返回空指针。这个步骤也要遍历链表。
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* tail = phead;
if (tail->data == x)
{
return tail;
}
while (tail ->data != x)
{
tail = tail->next;
if (tail->data == x)
{
return tail;
}
}
return NULL;
}2.10销毁链表
销毁链表需要将所有节点所占的内存全部释放，再将链表的头置为空即可。
void SListDestroy(SLTNode** pphead)
{
assert(*pphead != NULL);
SLTNode* cur = *pphead;
while (cur != NULL)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}3.完整代码
SList.h文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;//存放下一个链表的地址
}SLTNode;
//打印
void SListPrint(SLTNode* phead);
//创建新节点
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//头删
void SListPopBack(SLTNode** pphead);
//尾删
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//删除
void SListErase(SLTNode** pphead, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pphead);SList.c文件：
#include"SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;//将cur指向下一个节点
}
printf("NULL
");
}
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)//如果动态内存申请失败就退出程序
{
printf("malloc fail
");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
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 != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}
void SListPopFront(SLTNode** pphead)
{
//保证链表不是空链表
assert(*pphead != NULL);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* tail = phead;
if (tail->data == x)
{
return tail;
}
while (tail ->data != x)
{
tail = tail->next;
if (tail->data == x)
{
return tail;
}
}
return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead != NULL);
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
//找到pos的前一个位置
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
}
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead != NULL);
assert(pos != NULL);
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}
void SListDestroy(SLTNode** pphead)
{
assert(*pphead != NULL);
SLTNode* cur = *pphead;
while (cur != NULL)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}总结：这篇文章主要写的是单向链表，后续将继续带领大家学习双向链表。如果我写的有什么的不好之处，请在文章下方给出你宝贵的意见。如果觉得我写的好的话请点个赞赞和关注哦~😘
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效)