【数据结构】单链表和双向循环链表

客官°小女子只卖身不卖艺 2024-04-01 14:27 43阅读 0赞

#### 文章目录 ####

*   *  单链表
     *   *  链表的概念及结构
         *  链表的分类
         *  链表的实现
         *   *  动态申请一个节点
             *  创建链表
             *  单链表打印
             *  单链表尾插
             *  单链表尾删
             *  单链表头插
             *  单链表头删
             *  单链表的查找
             *  单链表在pos位置之后插入x
             *  单链表删除pos位置之后的值
     *  双向循环链表
     *   *   *  初始化
             *  申请一个新的节点
             *  双向链表的尾插
             *  双向链表的尾删
             *  双向链表的头插
             *  双向链表的头删
         *  顺序表和链表的区别

### 单链表 ###

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

> 概念：链表是一种**物理存储结构上连续**、非顺序的存储结构，数据元素的**逻辑顺序** 是通过链表中的**指针链接**次序实现的。
> 
> ![image-20221103165853401][]
> 
> **注意**：
> 
> 1.  从上图可以看出，链式结构在逻辑上连续的，但是在物理上不一定连续
> 2.  现实中的节点一般是从堆上申请出来的
> 3.  从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续的也可能是不连续

#### 链表的分类 ####

> 实际中链表的结构非常多样，一下情况组合起来就有8中情况：
> 
> 1.  **单向或者双向**
> 
> ![image-20221103170440333][]
> 
> ![image-20221103170453122][]
> 
> 1.  **带头或者不带头**
> 
> ![image-20221103170530572][]
> 
> 1.  **循环或者非循环**
> 
> ![image-20221103170608023][]
> 
> **虽然有这么多的链表的结构，但是我们实际中最常用的还是两种结构**：
> 
> ![image-20221103170822916][]
> 
> 1.  无头单向非循环链表：**结构简单**，一般不会用来单独存放数据。实际中更多是作为**其他数据结构的子结构**，如哈希桶，图的邻接表等等。另外这种结构在**笔试面试**中出现很多
> 2.  带头双向循环链表：**结构最复杂**，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构带来很多优势，实现反而简单了。

#### 链表的实现 ####

##### 动态申请一个节点 #####

>     SListNode* BuySListNode(SLTDataType x)
>     {
>          
>     	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
>     	if (newnode == NULL)
>     	{
>          
>     		perror("malloc fail");
>     		exit(-1);
>     	}
>     	newnode->data = x;
>     	newnode->next = NULL;
>     	return newnode;
>     }

##### 创建链表 #####

>     SListNode* CreateSListNode(int n)
>     {
>          
>     	SListNode* phead = NULL, * ptail = NULL;
>     	for (int i = 0; i < n; i++)
>     	{
>          
>     		SListNode* newnode = BuySListNode(i);
>     		if (phead == NULL)
>     		{
>          
>     			ptail = phead = newnode;
>     		}
>     		else
>     		{
>          
>     			ptail->next = newnode;
>     			ptail = newnode;
>     		}
>     	}
>     	return phead;
>     }

##### 单链表打印 #####

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

##### 单链表尾插 #####

>     //尾插要想改变原来的，就要传地址
>     void SListPushBack(SListNode** pplist, SLTDataType x)
>     {
>          
>     	SListNode* newnode = BuySListNode(x);
>     	if (*pplist == NULL)
>     	{
>          
>     		*pplist = newnode;
>     	}
>     	else
>     	{
>          
>     		SListNode* cur = *pplist;
>     		while (cur->next != NULL)
>     		{
>          
>     			cur = cur->next;
>     		}
>     		cur->next = newnode;
>     	}
>     }

##### 单链表尾删 #####

