数据结构:双向链表

embedded/2024/10/19 23:33:51/

一、什么是双向链表

双向链表是一种链式存储结构,每个节点除了存储数据外,还包含两个指针,分别指向前一个节点(prev)和后一个节点(next)。这与单向链表不同,双向链表允许我们在链表中向前或向后遍历,非常灵活。

二、程序的作用和意义

通过实现双向链表,我们可以更灵活地管理数据。相比数组,链表在插入和删除时更加高效,特别是当操作发生在链表中间位置时,不需要移动其他元素。双向链表在实际开发中有广泛的应用,比如在缓存、操作系统中的任务管理、文本编辑器等地方,都可以看到双向链表的身影。

三、双向链表结构图解

假设我们有以下的双向链表

[head] <--> [1] <--> [2] <--> [3] <--> [4] <--> [head]
  1. head 是哨兵节点(不存储实际数据,仅作链表的头和尾)。
  2. 每个节点都可以通过 next 指针访问下一个节点,通过 prev 指针访问上一个节点。
  3. 双向链表具有环形结构,最后一个节点的 next 指针指向 head,第一个节点的 prev 指针也指向 head

四、 双向链表的基本结构

我们先看一下在C语言中如何定义双向链表节点的结构体:

typedef int LTDataType; // 链表中的数据类型
typedef struct ListNode {LTDataType data; // 节点数据struct ListNode* next; // 指向下一个节点struct ListNode* prev; // 指向上一个节点
} LTNode;

每个节点存储一个data,以及两个指针nextprev,用来分别指向下一个和上一个节点。

五、 双向链表的基本操作

接下来我们讨论双向链表的几种常见操作,包括初始化、插入、删除、查找、打印等。我们将逐步介绍这些操作的实现原理和注意事项。

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);        // 删除指定节点

七、易错点和细节

  1. 指针的正确使用链表中的每个操作都涉及大量的指针操作。插入、删除节点时需要特别注意节点指针的调整顺序,否则可能导致链表断裂或出现悬空指针。
  2. 内存管理:在删除节点时,一定要记得free掉节点占用的内存,避免内存泄漏。
  3. 哨兵节点的使用:哨兵节点的引入可以简化代码,使得处理空链表或只有一个节点的特殊情况更加方便。但是要注意,哨兵节点本身不存储有效数据。

八、总结

双向链表链表的一种扩展形式,允许我们双向遍历数据。在C语言中,链表通过指针来实现,操作灵活,但需要小心指针操作和内存管理。通过本文介绍的代码和细节,大家可以掌握双向链表的基本实现方式,同时避免常见的错误。


http://www.ppmy.cn/embedded/128849.html

相关文章

2024年第四届“网鼎杯”网络安全大赛-赛前模拟训练

文章目录 网络安全&#xff08;WEB&#xff09;签到题WEB01WEB02 二进制漏洞安全&#xff08;PWN&#xff09;PWN01潜在的安全漏洞分析攻击步骤exp 逆向工程&#xff08;REVERSE&#xff09;REVERSE01代码分析重构密码 密码学&#xff08;CRYPTO&#xff09;CRYPTO01CRYPTO02 杂…

JavaScript的第三天

目录 JS中的循环&#xff0c;使某些代码重复执行 一、for循环&#xff1a;重复执行某段代码&#xff0c;通常用于计数 1、for的语法结构 2、代码解析 3、代码尝试 4、循环重复相同的代码&#xff0c;可以让用户控制输出的次数&#xff08;对该变量进行遍历&#xff09; 5、循环…

perl 给特定文件加上特定内容

perl 给特定文件加上特定内容 给所有的输入文件&#xff0c;加上特定的内容 本例中&#xff0c;给所有的输入文件内加入## Copyright xxx 如果检测到已经有## Copyright字样的行&#xff0c;那么不添加&#xff0c;具体代码如下。 可以使用该脚本&#xff0c;给所有的verilog文…

TCP与UDP

TCP与UDP区别&#xff1a;可靠连接和不可靠连接 细节&#xff1a; 一、连接性&#xff1a; TCP&#xff1a;是面向连接的协议。通信双方在传数据前必须通过三次握手建立连接&#xff0c;在数据传输结束后会还需进行四次挥手断开连接。 UDP&#xff1a;是无连接的协议。发送…

Linux 命令练习手册

1、cat命令练习 基本功能 功能&#xff1a;连接文件并输出其内容到标准输出。常用于查看文件、合并文件、重定向输出。 常用选项 -n&#xff1a;显示行号。 -b&#xff1a;显示非空行的行号。 -E&#xff1a;显示每行的结束符$&#xff0c;用于标识行尾。 -T&#xff1a;…

【K8s】专题十四(2):Kubernetes 安全机制之 Security Context

本文内容均来自个人笔记并重新梳理&#xff0c;如有错误欢迎指正&#xff01; 如果对您有帮助&#xff0c;烦请点赞、关注、转发、订阅专栏&#xff01; 专栏订阅入口 | 精选文章 | Kubernetes | Docker | Linux | 羊毛资源 | 工具推荐 | 往期精彩文章 【Docker】&#xff08;全…

JavaSE之String类

文章目录 一、String类常用的构造方法二、常见的四种String对象的比较1.使用比较2.使用equals()方法比较3.使用compareTo()方法比较4.使用compareToIgnoreCase()方法比较 三、字符串的查找四、字符串的转化1.数字和字符串间的转化2.大小写转化3.字符串和数组间的转化 五、字符串…

docker 指令集

docker 操作命令汇集说明&#xff1a; 1.将运行中的Docker容器保存为镜像 docker commit <容器ID或名称> <镜像名称>:<标签> 例如 docker commit abc123 my_image:latest 2.将镜像保存为tar文件 docker save -o <tar文件名…