文章目录
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:二级指针和一级指针应该什么时候用,如何选择?
在单链表和双向链表中,二级指针和一级指针的选择在于是否需要修改(删除)头节点/头指针(在双向链表中叫哨兵位)
在实际应用中:
- 一级指针:直接操作变量和简单数据结构
- 二级指针:用于处理复杂的数据结构(多级链表等)、动态内存分配以及需要改变指针本身(值)指向的情况