>     void SListPopBack(SListNode** pplist)
>     {
>          
>     	assert(*pplist);
>     	if ((*pplist)->next == NULL)
>     	{
>          
>     		free(*pplist);
>     		*pplist = NULL;
>     	}
>     	else
>     	{
>          
>     		SListNode* ptail = *pplist;
>     		while (ptail->next->next != NULL)
>     		{
>          
>     			ptail = ptail->next;
>     		}
>     		free(ptail->next);
>     		ptail->next = NULL;
>     	}
>     }

##### 单链表头插 #####

>     void SListPushFront(SListNode** pplist, SLTDataType x)
>     {
>          
>     	SListNode* newnode = BuySListNode(x);
>     	newnode->next = *pplist;
>     	*pplist = newnode;
>     }

##### 单链表头删 #####

>     void SListPopFront(SListNode** pplist)
>     {
>          
>     	assert(*pplist);
>     	SListNode* next = (*pplist)->next;
>     	free(*pplist);
>     	*pplist = next;
>     }

> **注意**：在C语言的单链表，关于改变链表的数字的函数传递方式，传的都是地址。如果不传地址的话就不能改变链表的数值。
> 
> 就如这个例子一样：
> 
>     void swap(int* a, int* b)
>     {
>          
>     	int x = *a;
>     	*a = *b;
>     	*b = x;
>     }
>     void swap1(int a, int b)
>     {
>          
>     	int x = a;
>     	a = b;
>     	b = x;
>     }
>     int main()
>     {
>          
>     	int a = 10;
>     	int b = 20;
>     	swap1(a, b);
>     	printf("a=%d b=%d\n", a, b);
>     	swap(&a, &b);
>     	printf("a=%d b=%d\n", a, b);
>     }
> 
> 运行结果：
> 
> ![image-20221103211601772][]
> 
> 对于第二种方法，传递的是地址，这里直接把地址里面的数字改了

##### 单链表的查找 #####

>     SListNode* SListFind(SListNode* plist, SLTDataType x)
>     {
>          
>     	SListNode* cur = plist;
>     	while (cur != NULL)
>     	{
>          
>     		if (cur->data == x)
>     		{
>          
>     			printf("找到了\n");
>     		}
>     		cur = cur->next;
>     	}
>     	printf("找不到\n");
>     }

##### 单链表在pos位置之后插入x #####

>     void SListInsertAfter(SListNode** pplist, SListNode* pos, SLTDataType x)
>     {
>          
>     	assert(pos);
>     	if (*pplist == pos)
>     	{
>          
>     		SlistPushFront(pplist, x);
>     	}
>     	else
>     	{
>          
>     		SListNode* prve = *pplist;
>     		while (prve->next != pos)
>     		{
>          
>     			prve = prve->next;
>     		}
>     		SListNode* newnode = BuySListNode(x);
>     		prve->next = newnode;
>     		newnode->next = pos;
>     	}
>     }

##### 单链表删除pos位置之后的值 #####

>     void SListEraseAfter(SListNode* pos)
>     {
>          
>     	assert(pos);
>     	if (pos->next == NULL)
>     	{
>          
>     		return;
>     	}
>     	else
>     	{
>          
>     		SListNode* newNode = pos->next;
>     		pos->next = newNode->next;
>     		free(newNode);
>     	}
>     }

### 双向循环链表 ###

> ![image-20221111135604992][]

##### 初始化 #####

>     typedef struct ListNode {
>          
>     	struct ListNode* prve;
>     	struct ListNode* next;
>     	LTDataType data;
>     }LTNode;
>     
>     
>     LTNode* LTInit() {
>          
>     	LTNode* phead = BuyListNode(-1);
>     	phead->next = phead;
>     	phead->prve = phead;
>     	return phead;
>     }

##### 申请一个新的节点 #####

>     LTNOde* BuyListNode(LTDatatype x) {
>          
>     	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
>     	if (node == NULL) {
>          
>     		perror("malloc fail");
>     		exit(-1);
>     	}
>     	node->data = x;
>     	node->next = NULL;
>     	node->prve = NULL;
>     	return node;
>     }

##### 双向链表的尾插 #####

