单链表的基本操作

我会带着你远行 2023-10-04 23:56 35阅读 0赞

**目录**

一.链表的基本概念和结构

二.链表的分类

三.单链表的基本操作

1.创建一个节点

2.打印

3.尾插

4.头插

5.尾删

6.头删

7.查找

8.指定位置插入

9.指定位置删除

10.销毁

--------------------

## 一.链表的基本概念和结构 ##

概念：链表是一种**物理存储结构上非连续**、非顺序的存储结构，数据元素的**逻辑顺序**是通过链表中的**指针链接**次序实现的。

结构：链表是有各个节点通过指针连接在一起的，每个节点分为数据域和指针域，每个节点的指针域指向下一个节点的地址，最后一个节点的指针域为空。

逻辑结构如下图所示

![34f52044a79342c3a0299a77f7afeadb.png][]![fa0b09f05cc7484c8b83e7632c659207.png][]

物理结构：逻辑结构看起来是连续的，但是由于链表的节点是在堆上开辟的，地址可能连续，也可能不连续

## 二.链表的分类 ##

1.单向和双向：

![dc6388c6bfac4c81b0d9009d8671c338.png][]

2. 带头和不带头

![dfedec358a534f22962dc2bff22e62b3.png][]

3.循环和不循环

![944b190aa40d4f71aa96478717c963e4.png][]

通过上面三种分类我们可以得知，组合起来链表总共有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.尾插 ###

尾插即将新节点插入到链表的尾部，插入过程：先调用开辟节点的函数开辟一个新节点，如果链表为空，则直接将头指针指向新节点，如果非空，链表的最后一个节点指针域通常为空，所以我们需要一个临时指针找到链表的最后一个节点，然后将最后的节点指针域指向新节点，如图所示

![be210373b18a4e8591485f61bfe429f7.png][]

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.头插 ###

链表的头插即将新节点插入到链表最前面，成为链表的第一个节点，插入过程：先调用开辟节点的函数创建一个新节点，若链表为空，则直接将头结点直接指向新节点，若非空，将新节点的指针域指向第一个节点，然后将链表的头指针指向新节点，如图所示

![a52fc8c984284999be426b56b1051d35.png][]

void SListPushFront(SListNode** pplist, SLTDateType x)
    {
    	SListNode* newnode = BuySListNode(x);//开辟新节点
    	if (*pplist == NULL)
    	{
    		*pplist = newnode;//若链表为空表，则直接将头指针指向新节点
    	}
    	else
    	{
    		newnode->next = *pplist;//新节点的指针域指向链表
    		*pplist = newnode;//头指针指向新向新节点
    	}
    }

### 5.尾删 ###

链表的尾删即删去链表的最后一个节点，删除过程：先判断链表是否为空，为空则不能删除，我们用assert断言函数检查链表是否为空表，若非空，如果只有一个节点，我们只需要删除这个节点然后将头指针置空，如果不止一个节点，我们需要找到最后一个节点的前面的一个几点，然后通过前一个的节点指针域释放最后一个节点，此时前一个节点变成新的最后一个节点，因此我们需要将其指针域置空，如图所示

![47b86070d98e4914a812fff4c288fb1c.png][]

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.头删 ###

链表的头删即删去链表的第一个节点，删除过程：先判断链表是否为空，为空则不能删除直接退出函数，如果只有一个节点，则直接将该节点删除，然后将头指针置空，如果不止一个节点，则需要一个临时指针指向第二个节点，通过头指针将第一个元素删除，此时第二个节点成为新的第一个节点，然后将头指针指向临时指针，即头指针指向新的第一个节点，如图所示

![ae1358e08ad14740a9586eae3294893f.png][]

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找到后面一个节点，然后将新节点的指针域指向后面一个节点，然后指定位置指针域指向新节点，如图所示

![749ffa39520842f7941c7a47487fdc0d.png][]

特别值得注意的是，图中的1和2顺序不能倒过来，如果倒过来，即先让指定位置指针域先指向新指针，就找不到指定位置的后一个节点了

void SListInsertAfter(SListNode* pos, SLTDateType x)
    {
    	assert(pos);//判断位置是否合法
    	SListNode*newnode=BuySListNode(x);//创建新节点
    	newnode->next = pos->next;//新节点指针域指向指定位置后一个节点
    	pos->next = newnode;//指定位置指针域指向新节点
    }

### 9.指定位置删除 ###

链表的指定位置删除一般是删除指定位置之后的节点，删除过程：先判断位置是否合法，然后需要定义一个临时指针找到给定位置的后一个节点，然后将指定位置指针域指向要删除的节点后一个节点，然后再删除指定位置后一个节点，如图所示

![fbef4b59ae4c4930952905547ab83968.png][]

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<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    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;
    }

输出结果：

![030244096e3743e5b27b24b954985d5b.png][]

写是为了不停地思考，创作是为了更好地思考，种一棵树最好的时间是十年前，其次是现在。单链表就暂时学到这啦，如果对您有所帮助，欢迎一键三连~

[34f52044a79342c3a0299a77f7afeadb.png]: https://img-blog.csdnimg.cn/34f52044a79342c3a0299a77f7afeadb.png
[fa0b09f05cc7484c8b83e7632c659207.png]: https://img-blog.csdnimg.cn/fa0b09f05cc7484c8b83e7632c659207.png
[dc6388c6bfac4c81b0d9009d8671c338.png]: https://img-blog.csdnimg.cn/dc6388c6bfac4c81b0d9009d8671c338.png
[dfedec358a534f22962dc2bff22e62b3.png]: https://img-blog.csdnimg.cn/dfedec358a534f22962dc2bff22e62b3.png
[944b190aa40d4f71aa96478717c963e4.png]: https://img-blog.csdnimg.cn/944b190aa40d4f71aa96478717c963e4.png
[be210373b18a4e8591485f61bfe429f7.png]: https://img-blog.csdnimg.cn/be210373b18a4e8591485f61bfe429f7.png
[a52fc8c984284999be426b56b1051d35.png]: https://img-blog.csdnimg.cn/a52fc8c984284999be426b56b1051d35.png
[47b86070d98e4914a812fff4c288fb1c.png]: https://img-blog.csdnimg.cn/47b86070d98e4914a812fff4c288fb1c.png
[ae1358e08ad14740a9586eae3294893f.png]: https://img-blog.csdnimg.cn/ae1358e08ad14740a9586eae3294893f.png
[749ffa39520842f7941c7a47487fdc0d.png]: https://img-blog.csdnimg.cn/749ffa39520842f7941c7a47487fdc0d.png
[fbef4b59ae4c4930952905547ab83968.png]: https://img-blog.csdnimg.cn/fbef4b59ae4c4930952905547ab83968.png
[030244096e3743e5b27b24b954985d5b.png]: https://img-blog.csdnimg.cn/030244096e3743e5b27b24b954985d5b.png