【数据结构】双向链表

怼烎@ 2024-04-27 15:59 10阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> 🚀write in front🚀  
> 📜所属专栏： [初阶数据结构][Link 1]  
> 🛰️博客主页：[睿睿的博客主页][Link 2]  
> 🛰️代码仓库：🎉[VS2022\_C语言仓库][VS2022_C]  
> 🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

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

*  前言
 *  一.双向循环链表的实现
 *   *   *  创建新节点：
         *  创建返回链表的头结点.
         *  打印链表
         *  判断链表是否只有头节点
         *  双向链表尾插
         *  双向链表尾删
         *  双向链表头插
         *  在pos位置后面插入
 *  二.顺序表和链表的区别
 *  总结

## 前言 ##

在前面的博客中，我们学习了单链表的实现与操作。然而单链表在进行找尾等操作时，会导致时间复杂度很低。下面我来介绍一下双向链表的相关知识。

## 一.双向循环链表的实现 ##

由下面的图我们可以看出，双向链表在创建时会建立两个指针，此时链表就不仅可以往后链接，还可以向前链接。  
![在这里插入图片描述][caa8d42ab0f34b1c8a78b9c8861f2c76.png]

我们来看看他们的区别：

*  之前写的单链表是没有头节点的，但是双向循环链表是有头节点的
 *  双向循环链表的头和尾也要建立联系，这样就可以快速找尾

因为之前写过单链表，下面我们就快速的实现双链表了，不细细介绍了。

#### 创建新节点： ####

LTNode* BuyListNode(LTDataType x)
    {
        
    	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    	if (newnode == NULL)
    	{
        
    		perror("malloc::newnode");
    		return NULL;
    	}
    	newnode->next = NULL;
    	newnode->prev = NULL;
    	newnode->data = x;
    	return newnode;
    }

#### 创建返回链表的头结点. ####

LTNode* LTInit()
    {
        
    	LTNode* newnode = BuyListNode(-1);
    	newnode->next = newnode;
    	newnode->prev = newnode;
    
    	return newnode;
    }

该头节点在初始化说要自行成环，方便后面拼接。

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

void LTPrint(LTNode* phead)
    {
        
    	assert(phead);
    	LTNode* cur = phead->next;
    	while (cur!=phead)
    	{
        
    		printf("%d<==>", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }

#### 判断链表是否只有头节点 ####

bool LTEmpty(LTNode* phead)
    {
        
    	assert(phead);
    	return phead->next == phead;
    }

这个判断十分重要，因为只剩头节点的话就不能删除了。

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

void LTPushBack(LTNode* phead, LTDataType x)
    {
        
    	assert(phead);
    	LTNode* newnode = BuyListNode(x);
    
    	LTNode* tail = phead->prev;
    	tail->next = newnode;
    	newnode->next = phead;
    	newnode->prev = tail;
    	phead->prev = newnode;
    }

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

void LTPopBack(LTNode* phead)
    {
        
    	assert(phead);
    	assert(!LTEmpty);
    	LTNode* tail = phead->prev;
    	tail->prev->next = phead;
    	phead->prev = tail->prev;
    	free(tail);
    	tail = NULL;
    }

删除了要记得和头节点重新形成联系。

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

void LTPushFront(LTNode* phead, LTDataType x)
    {
        
    	assert(phead);
    	LTNode* newnode = BuyListNode(x);
    	LTNode* first = phead->next;
    	phead->next = newnode;
    	newnode->next = first;
    	newnode->prev = phead;
    	first->prev = newnode;
    }

#### 在pos位置后面插入 ####

void LTInsert(LTNode* pos, LTDataType x)
    {
        
    	assert(pos);
    	LTNode* newnode = BuyListNode(x);
    	LTNode* cur = pos->next;
    	pos->next = newnode;
    	newnode->prev = pos;
    	newnode->next = cur;
    	cur->prev = newnode；
    }

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

<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>可能需要搬移元素，效率低O(N)</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>

## 总结 ##

这就是今天对双向循环链表的简要介绍，对于链表的学习就先告一段落了，接下来我们将开始学习栈与队列的知识了！

更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 3]  
> [c语言学习][c]  
> [算法][Link 4]  
> [智力题][Link 5]  
> [初阶数据结构][Link 1]  
> 更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/fc7448477dcc4d4eb62837a8df8310f8.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/80651c867ba24a329dc7814e1aae66b3.gif
[caa8d42ab0f34b1c8a78b9c8861f2c76.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/4b6aff993a00401f9b49807aa95416b4.png
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12166402.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/5490df1f89fc497fb55bcd40d1cb1251.gif