双向链表（Doubly Linked List）是链表的一种，它与单向链表的不同之处在于，每个节点不仅有一个指向下一个节点的指针（next），还包含一个指向前一个节点的指针（prev）。这种结构允许我们在链表中向前和向后进行遍历，增加了灵活性。
双向链表的概念
- 节点 (Node)：双向链表的基本单元，包含数据域和两个指针，分别指向前一个节点和后一个节点。
- 头节点 (Head)：指向链表的第一个节点，
head->prev为NULL。 - 尾节点 (Tail)：指向链表的最后一个节点，
tail->next为NULL。 - 前向指针 (Prev)：指向前一个节点的指针，头节点的
prev为NULL。 - 后向指针 (Next)：指向下一个节点的指针，尾节点的
next为NULL。
双向链表提供了比单向链表更多的操作灵活性，但也需要更多的内存，因为每个节点除了数据和 next 指针外，还需要存储一个 prev 指针。
双向链表的基本操作
- 创建链表：初始化一个空链表。
- 插入节点：在链表头部或尾部插入节点，或者在指定位置插入。
- 删除节点：删除指定位置的节点。
- 遍历链表：可以从头节点或尾节点进行遍历。
- 释放链表：释放链表中动态分配的所有节点内存。
双向链表的结构定义
#include <stdio.h>
#include <stdlib.h>
// 定义双向链表节点结构
struct Node {
int data; // 数据域
struct Node* prev; // 指向前一个节点的指针
struct Node* next; // 指向后一个节点的指针
};基本操作实现
- 创建新节点
// 创建新节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // 分配内存
if (newNode == NULL)
{
printf("申请内存失败！");
exit(-1);
}
newNode->data = data; // 设置节点数据
newNode->prev = NULL; // 初始化前一个节点指针为 NULL
newNode->next = NULL; // 初始化下一个节点指针为 NULL
return newNode;
}- 插入节点到链表头部
// 插入节点到链表头部
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data); // 创建新节点
if (*head == NULL) { // 如果链表为空
*head = newNode; // 新节点就是头节点
return;
}
(*head)->prev = newNode; // 头节点的前指针指向新节点
newNode->next = *head; // 新节点的后指针指向原来的头节点
*head = newNode; // 更新头节点为新节点
}- 在链表尾部插入节点
// 插入节点到链表尾部
void insertAtTail(struct Node** head, int data) {
struct Node* newNode = createNode(data); // 创建新节点
if (*head == NULL) { // 如果链表为空
*head = newNode; // 新节点就是头节点
return;
}
struct Node* temp = *head; // 临时指针遍历链表
while (temp->next != NULL) {
temp = temp->next; // 移动到最后一个节点
}
temp->next = newNode; // 最后一个节点的后指针指向新节点
newNode->prev = temp; // 新节点的前指针指向最后一个节点
}- 删除节点
// 删除链表中值为 data 的节点
void deleteNode(struct Node** head, int data) {
if (*head == NULL)
{
printf("节点为空，无法删除节点!");
return;
}
struct Node* temp = *head;
// 找到要删除的节点
while (temp != NULL && temp->data != data) {
temp = temp->next;
}
// 如果未找到
if (temp == NULL) return;
// 如果要删除的是头节点
if (*head == temp) {
*head = temp->next;
}
// 如果存在下一个节点，更新它的 prev 指针
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
// 如果存在前一个节点，更新它的 next 指针
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
free(temp); // 释放节点内存
}- 从头到尾遍历链表
// 从头到尾遍历链表并打印数据
void printListForward(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}- 从尾到头遍历链表
// 从尾到头遍历链表并打印数据
void printListBackward(struct Node* head) {
struct Node* temp = head;
if (temp == NULL) return; // 空链表不需要遍历
// 移动到尾节点
while (temp->next != NULL) {
temp = temp->next;
}
// 从尾到头遍历
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->prev;
}
printf("NULL\n");
}- 释放链表
// 释放链表的所有节点
void freeList(struct Node** head) {
struct Node* current = *head;
struct Node* next;
while (current != NULL) {
next = current->next; // 保存下一个节点
free(current); // 释放当前节点
current = next; // 移动到下一个节点
}
*head = NULL; // 头指针置为 NULL，表示链表已空
}使用示例
int main() {
struct Node* head = NULL; // 初始化空链表
// 插入数据
insertAtHead(&head, 3);
insertAtHead(&head, 2);
insertAtHead(&head, 1);
insertAtTail(&head, 4);
insertAtTail(&head, 5);
// 正向遍历链表
printf("正向遍历链表: ");
printListForward(head);
// 反向遍历链表
printf("反向遍历链表: ");
printListBackward(head);
// 删除节点
deleteNode(&head, 3);
printf("删除节点3后的正向链表: ");
printListForward(head);
// 释放链表
freeList(&head);
return 0;
}运行结果
正向遍历链表: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
反向遍历链表: 5 -> 4 -> 3 -> 2 -> 1 -> NULL
删除节点3后的正向链表: 1 -> 2 -> 4 -> 5 -> NULL总结
- 双向链表 相较于单向链表增加了指向前一个节点的指针，因此我们可以从任意节点向前或向后遍历链表。
- 它的优点在于提供了更方便的双向遍历和删除节点操作（不需要寻找前一个节点），但缺点是需要额外的存储空间来存储
prev指针，并且插入、删除时需要同时维护prev和next指针。