探索双链表：C语言中的链式结构魔法

目录

引言

一、双链表基础

1.1、什么是双链表？

1.2、双链表节点的结构定义

二、双链表的基本操作

2.1、双链表的初始化

2.2、尾插法

2.3、头插

2.4、判断双链表是否为空

2.5、尾删法

2.6、头删法

2.7、查找

2.8、双链表在指定位置之前插入

2.9、双链表删除指定节点

2.10、双链表的销毁

三、总结

结语

---

引言

在程序设计中，数据结构扮演着至关重要的角色。链表作为一种基础且强大的数据结构，广泛应用于需要动态内存管理和高效插入删除的场景。而双链表作为链表的一种拓展，具有双向遍历的能力，为我们的算法设计提供了更大的灵活性。本篇博客将带你深入了解C语言中的双链表，包括其定义、基本操作以及实际应用，让你在掌握数据结构的同时，提高编程的效率与能力

一、双链表基础

1.1、什么是双链表？

双链表同单链表一样，是一种线性结构的数据结构，与单链表不同的是，双链表的每个节点有两个指针，分别指向下一个节点和上一个节点。这使得双链表既可以向前遍历，也可以向后遍历，极大的节省了时间，但代价就是每个节点所占用的空间变大了。

1.2、双链表节点的结构定义

typedef int DLElemType;
typedef struct DListNode
{DLElemType data;   //节点的数据域struct DListNode* next;   //指向下一个节点struct DListNode* prev;   //指向上一个节点
}DListNode;

二、双链表的基本操作

2.1、双链表的初始化

void DLInit(DListNode** pphead)
{*pphead = (DListNode*)malloc(sizeof(DListNode));if (*pphead == NULL){perror("malloc fail!");exit(1);}(*pphead)->data = 0;(*pphead)->next = (*pphead)->prev = *pphead;
}

这里要注意的是，为了与其他类型的链表区分，双链表的初始化让两个指针都指向自己

2.2、尾插法

void DLPushBack(DListNode* phead , DLElemType x)
{assert(phead);DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}

在单链表中，我们要进行尾差就必须遍历找到最后一个节点，但是在双链表中，我们只需要找到头结点的prev指向就可以了，非常的方便

2.3、头插

在此之前，我们需要编写一个函数来实现新节点的创建，一次来提高效率：

//创建一个新的双链表节点
DListNode* BuyDListNode(DLElemType x)
{DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = NULL;return newnode;
}

接下来就是头插法的实现了

//头插
void DLTPushFront(DListNode* phead, DLElemType x)
{assert(phead);DListNode* newnode = BuyDListNode(x);newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}

2.4、判断双链表是否为空

//判断双链表是否为空
bool DLTEmpty(DListNode* phead)
{assert(phead);return phead->next == phead;
}

2.5、尾删法

void DLTPopBack(DListNode* phead)
{assert(phead && !DLTEmpty(phead));DListNode* pcur = phead->prev;pcur->prev->next = phead;phead->prev = pcur->prev;free(pcur);pcur = NULL;
}

2.6、头删法

void DLTPopFront(DListNode* phead)
{assert(phead && !DLTEmpty(phead));DListNode* pcur = phead->next;phead->next = pcur->next;pcur->next->prev = phead;free(pcur);pcur = NULL;
}

2.7、查找

DListNode* DLTFind(DListNode* phead, DLElemType x)
{assert(phead && !DLTEmpty(phead));DListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

2.8、双链表在指定位置之前插入

void DLTInsert(DListNode* pos, DLElemType x)
{assert(pos);DListNode* newnode = BuyDListNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}

2.9、双链表删除指定节点

void DLTErase(DListNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.10、双链表的销毁

void DLTDestory(DListNode** pphead)
{assert(pphead && *pphead);DListNode* pcur = (*pphead)->next;while (pcur != *pphead){DListNode* tmd = pcur->next;free(pcur);pcur = tmd;}free(*pphead);*pphead = NULL;
}

三、总结

掌握了单链表，那么掌握双链表也是分分钟的事，本篇以有哨兵位，循环的双链表为目的编写的代码。双链表的实际应用广泛，例如播放器的歌曲上一首下一首 ，以及网页的进一步退一步等。双链表非常好掌握，这里就不多赘述了

结语

通过对双链表的系统讲解与实践操作，相信你已经对其核心思想与实现细节有了更深的理解。双链表不仅是数据存储的利器，更是算法设计中不可或缺的基础结构。在今后的学习与开发中，灵活运用双链表，将会让你的代码更加高效、优雅。希望这篇文章能为你打开链式结构世界的大门，助你在编程之路上越走越远！