初阶数据结构【双链表及其接口的实现】

---

前言

前面我们介绍了数据结构中的链表，并实现了我们在实际中最常用的两个链表之一——无头单向非循环链表，这期我们继续来用C语言实现第二个常用链表——带头双向循环链表；

---

一、基本结构

带头双向循环链表(简称双向链表)的结构

typedef struct ListNode
{
struct ListNode* next; //指向下一个节点
struct ListNode* prev; //指向上一个节点
LTDataType data;
}ListNode;

二、双链表的接口实现

2.1 双链表基本功能接口

2.1.1 双向链表打印

我们为了验证双向链表的其他接口，我们需要实时打印双向链表，所以我们单独设计一个打印模块：

这里我们唯一要知道的是双向循环链表的空链表形式的prev和next都指向自己自身：

// 双向链表打印
void ListPrint(ListNode* plist) {
assert(plist);
ListNode* cur = plist->next;
if (cur == plist)
printf("空链表");
while (cur != plist)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

2.1.2 申请一个节点

当我们需要对双链表进行增加一个节点，我们就要利用malloc来申请一个节点的空间，为了提高代码的复用性，我们将这部分代码封装成函数：

//申请一个节点
ListNode* BuyListNode(LTDataType x) {
ListNode* newNode = malloc(sizeof(ListNode));
if (newNode == NULL)
{
perror("malloc");
exit(-1);
}
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;

return newNode;
}

2.1.3 创建并返回双向链表的头结点

我们根据前面的申请节点接口可以很容易写出创建双向链表的接口（初始双向链表为空）:

// 创建返回链表的头结点.
void ListCreate(ListNode** pplist) {
*pplist = BuyListNode(0);
(*pplist)->next = *pplist;
(*pplist)->prev = *pplist;
}

2.1.4 双向链表清理（不销毁）

当我们不想要这个双向链表的值，但是接下来还要使用这个双向链表，需要对双向链表执行一个清理的操作：

这里我们简单讲解一下使用的思想，由于我们free掉一个节点我们就无法再通过这个节点的next来寻找下个节点，所以我们这里实现这个操作需要两个节点来实现；

// 双向链表清理但不销毁,保留头结点可以继续使用
void ListClear(ListNode* plist){
assert(plist);
ListNode* cur = plist->next;
while (cur != plist)
{
ListNode* next = cur->next; //记录下一个节点的地址
free(cur);  //释放目标节点
cur = next; //指向下一个节点
}
plist->next = plist;
plist->prev = plist;
}

2.1.5 双向链表销毁

我们先将头节点之后的节点进行释放，最后将头结点释放，第一步我们可以复用双向链表的清理：

// 双向链表销毁,利用二级指针，将plist置为空，防止野指针
void ListDestory(ListNode** plist) {
assert(*plist);

/*ListNode* cur = plist;
while (cur != plist)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}*/
ListClear(*plist);
free(*plist);
*plist = NULL;
}

2.2 双向链表增加节点接口

2.2.1 双向链表头插

双向链表比较于单向链表的头插简单的多，我们简单画图理解：

我们先申请一个节点cur，记录插入后目标节点的后面一个节点curNext，进行头插：

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x) {
assert(plist);

//创建新节点
ListNode* cur = BuyListNode(x);
//找到插入后的下一个节点
ListNode* curNext = plist->next;

//解决头指针与新节点的链接
plist->next = cur;
cur->prev = plist;

//解决下一个节点与新节点的链接
curNext->prev = cur;
cur->next = curNext;
}

2.2.2 双向链表尾插

与上面的头插一样，我们需要先申请一个节点newNode，找到双向链表的尾tail，再将其插入双向链表尾部：

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
//防止plist为空
assert(plist);
ListNode* tail = plist->prev;
ListNode* newNode = BuyListNode(x);//申请一个节点

//链接
tail->next = newNode;
newNode->prev = tail;

newNode->next = plist;
plist->prev = newNode;
}

2.2.3 双向链表在pos的前面进行插入

我们通过上面的头插和尾插已经有了一定的经验，我们想要插入一个节点，我们需要知道插入节点的前后两个节点的地址，我们想要在pos前插入节点，我们要知道插入节点前pos的prev，想到这，我们实现pos前面插入就不难了：

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
assert(pos);
//申请新的节点
ListNode* cur = BuyListNode(x);
ListNode* curPrev = pos->prev;

//解决cur与前面的节点的链接
curPrev->next = cur;
cur->prev = curPrev;

//解决cur与后面的节点的链接
cur->next = pos;
pos->prev = cur;
}

若想实现在pos后插入也是同理的，这里就不多赘述了；

2.2.4 优化头插尾插

