51传奇网页游戏_宁波外贸公司排名前五十_免费注册域名网站_seo网站推广收费

一、什么是双向链表？

双向链表是一种链式存储结构，每个节点除了存储数据外，还包含两个指针，分别指向前一个节点（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);        // 删除指定节点