数据结构与算法之《单链表》详解

红太狼 2023-09-26 16:56 23阅读 0赞

> ## 标题：单链表的思路及代码实现 ##
> 
> ## **作者：@Ggggggtm** ##
> 
> ## 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ##
> 
> ## **文章目录：** ##
> 
> 引入
> 
> 一、链表的概念及结构
> 
> 1.1 链表的概念
> 
> 1.2 链表的结构
> 
> 二、链表的思路及代码实现详解
> 
> 2.1 单链表的实现思路
> 
> 2.2 单链表的思路及代码实现
> 
> 2.2.1 定义结构体
> 
> 2.2.2 打印链表数据 
> 
> 2.2.3 开辟节点
> 
> 2.2.4 头插 
> 
> 2.2.5 尾插
> 
> 2.2.6 头删
> 
> 2.2.7 尾删
> 
> 2.2.8 查找
> 
> 2.2.9 任意位置插入
> 
> 2.2.10 任意位置删除
> 
> 2.2.11 销毁链表
> 
> 三、单链表和顺序表的优缺点总结对比
> 
> --------------------
> 
> ![1acf80faadab498787ca2ce3e259c8c3.png][]

## 引入 ##

> 上篇文章我们讲述了动态的顺序表 （[顺序表文章详解][Link 1]）。  
> 通过上篇文章我们知道，动态的顺序表当空间不足够时需要扩容，扩容是有消耗的，同时可能会造成空间浪费。因此，我们针对顺序表的缺点，我们这里引入链表，我们来看链表的思路及代码的实现。

## 一、链表的概念及结构 ##

### 1.1 链表的概念 ###

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

> 通俗的解释一下链表。链表就是定义一个结构体，在链表中我们通常称结构体为节点，一个节点中包含一个要**存储的数据**，同时会有**下个节点的地址**。我们就是通过这个地址来访问下个节点。当然，最后一个节点存储的地址为空指针。但是它们在物理结构上，不是连续的。而逻辑结构上是连续的。

### 1.2 链表的结构 ###

> 通过上面给出的链表的概念，我们这里给出链表的结构，我们可以结合着先简单理解一下，下面我们会给出各个模块的实现，进而有更深层次的理解。

![cb2865a240fd4d21a59d27e9821dfc92.png][]

> 注意，上图的结构中实际上是**没有箭头**的。这里我们为了能够更加方便的理解，我们给出箭头。实际上，是通过地址访问到下个节点。

## 二、链表的思路及代码实现详解 ##

> 链表有很多种类，例如有**单向链表、双向链表、带有哨兵位的链表**等等。我们这里先给大家详解一下链表入门的单向链表，也称为单链表。

### 2.1 单链表的实现思路 ###

> 我们学习完顺序表后，我们会很容易学习链表。两者的实现思路大同小异。具体到每个模块细节的实现还是有所差别的。我们先来看单链表整体思路分为多种不同的模块有哪几个：
> 
> 1.  定义一个结构体，该结构体包含一个可以存放数据的变量和一个能够指向下一个节点的指针。
> 2.  打印链表数据。
> 3.  开辟节点
> 4.  头插。
> 5.  尾插。
> 6.  头删。
> 7.  尾删。
> 8.  查找
> 9.  任意位置插入。
> 10. 任意位置删除。
> 11. 销毁链表
> 
> 以上就是整个单链表的不同模块，那我们接下来看一下不同模块思路及代码实现的细节吧。

### 2.2 单链表的思路及代码实现 ###

#### 2.2.1 定义结构体 ####

> 上面我们提到，定义结构体时该结构体包含一个可以存放数据的变量和一个能够指向下一个节点的指针，那么代码的实现就很简单了。

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

> 通过上面我们看到：在定义结构体时，我们可以用**typedef**进行**数据类型简化**，同时方便我们后期更改存储类型的时候直接更改typedef处即可。同时我们也用**typedef**进行**结构体类型简化**，方便我们以后编辑代码。

#### 2.2.2 打印链表数据 ####

> 打印链表数据时，我们从第一个节点依次往后访问打印即可。直到当前节点存储的下一个节点的地址为空时结束。我们来看代码。

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

#### 2.2.3 开辟节点 ####

