数据结构——双向链表
前面我们讲到了线性表的一种——链表，细讲了单链表这一种链表结构，那么链表是只有这一种结构吗？接下来我们一起来看看，链表的分类
链表的分类
链表的结构我们可以从三个方面（方向，是否有头，是否循环）来进行定义：
一、链表的方向，是单向还是双向
单向链表只有一个方向，而双向是有两个方向的，可以从前往后，也可以从后往前。
二、链表是否带头
这里的头指的是什么呢？在前面，我们的单链表提到过单链表的头结点（单链表的第一个结点），那这里的头就是头结点吗？
事实上，并不是这样。
链表带头指的是链表的第一个结点，用来占位置的，并不会存储有效的数据，我们把它叫做“哨兵位”
而在我们前面单链表提到的头结点，虽然它是第一个结点，但是它也存放在有效的数据，并不是用来占位置的。
结合刚刚说的，我们就可以知道，第一个链表是不带头的（没有哨兵位），第二个链表是带头的（第一个结点就是哨兵位，没有存储有效的数据，是用来占位置的）。
三、链表是否循环
循环应该很好理解，一个链表的尾结点指向头结点（尾结点的next指针不为空）
比如，上面这个图中，第一个链表就是不循环的，第二个链表就是循环的。
那么我们知道链表有这三个影响因素，那么链表如果进行分类有多少种呢？
每一个影响因素都有两种情况，所以事实上，也就有2的三次方，也就是8种链表的结构。
我们前面讲到的单链表如果说细一点的话，那就是不带头（无头）单向不循环链表。
链表有这么多结构，我们比较经常使用的依然是单链表和带头双向循环链表。
这两个常用的链表有什么区别呢？
单链表： 结构简单，一般不会单独用来存数据。 实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
带头双向循环链表（双向链表）： 结构最复杂，⼀般用在单独存储数据。 实际中使用的链表数据结构，都是带头双向循环链表。
这一篇文章我们就来进一步了解带头双向循环链表这一个链表结构。
双向链表
结构
双向链表也就是带头双向循环链表，既然是一个双向的链表，那么每一个结点除了存储下一个结点的地址，还需要存储的是上一个节点的地址，这样才可以实现双向。
所以
双向链表的结构：数据 + 指向上一个结点的指针 + 指向下一个结点的指针。
我们用代码表示出来的话就是
struct ListNode
{
int data;
struct ListNode* next;//指向下一个结点
struct ListNode* prev;//指向上一个结点
};如果再进行一定的优化就可以写成：
typedef int LTDataType;//进行重命名，以后使用更加方便
typedef struct ListNode
{
int data;
struct ListNode* next;//指向下一个结点
struct ListNode* prev;//指向上一个结点
}LTNode;使用
初始化
双向链表是有一个哨兵位用来占位置的，所以在初始化的时候，我们首先就需要创建一个哨兵位，给哨兵位的数据一个默认值。
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
else
{
newnode->data = x;
newnode->next = newnode->prev = newnode;
}
return newnode;
}
void LTInit01(LTNode** pphead)
{
//创建一个哨兵位
*pphead = LTBuyNode(-1);
}在这里，我们传递过去的是这个指针变量的地址（传值传参不改变实参，传址传参改变实参），是一个二级指针，如果我们不想传递过去的是二级指针，我们还有一种方法，就是不给初始化的函数传参，在初始化的函数内部进行指针变量的创建并且将这个指针变量初始化，最终返回创建的指针。
代码如下：
LTNode* LTInit02( )
{
//在函数内部新创建一个变量再返回
LTNode* phead = LTBuyNode(-1);
return phead;
}
通过调试我们可以发现，达到了相同的效果。
尾插
我们首先来想一想尾插在传参的时候是传指针变量，还是传指针变量的地址呢？
在前面单链表的插入和删除都是传递的是指针变量的地址，这是因为在进行插入的时候和删除的时候会影响到第一个结点可能会发生改变，而在双向链表中，第一个结点是用来占位置的，并不会发生改变，我们传参的时候就可以直接传指针变量（一级）。
所以看第一个参传一级还是二级，要看pphead指向的结点（第一个结点）会不会发生改变 如果发生改变，那么pphead的改变要影响实参，传二级 如何不发生改变，pphead不会影响实参，传一级
进行尾插操作时，影响到是原来尾结点（phead->prev)的指向，以及第一个结点的指向和新结点的指向，在改变指向的时候，我们先处理插入结点（新结点）的指向，这样就可以避免结点指向错误。
代码如下：
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//链表不为空
LTNode* newnode = (LTNode*)LTBuyNode(x);
newnode->prev = phead->prev;//哨兵位的前一个结点就是尾结点
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}通过调试，我们可以发现成功进行了插入
打印数据
我们也可以通过打印来验证
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
//第一个结点是哨兵位，不存储有效数据，不需要进行打印
while (pcur != phead)
//注意双向链表是循环的，这里不能写成pcur，因为链表不会为空
//写成pcur就会进行死循环
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
头插
这里的头插不是指在哨兵位前面插入，而是在哨兵位后面进行插入一个结点，如果在哨兵位前面，那么依然是尾插的结果。
代码如下：
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
尾删
在进行删除操作时，我们首先需要确定哨兵位是否存在，以及链表是否为空链表（只有一个哨兵位），我们可以写一个函数来判断是否为空链表。
进行尾删时我们可以先保存倒数第二个结点，然后释放掉最后一个结点，再进行指向改变。
//判断是否为空链表（只有哨兵位）
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
//如果哨兵位下一个也是哨兵位，说明只有哨兵位（空链表）
}
void LTEraseBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* prev = phead->prev->prev;//倒数第二个结点
free(phead->prev);
prev->next = phead;
phead->prev = prev;
}
头删
头删删除的也就是哨兵位后面的那一个结点，代码如下：
void LTEraseFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* next = phead->next->next;//哨兵位后面的第二个结点
free(phead->next);
phead->next = next;
next->prev = phead;
}
查找结点
查找结点就需要我们对链表进行遍历，找到我们想要的结点，只有哨兵位也可以进行查找，只不过找不到，直接就返回NULL.
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;//遍历链表，查找结点
while (pcur != phead)//走一次循环
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;//没有找到
}
在pos之后插入结点
结合前面的代码，相信这里是手到擒来了
void LTNPushPosBack(LTNode* phead, LTNode* pos, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
删除指定位置pos的结点
void LTNErasePos(LTNode* phead, LTNode* pos)
{
assert(phead);
pos->prev->next = pos->next;
//pos前一个结点的next指向pos的后面一个
pos->next->prev = pos->prev;
//pos后面一个结点的prev指向pos的前面一个
free(pos);
pos = NULL;
}
销毁链表
链表进行销毁就需要对整个链表进行销毁释放，包括我们的哨兵位。
方法一
传二级指针
void Destory01(LTNode** pphead)
{
assert((pphead) && (*pphead));
LTNode* pcur = (*pphead)->next;
while (pcur != (*pphead))
{
LTNode* next = pcur->next;//保存下一个结点
free(pcur);//释放当前结点
pcur = next;
}
//销毁哨兵位
free(*pphead);
*pphead = NULL;
pcur = NULL;
}
我们可以看到，代码正常运行也没有报错和警告。
方法二
第一个方法使用了二级指针，事实上，我们也可以使用一级指针来实现链表的销毁，这样可以保证我们的接口一致性，所有实现双向链表的操作的函数操作都是使用一级指针来实现，当然这里释放完哨兵位这一块内存空间之后，要在原来的函数中将ps置为空。
void Destory02(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;//保存下一个结点
free(pcur);//释放当前结点
pcur = next;
}
//销毁哨兵位
free(phead);
phead = NULL;
pcur = NULL;
}
总代码
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//struct ListNode
//{
// int data;
// struct ListNode* next;//指向下一个结点
// struct ListNode* prev;//指向上一个结点
//};
typedef int LTDataType;//进行重命名，以后使用更加方便
typedef struct ListNode
{
int data;
struct ListNode* next;//指向下一个结点
struct ListNode* prev;//指向上一个结点
}LTNode;
LTNode* LTBuyNode(LTDataType x);
void LTInit01(LTNode** pphead);
LTNode* LTInit02( );
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTEraseBack(LTNode* phead);
void LTEraseFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTNPushPosBack(LTNode* phead, LTNode* pos, LTDataType x);
void LTNErasePos(LTNode* phead, LTNode* pos);
void Destory01(LTNode** pphead);
void Destory02(LTNode* phead);List.c
#include"List.h"
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
else
{
newnode->data = x;
newnode->next = newnode->prev = newnode;
}
return newnode;
}
void LTInit01(LTNode** pphead)
{
//创建一个哨兵位
*pphead = LTBuyNode(-1);
}
LTNode* LTInit02( )
{
//在函数内部新创建一个变量再返回
LTNode* phead = LTBuyNode(-1);
return phead;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
//第一个结点是哨兵位，不存储有效数据，不需要进行打印
while (pcur != phead)
//注意双向链表是循环的，这里不能写成pcur，因为链表不会为空
//写成pcur就会进行死循环
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//链表不为空
LTNode* newnode = (LTNode*)LTBuyNode(x);
newnode->prev = phead->prev;//哨兵位的前一个结点就是尾结点
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
//判断是否为空链表（只有哨兵位）
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
//如果哨兵位下一个也是哨兵位，说明只有哨兵位（空链表）
}
void LTEraseBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* prev = phead->prev->prev;//倒数第二个结点
free(phead->prev);
prev->next = phead;
phead->prev = prev;
}
void LTEraseFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* next = phead->next->next;//哨兵位后面的第二个结点
free(phead->next);
phead->next = next;
next->prev = phead;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;//遍历链表，查找结点
while (pcur != phead)//走一次循环
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;//没有找到
}
void LTNPushPosBack(LTNode* phead, LTNode* pos, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
void LTNErasePos(LTNode* phead, LTNode* pos)
{
assert(phead);
pos->prev->next = pos->next;
//pos前一个结点的next指向pos的后面一个
pos->next->prev = pos->prev;
//pos后面一个结点的prev指向pos的前面一个
free(pos);
pos = NULL;
}
void Destory01(LTNode** pphead)
{
assert((pphead) && (*pphead));
LTNode* pcur = (*pphead)->next;
while (pcur != (*pphead))
{
LTNode* next = pcur->next;//保存下一个结点
free(pcur);//释放当前结点
pcur = next;
}
//销毁哨兵位
free(*pphead);
*pphead = NULL;
pcur = NULL;
}
void Destory02(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;//保存下一个结点
free(pcur);//释放当前结点
pcur = next;
}
//销毁哨兵位
free(phead);
phead = NULL;
pcur = NULL;
}test.c
#include"List.h"
void Test01()
{
LTNode* ps;
//LTInit01(&ps);
ps = LTInit02();
LTPushBack(ps, 1);
LTPushBack(ps, 2);
LTPushBack(ps, 3);
LTPushBack(ps, 4);
LTPushBack(ps, 5);
LTPrint(ps);
//Destory01(&ps);
Destory02(ps);
ps=NULL;//ps手动置为空
//LTPrint(ps);
//LTPrint(ps);
/*LTNode* find = LTFind(ps, 3);
LTNErasePos(ps, find);
LTPrint(ps);*/
//LTPrint(ps);
//LTPrint(ps);
/*LTNPushPosBack(ps, find, 7);
LTPrint(ps);
LTNPushPosBack(ps, find, 6);
LTPrint(ps);*/
/*LTNode* find = LTFind(ps, 4);
if (find == NULL)
{
printf("没有找到\n");
}
else
printf("找到了\n");*/
/*LTEraseFront(ps);
LTPrint(ps);
LTEraseFront(ps);
LTEraseFront(ps);
LTEraseFront(ps);
LTPrint(ps);*/
/*LTPushFront(ps, 1);
LTPushFront(ps, 2);
LTPushFront(ps, 3);
LTPushFront(ps, 4);
LTPushFront(ps, 5);
LTPrint(ps);
LTEraseBack(ps);
LTEraseBack(ps);
LTEraseBack(ps);
LTEraseBack(ps);
LTPrint(ps);*/
}
int main()
{
Test01();
return 0;
}顺序表和链表的简单分析
结合前面学习的知识，我们知道链表可以降低使用顺序表插入和删除的时间复杂度，可以减少或者避免增容带来的性能消耗，同时也可以避免空间的浪费。
那么学习完链表和顺序表，你觉得哪一个更好呢？
我们一起来深入分析一下：
不同点 | 链表（单链表） | 顺序表 |
|---|---|---|
存储空间上 | 逻辑上连续，但物理上不⼀定连续 | 物理上⼀定连续 |
随机访问 | 需要遍历，时间复杂度O(N) ，不支持O(1) | 支持O（1） |
任意位置插⼊或者删除元素 | 只需修改指针指向 ，降低时间复杂度 | 可能需要移动元素，效率低，O(N) |
插⼊ | 没有容量的概念，按需申请释放，不存在空间浪费 | 动态顺序表，空间不够时需要进行扩容，一般为两倍扩容，可能造成空间浪费 |
应⽤场景 | 任意位置⾼效插⼊和删除 | 元素⾼效存储+频繁访问 |
事实上，顺序表和链表并没有好坏之分，在不同的应用场景下，它们都有着自己的优势，我们可以结合不同应用场景选择合适的线性表来进行处理。
♥♥♥本篇博客内容结束，期待与各位未来的优秀程序员交流，有什么问题请私信♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
腾讯云开发者
