【数据结构】顺序表和链表详解(下)

前言：上期我们从顺序表开始讲到了单链表的概念，分类，和实现，而这期我们来将相较于单链表没那么常用的双向链表。

一、双向链表

前面我们讲过单链表，我们知道他是单向不带头，不循环链表结构，而双向链表就不一样了，双向链表是：带头的双向循环链表。

前面我们将链表的分类，但没有具体展现每一种链表到底是什么样的；是因为怕大家混淆，当时为了方便理解就把单链表的第一个节点当作是头节点；但实际上单链表是每一头节点的。

既然双链表是双向带头的循环链表，那么将上面这几种结构结合起来自然就得到了双链表的结构：

注意：这里的“带头”跟前面我们说的“头结点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头结点。

带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨 的”

二，双向链表的实现

首先要实现双链表我们就要创建一个双链表与单链表的实现一样。
在.h文件中

//需要包含的头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int LTData;
//双向链表的构建
typedef struct ListNode
{LTData data;struct ListNode* next;struct ListNode* prev;
}LTNode;

构建好双链表后，我们可以发现双链表比单链表多了一个prev指针，指向它的前一个节点。这一点与单链表很不一样，仅仅多了一个prev指针就使得了链表变得循环起来。而且在单链表中是不能往前遍历的，但在双链表中就可以。

紧接着我们初始化节点：

//初始化新节点
LTNode* LTNodeInit();

//封装一个开辟一个结点的函数   
LTNode* LTBuyNode(LTData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){//到这说明开辟失败perror("malloc fail!");exit(1);}//到这说明开辟成功 调节新结点的prev和head指针 指向自己 因为时双向链表newnode->prev = newnode;newnode->next = newnode;newnode->data = x;//调整完后返回新结点的地址return newnode;
}//初始化
LTNode* LTNodeInit()
{LTNode* phead = LTBuyNode(-1);//向内存申请一块空间 代表一个头结点 return phead;//返回头结点的地址
}

创建好双链表，初始化节点后我们就可以来实现双链表的增，删，查，改了。

一，增

1，头插

//头插
void LTPushFront(LTNode* phead, LTData x);

//头插
void LTPushFront(LTNode* phead, LTData x)
{assert(phead);//既然要插入结点 就要先创建一个结点LTNode* newnode = LTBuyNode(x);//head newnode head->next(d1) 处理他们三个的指向关系newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

2，尾插

//头结点不发生改变传一级指针
//头结点要发生改变传二级指针
//尾插
void LTPushBack(LTNode* phead,LTData x);

//尾插
void LTPushBack(LTNode* phead, LTData x)
{assert(phead);//既然要尾插那么就要有新的结点 新的结点使用LTBuyNode方法开辟 然后返回新结点的地址LTNode* newnode = LTBuyNode(x);//phead  phead->prev(尾结点) newnode//先修改newnodenewnode->prev = phead->prev;//phead->prev即d3结点 newnode指向d3newnode->next = phead;//尾与头相连//再修改链表内部的结点phead->prev->next = newnode;//相当于d3->newnode d3指向newnodephead->prev = newnode;//头与尾相连
}

3，在指定位置后插入

//在指定位置之后插入结点
void LTInsert(LTNode* pos, LTData x);

//在指定位置之后插入结点
void LTInsert(LTNode* pos, LTData x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

二，删

1，头删

//头删
void LTPopFront(LTNode* phead);

//头删
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* del = phead->next;//phead->next 为头结点//处理 head del del->nexphead->next = del->next;del->next->prev = phead;//释放头结点free(del);del = NULL;
}

2，尾删

//尾删
void LTPopBack(LTNode* phead);   

//尾删
void LTPopBack(LTNode* phead)
{//先判断是否是空链表assert(!LTEmpty(phead));//如果链表为空 返回1 !1（非1） 就为0 就会断言报错LTNode* del = phead->prev;//定义del来保存尾结点//处理head  head-next->prev(del->prev)     head->next(del)//             尾结点的上一个结点                   尾结点del->prev->next = phead;phead->prev = del->prev;//释放free(del);del = NULL;
}

3，删除pos位置的节点

//删除pos位置的结点
void LTErase(LTNode* pos);

//删除pos位置的结点
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

三，查

//查找
LTNode* LTFind(LTNode* phead, LTData x);

//查找
LTNode* LTFind(LTNode* phead, LTData x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//走到这里已经循环完了链表都没找到 说明找不到了返回NULLreturn NULL;
}

四，链表的销毁

与单链表一样，双链表也是我们人为向操作系统申请的空间，为了避免空间浪费再我们不使用链表的时候就将他销毁，还给操作系统。

//链表的销毁
void LTdesTroy(LTNode*phead);

void LTdesTroy(LTNode*phead)
{LTNode*pcur=phead->next;while(pcur!=NULL){LTNode*next=pcur->next;free(pcur);pcur=next;}//跳出循环只剩下哨兵位 释放哨兵位free(phead);phead=NULL;
}

五，测试代码

以上就是双链表的实现，实现完后我们可以用一些测试代码来测试一下，

//链表的打印
//链表的打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}

void test1()
{LTNode* plist= LTNodeInit();//ʼ//β/*LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPushBack(plist,4);*/LTPushFront(plist, 1);LTPushFront(plist, 2);LTPrint(plist);
}int main()
{test1();return 0;
}

六，顺序表与链表的总结

以上就是所有链表和顺序表的内容了，我们最后再来比较一下二者的区别：

以上就是本章的全部内容啦！
最后感谢能够看到这里的读者，如果我的文章能够帮到你那我甚是荣幸，文章有任何问题都欢迎指出！制作不易还望给一个免费的三连，你们的支持就是我最大的动力！