> 在我们插入数据之前，不管是头插还是尾插，还是任意插入，我们都需要新开辟一个节点。然后把要插入的数据存储到新节点当中，然后进行连接即可。所以这里我们把开辟节点单独分为一个模块来解释。我们来看一下代码的是实现。

SLTNode* BuySlistNode(SLTDataType x)
    {
    	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    	if (newnode == NULL)
    	{
    		printf("malloc failed\n");
    		exit(-1);
    	}
    	newnode->data = x;
    	newnode->next = NULL;
    	return newnode;
    }

#### 2.2.4 头插 ####

> 头插的实现相对较为简单。开辟一个新的节点，然后新的节点中的next指向第一个节点即可，也就是存储了第一个节点的地址。当头插结束之后，要更新头节点所指向的位置。

void SListPushFront(SLTNode** pphead, SLTDataType x)
    {
    	SLTNode* newnode = BuySlistNode(x);
    	newnode->next = *pphead;
    	*pphead = newnode;
    }

> 那上面的代码当**头插时是空链表可以吗**？一样可以的。当是空链表时，\*pphead也为空（NULL），分析后依然可以的。

#### 2.2.5 尾插 ####

> 尾插同样需要开辟节点。我们需要找到链表的最后一个节点，然后最后一个节点的next指向新节点即可。但是尾插时，当链表为空的时候需要另外考虑。我们结合着代码一起理解一下。

void SListPushBack(SLTNode** pphead, SLTDataType x)
    {
    	SLTNode* newnode=BuySlistNode(x);
    	if (*pphead == NULL)
    	{
    		*pphead = newnode;
    	}
    	else
    	{
    		SLTNode* tail = *pphead;
    		while (tail->next != NULL)
    		{
    			tail = tail->next;
    		}
    		tail->next = newnode;
    	}
    }

#### 2.2.6 头删 ####

> 头删相对简单。我们只要保存了第二个节点，然后删除第一个节点，改变头节点的位置即可。但是我们删除节点时应该确保链表不为空。

void SListPopFront(SLTNode** pphead)
    {
    	assert(*pphead != NULL);
    	SLTNode* cur = (*pphead)->next;
    	free(*pphead);
    	*pphead = cur;
    }

#### 2.2.7 尾删 ####

> 尾删的思路相对较为麻烦，因为我们不仅要找到尾节点，同时还需要找到尾节点的前一个节点，因为我们需要把尾节点的前一个节点的next指向空（NULL）。同样因此尾删有一种特殊的情况。当链表只有一个节点时，此节点就是尾节点，这种情况不需要找前一个结点，直接删除此节点即可。我们结合代码一起理解，我这里提供了两种思路。

void SListPopBack(SLTNode** pphead)
    {
    	assert(*pphead != NULL);
    	if ((*pphead)->next == NULL)
    	{
    		free(*pphead);
    		*pphead = NULL;
    	}
    	else
    	{
    		//SLTNode* tail = *pphead;
    		//while (tail->next->next != NULL)
    		//{
    		//	tail = tail->next;
    		//}
    		//free(tail->next);
    		//tail->next = NULL;
    		SLTNode* prev = NULL;
    		SLTNode* tail = *pphead;
    		while (tail->next != NULL)
    		{
    			prev = tail;
    			tail = tail->next;
    		}
    		free(tail);
    		tail = NULL;
    		prev->next = NULL;
    	}
    }

#### 2.2.8 查找 ####

> 当我们任意插入或者任意删除时，当我们不知道某个元素的位置的时候我们可以先通过查找再进行任意插入或任意删除的操作。这也是我们把查找单独列为一个板块的原因。 当我们找到该节点时，我们就返回该节点的地址，找不到返回空。

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
    {
    	SLTNode* cur = phead;
    	while (cur) 
    	{
    		if (cur->data == x)
    		{
    			return cur;
    		}
    		else
    		{
    			cur = cur->next;
    		}
    	}
    	return NULL;
    }

#### 2.2.9 任意位置插入 ####

> 我们这里的任意位置插入是：在**某个节点前面**插入一个节点。我们先查找一个位置，再进行插入。当然插入需要开辟新节点。我们插入时，我们需要找到pos位置的前一个节点进行连接插入即可。当然，当链表只有一个节点或者没有节点时，我们直接头插就行。我们看代码。

