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

前言

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

一.双向循环链表的实现

  由下面的图我们可以看出，双向链表在创建时会建立两个指针，此时链表就不仅可以往后链接，还可以向前链接。

我们来看看他们的区别：

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

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

创建新节点：

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

创建返回链表的头结点.

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

return newnode;
}
1
2
3
4
5
6
7
8

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

打印链表

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

1
2
3
4
5
6
7
8
9
10
11
12

判断链表是否只有头节点

bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
1
2
3
4
5

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

双向链表尾插

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;
}
1
2
3
4
5
6
7
8
9
10
11

双向链表尾删

void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty);
LTNode* tail = phead->prev;
tail->prev->next = phead;
phead->prev = tail->prev;
free(tail);
tail = NULL;
}
1
2
3
4
5
6
7
8
9
10

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

双向链表头插

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;
}
1
2
3
4
5
6
7
8
9
10

在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；
}
1
2
3
4
5
6
7
8
9
10

二.顺序表和链表的区别

总结

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

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

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