一、什么是双向链表?
双向链表是一种链式存储结构,每个节点除了存储数据外,还包含两个指针,分别指向前一个节点(prev
)和后一个节点(next
)。这与单向链表不同,双向链表允许我们在链表中向前或向后遍历,非常灵活。
二、程序的作用和意义
通过实现双向链表,我们可以更灵活地管理数据。相比数组,链表在插入和删除时更加高效,特别是当操作发生在链表中间位置时,不需要移动其他元素。双向链表在实际开发中有广泛的应用,比如在缓存、操作系统中的任务管理、文本编辑器等地方,都可以看到双向链表的身影。
三、双向链表结构图解
假设我们有以下的双向链表:
[head] <--> [1] <--> [2] <--> [3] <--> [4] <--> [head]
head
是哨兵节点(不存储实际数据,仅作链表的头和尾)。- 每个节点都可以通过
next
指针访问下一个节点,通过prev
指针访问上一个节点。 - 双向链表具有环形结构,最后一个节点的
next
指针指向head
,第一个节点的prev
指针也指向head
。
四、 双向链表的基本结构
我们先看一下在C语言中如何定义双向链表节点的结构体:
typedef int LTDataType; // 链表中的数据类型
typedef struct ListNode {LTDataType data; // 节点数据struct ListNode* next; // 指向下一个节点struct ListNode* prev; // 指向上一个节点
} LTNode;
每个节点存储一个data
,以及两个指针next
和prev
,用来分别指向下一个和上一个节点。
五、 双向链表的基本操作
接下来我们讨论双向链表的几种常见操作,包括初始化、插入、删除、查找、打印等。我们将逐步介绍这些操作的实现原理和注意事项。
5.1 初始化链表
初始化时,我们通常创建一个“哨兵节点”,这个节点不存储实际的数据,只是为了方便后续操作。哨兵节点的next
指针指向链表的第一个节点,prev
指针指向链表的最后一个节点。以下是链表初始化的代码:
LTNode* LTInit() {LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); // 创建哨兵节点phead->data = -1; // 哨兵节点通常存放无意义的数据phead->next = phead;phead->prev = phead;return phead;
}
5.2 尾插法(在链表末尾插入节点)
尾插法是向链表的末尾添加新节点的一种方式。具体操作如下:
- 新节点的
prev
指向当前链表的最后一个节点。 - 新节点的
next
指向哨兵节点。 - 调整哨兵节点和原最后一个节点的指针,指向新节点。
代码如下:
// 尾插法
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);// 插入新节点到尾部newnode->next = phead; // 新节点next指向哨兵newnode->prev = phead->prev; // 新节点prev指向原最后节点phead->prev->next = newnode; // 原最后节点的next指向新节点phead->prev = newnode; // 哨兵的prev指向新节点
}
5.3 头插法(在链表头部插入节点)
头插法与尾插法类似,只是新节点被插入到哨兵节点之后,第一个有效节点之前。注意指针的调整顺序:
// 头插法
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);// 插入新节点到头部newnode->next = phead->next; // 新节点的next指向原第一节点newnode->prev = phead; // 新节点的prev指向哨兵phead->next->prev = newnode; // 原第一节点的prev指向新节点phead->next = newnode; // 哨兵的next指向新节点
}
5.4 删除链表尾部节点
删除尾部节点需要修改链表末尾节点的前一个节点和哨兵节点的prev
指针,断开它们与被删除节点的连接:
// 尾部删除
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead)); // 确保链表不为空LTNode* del = phead->prev; // 找到最后一个节点del->prev->next = phead; // 修改倒数第二个节点的next指向哨兵phead->prev = del->prev; // 修改哨兵的prev指向倒数第二个节点free(del); // 释放被删除的节点内存
}
5.5 删除链表头部节点
删除头部节点类似尾部删除,只是需要调整的是哨兵节点和第二个节点的指针:
// 头部删除
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead)); // 确保链表不为空LTNode* del = phead->next; // 找到第一个有效节点phead->next = del->next; // 哨兵的next指向第二个节点del->next->prev = phead; // 第二个节点的prev指向哨兵free(del); // 释放被删除的节点内存
}
5.6 查找节点
我们可以通过遍历链表来查找某个特定值的节点:
LTNode* LTFind(LTNode* phead, LTDataType x) {LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur; // 找到节点}pcur = pcur->next;}return NULL; // 没有找到
}
5.7 插入节点(在指定节点后插入)
当我们需要在某个节点pos
之后插入节点时,可以这样做:
void LTInsert(LTNode* pos, LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); // 创建新节点newnode->data = x;newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
5.8 删除指定节点
删除指定节点时,需要将节点前后的节点指针重新连接:
// 删除指定位置的节点
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next; // 修改前后节点的链接pos->next->prev = pos->prev;free(pos); // 释放节点内存
}
5.9 打印链表
void LTPrint(LTNode* phead) {LTNode* pcur = phead->next;while (pcur != phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
5.10打印链表中的数据
// 打印链表中的数据
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next; // 从第一个有效节点开始遍历while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
5.11判断链表是否为空
//c
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}
5.12销毁链表
// 销毁链表
void LTDesTroy(LTNode** pphead)
{assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* next = pcur->next;free(pcur); // 逐个释放节点pcur = next;}free(*pphead); // 释放哨兵节点*pphead = NULL;
}
六、双向链表的实现
在下面的代码中,我们将实现一个基本的双向链表,包含初始化、插入、删除、查找等基本操作。
List.h
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>// 双向链表节点定义
typedef int LTDataType;
typedef struct ListNode
{LTDataType data; // 节点存储的数据struct ListNode* next; // 指向下一个节点的指针struct ListNode* prev; // 指向前一个节点的指针
} LTNode;// 函数声明
LTNode* LTInit(); // 初始化双向链表
void LTDesTroy(LTNode** pphead); // 销毁双向链表
void LTDesTroy2(LTNode* phead); // 销毁链表 (传一级指针)void LTPrint(LTNode* phead); // 打印链表
void LTPushBack(LTNode* phead, LTDataType x); // 末尾插入
void LTPushFront(LTNode* phead, LTDataType x); // 头部插入
void LTPopBack(LTNode* phead); // 末尾删除
void LTPopFront(LTNode* phead); // 头部删除
bool LTEmpty(LTNode* phead); // 判断链表是否为空
LTNode* LTFind(LTNode* phead, LTDataType x); // 查找元素
void LTInsert(LTNode* pos, LTDataType x); // 在指定位置插入
void LTErase(LTNode* pos); // 删除指定节点
七、易错点和细节
- 指针的正确使用:链表中的每个操作都涉及大量的指针操作。插入、删除节点时需要特别注意节点指针的调整顺序,否则可能导致链表断裂或出现悬空指针。
- 内存管理:在删除节点时,一定要记得
free
掉节点占用的内存,避免内存泄漏。 - 哨兵节点的使用:哨兵节点的引入可以简化代码,使得处理空链表或只有一个节点的特殊情况更加方便。但是要注意,哨兵节点本身不存储有效数据。
八、总结
双向链表是链表的一种扩展形式,允许我们双向遍历数据。在C语言中,链表通过指针来实现,操作灵活,但需要小心指针操作和内存管理。通过本文介绍的代码和细节,大家可以掌握双向链表的基本实现方式,同时避免常见的错误。