SLTNode* pos=SListFind(phead,x);
    if (pos)
    {
    	SListInsert(&plist, pos, 0);
    }
    void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    {
    	SLTNode* newnode = BuySlistNode(x);
    	if (*pphead == pos)
    	{
    		newnode->next = *pphead;
    		*pphead = newnode;
    	}
    	else
    	{
    		SLTNode* PosPrev = *pphead;
    		while (PosPrev->next != pos)
    		{
    			PosPrev = PosPrev->next;
    		}
    		PosPrev->next = newnode;
    		newnode->next = pos;
    	}
    }

#### 2.2.10 任意位置删除 ####

> 删除时，我们首先要判断的时链表是否为空。任意删除我们需要找到pos位置的前一个节点，把pos的前一个结点连接到pos的后一个节点 ，删除pos位置的节点即可。当链表只有一个节点时，我们直接头删就行。

SLTNode* pos=SListFind(phead,x);
    if (pos)
    {
    	SListInsert(&plist, pos);
    }
    void SListErase(SLTNode** pphead, SLTNode* pos)
    {
    	assert(*pphead != NULL);
    	if (*pphead==pos)
    	{
    		SListPopFront(pphead);
    	}
    	else
    	{
    		SLTNode* prev = *pphead;
    		while (prev->next != pos)
    		{
    			prev = prev->next;
    		}
    		prev->next = pos->next;
    		free(pos);
    		pos = NULL;
    	}
    }

#### 2.2.11 销毁链表 ####

> 因为链表是我们动态开辟出来的，所以我们要释放掉，避免空间泄露。销毁链表时，我们**不只是释放头节点的空间**，每个节点的空间都要释放。

void SListDestory(SLTNode** pphead)
    {
    	SLTNode* cur = *pphead;
    	while (cur)
    	{
    		SLTNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	*pphead = NULL;
    }

> 以上解释我们的整个单链表的不同模块细节实现，那么单链表和动态顺序表有什么区别呢？各自的优缺点是什么呢？接下来我给大家再总结对比一下。

## 三、单链表和顺序表的优缺点总结对比 ##

> <table style="width:650px;">  单链表的优缺点对比  
>  <thead> 
>   <tr> 
>    <th>单链表优点</th> 
>    <th>单链表缺点</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td> <p>按需申请空间，不需要了释放空间，更加合理的利用空间。</p> </td> 
>    <td>每插一个数据，都需要连接后面的一个节点。</td> 
>   </tr> 
>   <tr> 
>    <td>头部或者中间插入数据时不需要挪动数据，插入时效率较高。</td> 
>    <td>不支持随机访问。</td> 
>   </tr> 
>   <tr> 
>    <td>不存在空间浪费。</td> 
>    <td></td> 
>   </tr> 
>  </tbody> 
> </table>

> <table style="width:650px;">  顺序表的优缺点对比  
>  <thead> 
>   <tr> 
>    <th>顺序表优点</th> 
>    <th>顺序表缺点</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td> <p>支持随机访问。在有些算法中需应用随机访问。</p> </td> 
>    <td>空间不够时需要扩容，扩容是有消耗的。</td> 
>   </tr> 
>   <tr> 
>    <td></td> 
>    <td>头部或者中间插入或者删除时需要挪动数据，挪动数据也是有消耗的。</td> 
>   </tr> 
>   <tr> 
>    <td></td> 
>    <td>一次扩容2倍，可能存在空间浪费。</td> 
>   </tr> 
>  </tbody> 
> </table>

> 通过对比发现，单链表和顺序表都有各自的优缺点，都**不可被替代的**。当然，单链表和顺序表都是我们需要重点掌握的。
> 
> 单链表的学习就到这里，希望以上内容对你有所帮助，感谢阅读ovo！

[1acf80faadab498787ca2ce3e259c8c3.png]: https://img-blog.csdnimg.cn/1acf80faadab498787ca2ce3e259c8c3.png
[Link 1]: http://t.csdn.cn/QG1BE
[cb2865a240fd4d21a59d27e9821dfc92.png]: https://img-blog.csdnimg.cn/cb2865a240fd4d21a59d27e9821dfc92.png