目录
一.链表的基本概念和结构
二.链表的分类
三.单链表的基本操作
1.创建一个节点
2.打印
3.尾插
4.头插
5.尾删
6.头删
7.查找
8.指定位置插入
9.指定位置删除
10.销毁
一.链表的基本概念和结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
结构：链表是有各个节点通过指针连接在一起的，每个节点分为数据域和指针域，每个节点的指针域指向下一个节点的地址，最后一个节点的指针域为空。
逻辑结构如下图所示
物理结构：逻辑结构看起来是连续的，但是由于链表的节点是在堆上开辟的，地址可能连续，也可能不连续
二.链表的分类
1.单向和双向：
2. 带头和不带头
3.循环和不循环
通过上面三种分类我们可以得知，组合起来链表总共有8中结构，但是我们经常使用的不带头无循环单链表和带头双向循环链表，此篇文章暂时只讨论第一种结构的基本操作
三.单链表的基本操作
单链表的基本操作有尾插、尾删、头插、头删、指定位置插入、指定位置删除、查找、销毁等操作，下面我们来实现这些操作
// 1 、无头 + 单向 + 非循环链表增删查改实现 typedef int SLTDateType ; typedef struct SListNode { SLTDateType data ; struct SListNode * next ; } SListNode ; // 动态申请一个结点 SListNode * BuySListNode ( SLTDateType x ); // 单链表打印 void SListPrint ( SListNode * plist ); // 单链表尾插 void SListPushBack ( SListNode ** pplist , SLTDateType x ); // 单链表的头插 void SListPushFront ( SListNode ** pplist , SLTDateType x ); // 单链表的尾删 void SListPopBack ( SListNode ** pplist ); // 单链表头删 void SListPopFront ( SListNode ** pplist ); // 单链表查找 SListNode * SListFind ( SListNode * plist , SLTDateType x ); // 单链表在 pos 位置之后插入 x void SListInsertAfter ( SListNode * pos , SLTDateType x ); // 单链表删除 pos 位置之后的值 void SListEraseAfter ( SListNode * pos );1.创建一个节点
链表和顺序表一样，依然是使用结构体来实现，然后利用动态内存管理函数开辟相应的空间，结构体含有一个数据变量和指针变量
SListNode* BuySListNode(SLTDateType x)//传入数据变量
{
SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));//开辟一个节点
if (newnode == NULL)//检查是否开辟成功
{
perror("SLTBynode error");
return NULL;
}
newnode->data = x;//将数据变量赋给data
newnode->next = NULL;//指针变量初始化为空指针
return newnode;//返回开辟的节点地址
}
2.打印
打印链表和打印顺序表思想相似，从前到后一次遍历每个节点并打印数据变量，链表访问下一个节点需要找到下一个节点的地址，而下一个的地址存储在当前指针指向的节点的指针域，所以要使指针的值改为当前节点的指针域，此时指针便指向了下一个节点了，即cur=cur->next,使指针指向下一个节点
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;//定义一个临时指针进行遍历，最好不要动头结点
while (cur)//指针进行遍历，直到指针指向空即遍历结束
{
printf("%d->", cur->data);//打印链表数据变量
cur = cur->next;//指针指向下一个节点
}
printf("NULL\n");
}
3.尾插
尾插即将新节点插入到链表的尾部，插入过程：先调用开辟节点的函数开辟一个新节点，如果链表为空，则直接将头指针指向新节点，如果非空，链表的最后一个节点指针域通常为空，所以我们需要一个临时指针找到链表的最后一个节点，然后将最后的节点指针域指向新节点，如图所示
void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);//创建一个新节点
if (*pplist == NULL)
{
*pplist = newnode;//如果链表是空则直接将头结点指向新节点
}
else
{
SListNode* cur = *pplist;//定义一个临时指针，遍历找到尾节点
while (cur->next)//直到最后一个节点结束
{
cur = cur->next;//指针往后走一个节点
}
cur->next = newnode;//将尾节点的指针域指向新节点
}
}
4.头插
链表的头插即将新节点插入到链表最前面，成为链表的第一个节点，插入过程：先调用开辟节点的函数创建一个新节点，若链表为空，则直接将头结点直接指向新节点，若非空，将新节点的指针域指向第一个节点，然后将链表的头指针指向新节点，如图所示
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);//开辟新节点
if (*pplist == NULL)
{
*pplist = newnode;//若链表为空表，则直接将头指针指向新节点
}
else
{
newnode->next = *pplist;//新节点的指针域指向链表
*pplist = newnode;//头指针指向新向新节点
}
}
5.尾删
链表的尾删即删去链表的最后一个节点，删除过程：先判断链表是否为空，为空则不能删除，我们用assert断言函数检查链表是否为空表，若非空，如果只有一个节点，我们只需要删除这个节点然后将头指针置空，如果不止一个节点，我们需要找到最后一个节点的前面的一个几点，然后通过前一个的节点指针域释放最后一个节点，此时前一个节点变成新的最后一个节点，因此我们需要将其指针域置空，如图所示
void SListPopBack(SListNode** pplist)
{
assert(*pplist);//判断链表是否为空
SListNode* cur = *pplist;//定义临时指针,用来找到最后一个节点的前一个节点
if ((*pplist)->next == NULL)//判断是否只有一个节点
{
free(*pplist);//删除这个节点
*pplist = NULL;//头指针置空
}
else
{
while (cur->next->next)//遍历到最后一个节点的前一个节点
{
cur = cur->next;
}
free(cur->next);//删除最后一个元素
cur->next = NULL;//前一个节点已成新的最后一个元素，指针域置空
}
}
6.头删
链表的头删即删去链表的第一个节点，删除过程：先判断链表是否为空，为空则不能删除直接退出函数，如果只有一个节点，则直接将该节点删除，然后将头指针置空，如果不止一个节点，则需要一个临时指针指向第二个节点，通过头指针将第一个元素删除，此时第二个节点成为新的第一个节点，然后将头指针指向临时指针，即头指针指向新的第一个节点，如图所示
void SListPopFront(SListNode** pplist)
{
assert(*pplist);//判断链表是否为空
SListNode* cur = *pplist;//定义临时指针指向第二个节点
if ((*pplist)->next == NULL)//判断是否只有一个节点
{
free(*pplist);//删除该节点
*pplist = NULL;//头指针置空
}
else
{
cur= cur->next;//临时指针指向第二个节点
free(*pplist);//删除第一个节点
*pplist = cur;//头指针指向第二个节点
}
}
7.查找
链表的查找和顺序表思想相似，从前往后遍历每个节点的数据与查找的数据相比较，相等则返回该节点的地址，找不到则返回NULL
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;//定义临时指针遍历链表
while (cur)//临时指针为空则遍历结束
{
if (cur->data == x)//节点的数据和查找的数据比较
return cur;//返回该节点的地址
cur = cur->next;//临时指针往后走一个节点
}
return NULL;//没有找到则返回空
}
8.指定位置插入
链表指定位置一般是在指定位置后面插入元素，插入元素过程：先判断位置是否合法，在创建一个新节点，然后通过给定位置的next找到后面一个节点，然后将新节点的指针域指向后面一个节点，然后指定位置指针域指向新节点，如图所示
特别值得注意的是，图中的1和2顺序不能倒过来，如果倒过来，即先让指定位置指针域先指向新指针，就找不到指定位置的后一个节点了
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);//判断位置是否合法
SListNode*newnode=BuySListNode(x);//创建新节点
newnode->next = pos->next;//新节点指针域指向指定位置后一个节点
pos->next = newnode;//指定位置指针域指向新节点
}
9.指定位置删除
链表的指定位置删除一般是删除指定位置之后的节点，删除过程：先判断位置是否合法，然后需要定义一个临时指针找到给定位置的后一个节点，然后将指定位置指针域指向要删除的节点后一个节点，然后再删除指定位置后一个节点，如图所示
void SListEraseAfter(SListNode* pos)
{
assert(pos&&pos->next);//判断位置是否合法
SListNode* cur = pos->next;//定义临时指针指向指定位置的后一个节点
pos->next = pos->next->next;//让指定位置指针域指向要删除节点的后一个接地那
free(cur);//删除指定位置后一个节点
}
10.销毁
单链表的销毁需要两个临时指针，第一个指针指向前面一个元素，第二个指针指向后一个元素，依次从前往后遍历，删除掉第一个指针指向的节点，然后第一个指针指向第二个指针指向的节点，第二个指针往后走一个节点，然后继续删除掉第一个指针指向的节点，知道第二指针指向为空，此时第一个指针指向最后一个节点，再继续删除掉第一个指针指向的节点，即全部删除完成
void SListDestroy(SListNode* plist)
{
SListNode* cur = plist;//定义第一个临时指针，指向相对前一个节点
SListNode* next = plist;//定义第二个临时指针，指向相对前一个节点
while (next)//遍历，直到第二个节点指向空
{
cur = next;
next = next->next;
free(cur);
}
}
以上就是单链表的一些基本操作，下面看全部代码：
SList.c
#include"SList.h"
SListNode* BuySListNode(SLTDateType x)//传入数据变量
{
SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));//开辟一个节点
if (newnode == NULL)//检查是否开辟成功
{
perror("SLTBynode error");
return NULL;
}
newnode->data = x;//将数据变量赋给data
newnode->next = NULL;//指针变量初始化为空指针
return newnode;//返回开辟的节点地址
}
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;//定义一个临时指针进行遍历，最好不要动头结点
while (cur)//指针进行遍历，直到指针指向空即遍历结束
{
printf("%d->", cur->data);//打印链表数据变量
cur = cur->next;//指针指向下一个节点
}
printf("NULL\n");
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);//创建一个新节点
if (*pplist == NULL)
{
*pplist = newnode;//如果链表是空则直接将头结点指向新节点
}
else
{
SListNode* cur = *pplist;//定义一个临时指针，遍历找到尾节点
while (cur->next)//直到最后一个节点结束
{
cur = cur->next;//指针往后走一个节点
}
cur->next = newnode;//将尾节点的指针域指向新节点
}
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);//开辟新节点
if (*pplist == NULL)
{
*pplist = newnode;//若链表为空表，则直接将头指针指向新节点
}
else
{
newnode->next = *pplist;//新节点的指针域指向链表
*pplist = newnode;//头指针指向新向新节点
}
}
void SListPopBack(SListNode** pplist)
{
assert(*pplist);//判断链表是否为空
SListNode* cur = *pplist;//定义临时指针,用来找到最后一个节点的前一个节点
if ((*pplist)->next == NULL)//判断是否只有一个节点
{
free(*pplist);//删除这个节点
*pplist = NULL;//头指针置空
}
else
{
while (cur->next->next)//遍历到最后一个节点的前一个节点
{
cur = cur->next;
}
free(cur->next);//删除最后一个元素
cur->next = NULL;//前一个节点已成新的最后一个元素，指针域置空
}
}
void SListPopFront(SListNode** pplist)
{
assert(*pplist);//判断链表是否为空
SListNode* cur = *pplist;//定义临时指针指向第二个节点
if ((*pplist)->next == NULL)//判断是否只有一个节点
{
free(*pplist);//删除该节点
*pplist = NULL;//头指针置空
}
else
{
cur= cur->next;//临时指针指向第二个节点
free(*pplist);//删除第一个节点
*pplist = cur;//头指针指向第二个节点
}
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;//定义临时指针遍历链表
while (cur)//临时指针为空则遍历结束
{
if (cur->data == x)//节点的数据和查找的数据比较
return cur;//返回该节点的地址
cur = cur->next;//临时指针往后走一个节点
}
return NULL;//没有找到则返回空
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);//判断位置是否合法
SListNode*newnode=BuySListNode(x);//创建新节点
newnode->next = pos->next;//新节点指针域指向指定位置后一个节点
pos->next = newnode;//指定位置指针域指向新节点
}
void SListEraseAfter(SListNode* pos)
{
assert(pos&&pos->next);//判断位置是否合法
SListNode* cur = pos->next;//定义临时指针指向指定位置的后一个节点
pos->next = pos->next->next;//让指定位置指针域指向要删除节点的后一个接地那
free(cur);//删除指定位置后一个节点
}
void SListDestroy(SListNode* plist)
{
SListNode* cur = plist;//定义第一个临时指针，指向相对前一个节点
SListNode* next = plist;//定义第二个临时指针，指向相对前一个节点
while (next)//遍历，直到第二个节点指向空
{
cur = next;
next = next->next;
free(cur);
}
}
SList.h
#pragma once
#include
#include
#include
typedef int SLTDateType;
typedef struct SLT
{
SLTDateType data;
struct SLT* next;
}SListNode;
//创建一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode* plist);
test.c
#include"SList.h"
void TestSList()
{
SListNode* node = NULL;
SListPushBack(&node, 1);
SListPushBack(&node, 2);
SListPushBack(&node, 3);
SListPushBack(&node, 4);
SListPushBack(&node, 5);
SListPushFront(&node, 0);
SListPopBack(&node);
SListPopFront(&node);
SListNode* pos=SListFind(node, 3);
SListPrint(node);
//SListInsertAfter(pos,100);
//SListPrint(node);
SListEraseAfter(pos);
SListPrint(node);
SListDestroy(node);
}
int main()
{
TestSList();
return 0;
}
输出结果：
写是为了不停地思考，创作是为了更好地思考，种一棵树最好的时间是十年前，其次是现在。单链表就暂时学到这啦，如果对您有所帮助，欢迎一键三连~
