文章目录
1、双向链表的概念
双向链表（Doubly Linked List）是一种常见的链表数据结构，它与普通的单向链表不同之处在于，每个节点除了存储数据元素外，还存储着指向前一个节点和后一个节点的指针（或引用）。
与单链表的区别：双向链表中可以通过节点本身直接访问其前驱节点和后继节点，而不需要像单向链表那样只能从头节点开始顺序访问。
2、双向链表的接口实现
2.1结构
- 双向链表的一个节点由三部分构成
1）当前节点的数据——date
2）前驱指针——prev
3）后驱指针——next
//定义双向链表中节点的结构
typedef int LDateType;
typedef struct ListNode {
LDateType date;
struct ListNode* prev;
struct ListNode* next;
}LNode;
带头双向链表:
- 双向链表带有哨兵位，插入数据之前必须要初始化哨兵位
- 哨兵节点（头节点）：本身不存储有效数据，它的存在只是为了简化边界条件的处理。
这里我用双向带头循环链表来实现
2.2初始化
申请节点
对申请节点功能进行封装，方便调用。
//申请节点
LNode* LBuyNode(LDateType x) {
LNode* newnode = (LNode*)malloc(sizeof(LNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->date = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
直接调用申请节点函数创建哨兵位
LNode* LInit()
{
//创建一个哨兵位
LNode* phead = LBuyNode(-1);
return phead;
}
2.3插入数据
尾插
当双向链表进行尾插的时候，无需像单链表那样循环找尾节点，双向链表中的尾节点与哨兵位相连，可以直接获取:
ptail = phead->prev
- 思路：在修改指针连接时，优先对newnode的前驱和后驱进行修改，避免影响链表原来的指向，随后对ptail的后驱和phead的前驱进行修改
void LPushBack(LNode* phead, LDateType x)
{
assert(phead);
LNode* newnode = LBuyNode(x);//申请节点
//phead phead->prev(ptail) newnode 修改指针连接
newnode->next = phead;
newnode->prev = phead->prev;
(phead->prev)->next = newnode;
phead->prev = newnode;
}
头插
与尾插相似，修改对应指针连接即可
void LPushFront(LNode* phead, LDateType x)
{
assert(phead);
LNode* newnode = LBuyNode(x);
// phead newnode phead->next 修改这三个节点的连接
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
指定位置之后插入数据
对插入数据的位置前驱后驱节点修改指针连接即可
pos-> newnode-> pos->next
void LInsert(LNode* pos, LDateType x) {
assert(pos);
LNode* newnode = LBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
2.4删除数据
- 思路：修改指针连接，free函数释放被删除节点即可
尾删
void LPopBack(LNode* phead) {
assert(phead);
//若哨兵位节点的next指针或prev指针指向的是自己，则链表为空
assert(phead->next != phead);
LNode* del = phead->prev;
LNode* prev = del->prev;
//实现结果一致，无需分情况讨论，
prev->next = phead;
phead->prev = prev;
free(del);
del = NULL;
}
头删
void LPopFront(LNode* phead) {
assert(phead);
assert(phead->next != phead);
LNode* del = phead->next;
LNode* next = del->next;
//改变指针指向，删除指定节点即可
next->prev = phead;
phead->next = next;
free(del);
del = NULL;
}
指定位置删除
void LErase(LNode* pos) {
assert(pos);
//pos->prev pos pos->next
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
2.5查找
- 功能 ：查找指定节点并返回节点
- 实现思路：创建节点指针pcur指向链表中第一个节点(phead->next),
遍历链表，查找指定节点，如果找到直接返回节点，停止条件为当pcur指向哨兵位，当跳出循环则链表中不存在指定节点，返回NULL
LNode* LFind(LNode* phead, LDateType x) {
assert(phead);
LNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->date == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
2.6打印
- 思路：创建节点指针pcur指向链表中第一个节点(phead->next),
遍历链表，停止条件为当pcur指向哨兵位，当pcur指向哨兵位则遍历完成
void LPrint(LNode* phead) {
assert(phead);
LNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->date);
pcur = pcur->next;
}
printf("\n");
}
2.7销毁
- 思路：通过遍历删除每个有效节点，最后删除哨兵位
void LDestroy(LNode** pphead) {
assert(pphead);
//哨兵位不能为空
assert(*pphead);
LNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
LNode* next = pcur->next;
free(pcur);
pcur = next;
}
//最后链表只剩哨兵位
//销毁哨兵位
free(*pphead);
*pphead = NULL;
}
3、链表和顺序表的区别
4、问题与思考
Q：二级指针和一级指针应该什么时候用，如何选择？
在单链表和双向链表中，二级指针和一级指针的选择在于是否需要修改(删除)头节点/头指针（在双向链表中叫哨兵位）
在实际应用中：
- 一级指针：直接操作变量和简单数据结构
- 二级指针：用于处理复杂的数据结构(多级链表等)、动态内存分配以及需要改变指针本身(值)指向的情况