到这我相信大家发现了这三种插入其实是一个插入：
头插可以写成：

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x) {
assert(plist);

创建新节点
//ListNode* cur = BuyListNode(x);
找到插入后的下一个节点
//ListNode* curNext = plist->next;

解决头指针与新节点的链接
//plist->next = cur;
//cur->prev = plist;

解决下一个节点与新节点的链接
//curNext->prev = cur;
//cur->next = curNext;

ListInsert(plist->next, x);
}

同理，尾插可以写成：

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
//防止plist为空
assert(plist);

//ListNode* tail = plist->prev;
//
//ListNode* newNode = BuyListNode(x);

链接
//tail->next = newNode;
//newNode->prev = tail;

//newNode->next = plist;
//plist->prev = newNode;
ListInsert(plist, x);
}

2.3 双向链表删除节点接口

2.3.1 双向链表的头删

我们要讲目标节点的上一个节点和下一个节点链接起来即可，我们需要注意的是，删除的节点我们最后要free掉：

// 双向链表头删
void ListPopFront(ListNode* plist) {
assert(plist);
assert(plist != plist->next);//防止对空链表删除，free了头指针

//指向被删节点
ListNode* cur = plist->next;
//被删节点的下个节点
ListNode* curNext = cur->next;

//取消头结点与第一个节点链接
plist->next = curNext;
curNext->prev = plist;

//释放空间
free(cur);
cur = NULL;
}

2.3.2 双向链表的尾删

理解了上面的头删，我们很容易写出尾删：
这里很多人会这样写：

 //双向链表尾删
void ListPopBack(ListNode* plist) {
assert(plist);

//找到尾节点
ListNode* tail = plist->prev;
//改变头指针的prev
plist->prev = tail->prev;

//改变尾指针上一个节点的next
tail->prev->next = plist;

free(tail);
    tail = NULL;//防止野指针，函数内部局部变量，不置空也可以
}

这样写本身没有什么错误，但是不利于代码的可读性，所以我们一般这样来写：

//上面的代码不利于可读性，我们可以这样写
void ListPopBack(ListNode* plist) {
assert(plist);

assert(plist->next != plist);//防止对空链表进行删除

ListNode* tail = plist->prev;
ListNode* tailPrev = tail->prev; //需要删除节点的上一个节点

tailPrev->next = plist; 
plist->prev = tailPrev;

free(tail);
tail = NULL;//防止野指针，函数内部局部变量，不置空也可以
}

2.3.3 双向链表删除pos位置的结点

// 双向链表删除pos位置的结点
void ListErase(ListNode* pos) {
assert(pos);
/*assert(pos != plist);*/

ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;

posPrev->next = posNext;
posNext->prev = posPrev;

free(pos);
pos = NULL;
}

2.3.4 优化头删尾删

与插入一样我们同样可以使用ListErase一个接口来实现这里所有的删除：

双链表的头删：

void ListPopFront(ListNode* plist) {
assert(plist);
assert(plist != plist->next);//防止对空链表删除，free了头指针

指向被删节点
//ListNode* cur = plist->next;
被删节点的下个节点
//ListNode* curNext = cur->next;

取消头结点与第一个节点链接
//plist->next = curNext;
//curNext->prev = plist;

释放空间
//free(cur);
//cur = NULL;

ListErase(plist->next);
}

双链表的尾删：

void ListPopBack(ListNode* plist) {
assert(plist);

assert(plist->next != plist);//防止对空链表进行删除

//ListNode* tail = plist->prev;
//ListNode* tailPrev = tail->prev;

//tailPrev->next = plist;
//plist->prev = tailPrev;

//free(tail);
//tail = NULL;//防止野指针，函数内部局部变量，不置空也可以

ListErase(plist->prev);
}

2.4 双向链表修改节点数据接口

通过节点的地址来将所指节点的数据进行修改：

//双向链表修改数据接口
void ListUpData(ListNode* pos, LTDataType x){
assert(pos);
pos->data = x;
}

pos节点一般由下面的查找节点接口实现。

2.5 双向链表查找节点接口

通过数据查找节点，如果找到节点我们就返回这个节点的地址，反之，返回空：

// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x) {
assert(plist);

ListNode* cur = plist->next;
while(cur != plist)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
//没找到

return NULL;
}

三、顺序表和链表的区别

到目前为止我们已经用C语言实现了顺序表和链表的部分接口，我们也已经知道两者部分的优缺点，我们今天做一个总结：

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

---

要想了解的更详细可以去看看<<深入理解计算机系统>>

四、是否传二级指针的总结

通过我们对顺序表和链表的实现接口的过程中我们有时候需要改变其头指针的值，如对无头单链表进行头插：

这样由于头指针发生了改变，所以我们要传二级指针来修改这个指针的值，这样我们就不难理解为什么要创造出带哨兵位的链表了；

总结

这期我们利用C语言实现了带头双向循环链表的接口，我们充分体会到了链表对于顺序表的优点.我们下期继续，谢谢观看；
26考研一战成硕！

---

原文地址：https://blog.csdn.net/2303_78558007/article/details/144889116

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！