> 这个最主要的一部分，就是找到双向链表的尾部。
> 
>     void LTPushBack(LTNode* phead, LTDataType x) {
>          
>     	assert(phead);
>     	LTNode* newnode = BuyListNode(x);
>     	LTNode* tail = phead->prve;//tail 现在就是尾指针
>     	tail->next = newnode;
>     	newnode->prve = tail;
>     	newnode->next = phead;
>     	phead->prve = newnode; 
>     }
> 
> ![image-20221111153801669][]

##### 双向链表的尾删 #####

>     void LTPopBack(LTNode* phead) {
>          
>     	assert(phead);
>     	assert(phead->next = phead);
>     	LTNode* tail = phead->prve;
>     	LTNode* tailPrve = tail->prve;
>     	free(tail);
>     	tailPrve->next = phead;
>     	phead->prve = tailPrve;
>     }
> 
> 思路：找到最后一个节点，然后再通过最后一个节点，找到最后一个的前一个节点。连接起来就可以了。

##### 双向链表的头插 #####

>     void LTPushFront(LTNode* phead, LTDataType x) {
>          
>     	LTNode* newnode = BuyListNode(x);
>     	assert(phead);
>     	newnode->next = phead->next;
>     	phead->next->prve = newnode;
>     	phead->next = newnode;
>     	newnode->prve = phead;
>     }
> 
> ![image-20221111154451215][]

##### 双向链表的头删 #####

> 思路：先找到第一个然后再找到第二个节点，接着释放掉第一个节点。
> 
>     void LTPopFront(LTNode* phead) {
>          
>     	assert(phead);
>     	assert(phead->next != phead);
>     	LTNode* first = phead->next;
>     	LTNode* second = first->next;
>     	free(first);
>     	phead->next = second;
>     	second->prve = phead;
>     }

#### 顺序表和链表的区别 ####

> <table> 
>  <thead> 
>   <tr> 
>    <th>不同点</th> 
>    <th>顺序表</th> 
>    <th>链表</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>存储空间上</td> 
>    <td>物理上一定连续</td> 
>    <td>逻辑上连续，但物理上不一定连续</td> 
>   </tr> 
>   <tr> 
>    <td>随机访问</td> 
>    <td>支持O(1)</td> 
>    <td>不支持O(N)</td> 
>   </tr> 
>   <tr> 
>    <td>任意位置插入或者删除元素</td> 
>    <td>可能需要搬移元素，效率低</td> 
>    <td>只需要修改指针指向</td> 
>   </tr> 
>   <tr> 
>    <td>插入</td> 
>    <td>动态顺序表，空间不够的时候，需要扩容</td> 
>    <td>没有容量的概念</td> 
>   </tr> 
>   <tr> 
>    <td>应用场景</td> 
>    <td>元素高效存储+频繁访问</td> 
>    <td>任意位置插入和删除频繁</td> 
>   </tr> 
>   <tr> 
>    <td>缓存利用率</td> 
>    <td>高</td> 
>    <td>低</td> 
>   </tr> 
>  </tbody> 
> </table>

[image-20221103165853401]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f203d19c4b894b699120fd1f2b14eea7.png
[image-20221103170440333]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/da8be7d1285b4d1db8900d369fdf37fa.png
[image-20221103170453122]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4f8a576795404e2289f530584ba883b6.png
[image-20221103170530572]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b6d3f35aeab0410383e29aab70196b2a.png
[image-20221103170608023]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a74d856409c341bbb27614ad7f813673.png
[image-20221103170822916]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c4a7da8232fc464e8d856cc1fcd91b42.png
[image-20221103211601772]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/81a79b26a4d54f3ea3e34dd28d3e5705.png
[image-20221111135604992]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ff66b7b44da144bea1513b5c7d6a59e2.png
[image-20221111153801669]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f65ae71842d74d559e5d273ef154f252.png
[image-20221111154451215]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/02ba280f7e0547a28049c0f62edbb1da.png