初阶数据结构【双链表及其接口的实现】

news/2025/1/15 10:25:52/

目录

  • 前言
  • 一、基本结构
  • 二、双链表的接口实现
    • 2.1 双链表基本功能接口
      • 2.1.1 双向链表打印
      • 2.1.2 申请一个节点
      • 2.1.3 创建并返回双向链表的头结点
      • 2.1.4 双向链表清理（不销毁）
      • 2.1.5 双向链表销毁
    • 2.2 双向链表增加节点接口
      • 2.2.1 双向链表头插
      • 2.2.2 双向链表尾插
      • 2.2.3 双向链表在pos的前面进行插入
      • 2.2.4 优化头插尾插
    • 2.3 双向链表删除节点接口
      • 2.3.1 双向链表的头删
      • 2.3.2 双向链表的尾删
      • 2.3.3 双向链表删除pos位置的结点
      • 2.3.4 优化头删尾删
    • 2.4 双向链表修改节点数据接口
    • 2.5 双向链表查找节点接口
  • 三、顺序表和链表的区别
  • 四、是否传二级指针的总结
  • 总结

前言

前面我们介绍了数据结构中的链表，并实现了我们在实际中最常用的两个链表之一——无头单向非循环链表，这期我们继续来用C语言实现第二个常用链表——带头双向循环链表；

一、基本结构

带头双向循环链表(简称双向链表)的结构
在这里插入图片描述

typedef struct ListNode
{struct ListNode* next; //指向下一个节点struct ListNode* prev; //指向上一个节点LTDataType data;
}ListNode;

二、双链表的接口实现

2.1 双链表基本功能接口

2.1.1 双向链表打印

我们为了验证双向链表的其他接口，我们需要实时打印双向链表，所以我们单独设计一个打印模块：

这里我们唯一要知道的是双向循环链表的空链表形式的prev和next都指向自己自身：
在这里插入图片描述

// 双向链表打印
void ListPrint(ListNode* plist) {assert(plist);ListNode* cur = plist->next;if (cur == plist)printf("空链表");while (cur != plist){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

2.1.2 申请一个节点

当我们需要对双链表进行增加一个节点，我们就要利用malloc来申请一个节点的空间，为了提高代码的复用性，我们将这部分代码封装成函数：

//申请一个节点
ListNode* BuyListNode(LTDataType x) {ListNode* newNode = malloc(sizeof(ListNode));if (newNode == NULL){perror("malloc");exit(-1);}newNode->data = x;newNode->next = NULL;newNode->prev = NULL;return newNode;
}

2.1.3 创建并返回双向链表的头结点

我们根据前面的申请节点接口可以很容易写出创建双向链表的接口（初始双向链表为空）:

// 创建返回链表的头结点.
void ListCreate(ListNode** pplist) {*pplist = BuyListNode(0);(*pplist)->next = *pplist;(*pplist)->prev = *pplist;
}

2.1.4 双向链表清理（不销毁）

当我们不想要这个双向链表的值，但是接下来还要使用这个双向链表，需要对双向链表执行一个清理的操作：

这里我们简单讲解一下使用的思想，由于我们free掉一个节点我们就无法再通过这个节点的next来寻找下个节点，所以我们这里实现这个操作需要两个节点来实现；

// 双向链表清理但不销毁,保留头结点可以继续使用
void ListClear(ListNode* plist){assert(plist);ListNode* cur = plist->next;while (cur != plist){ListNode* next = cur->next; //记录下一个节点的地址free(cur);  //释放目标节点cur = next; //指向下一个节点}plist->next = plist;plist->prev = plist;
}

2.1.5 双向链表销毁

我们先将头节点之后的节点进行释放，最后将头结点释放，第一步我们可以复用双向链表的清理：

// 双向链表销毁,利用二级指针，将plist置为空，防止野指针
void ListDestory(ListNode** plist) {assert(*plist);/*ListNode* cur = plist;while (cur != plist){ListNode* next = cur->next;free(cur);cur = next;}*/ListClear(*plist);free(*plist);*plist = NULL;
}

2.2 双向链表增加节点接口

2.2.1 双向链表头插

双向链表比较于单向链表的头插简单的多，我们简单画图理解：

我们先申请一个节点cur，记录插入后目标节点的后面一个节点curNext，进行头插：
在这里插入图片描述

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x) {assert(plist);//创建新节点ListNode* cur = BuyListNode(x);//找到插入后的下一个节点ListNode* curNext = plist->next;//解决头指针与新节点的链接plist->next = cur;cur->prev = plist;//解决下一个节点与新节点的链接curNext->prev = cur;cur->next = curNext;
}

2.2.2 双向链表尾插

与上面的头插一样，我们需要先申请一个节点newNode，找到双向链表的尾tail，再将其插入双向链表尾部：
在这里插入图片描述

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{//防止plist为空assert(plist);ListNode* tail = plist->prev;ListNode* newNode = BuyListNode(x);//申请一个节点//链接tail->next = newNode;newNode->prev = tail;newNode->next = plist;plist->prev = newNode;
}

2.2.3 双向链表在pos的前面进行插入

我们通过上面的头插和尾插已经有了一定的经验，我们想要插入一个节点，我们需要知道插入节点的前后两个节点的地址，我们想要在pos前插入节点，我们要知道插入节点前pos的prev，想到这，我们实现pos前面插入就不难了：

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {assert(pos);//申请新的节点ListNode* cur = BuyListNode(x);ListNode* curPrev = pos->prev;//解决cur与前面的节点的链接curPrev->next = cur;cur->prev = curPrev;//解决cur与后面的节点的链接cur->next = pos;pos->prev = cur;
}

若想实现在pos后插入也是同理的，这里就不多赘述了；

2.2.4 优化头插尾插

到这我相信大家发现了这三种插入其实是一个插入：
头插可以写成：

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x) {assert(plist);创建新节点//ListNode* cur = BuyListNode(x);找到插入后的下一个节点//ListNode* curNext = plist->next;解决头指针与新节点的链接//plist->next = cur;//cur->prev = plist;解决下一个节点与新节点的链接//curNext->prev = cur;//cur->next = curNext;ListInsert(plist->next, x);
}

同理，尾插可以写成：

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{//防止plist为空assert(plist);//ListNode* tail = plist->prev;////ListNode* newNode = BuyListNode(x);链接//tail->next = newNode;//newNode->prev = tail;//newNode->next = plist;//plist->prev = newNode;ListInsert(plist, x);
}

2.3 双向链表删除节点接口

2.3.1 双向链表的头删

我们要讲目标节点的上一个节点和下一个节点链接起来即可，我们需要注意的是，删除的节点我们最后要free掉：
在这里插入图片描述

// 双向链表头删
void ListPopFront(ListNode* plist) {assert(plist);assert(plist != plist->next);//防止对空链表删除，free了头指针//指向被删节点ListNode* cur = plist->next;//被删节点的下个节点ListNode* curNext = cur->next;//取消头结点与第一个节点链接plist->next = curNext;curNext->prev = plist;//释放空间free(cur);cur = NULL;
}

2.3.2 双向链表的尾删

理解了上面的头删，我们很容易写出尾删：
这里很多人会这样写：

 //双向链表尾删
void ListPopBack(ListNode* plist) {assert(plist);//找到尾节点ListNode* tail = plist->prev;//改变头指针的prevplist->prev = tail->prev;//改变尾指针上一个节点的nexttail->prev->next = plist;free(tail);tail = NULL;//防止野指针，函数内部局部变量，不置空也可以
}

这样写本身没有什么错误，但是不利于代码的可读性，所以我们一般这样来写：

//上面的代码不利于可读性，我们可以这样写
void ListPopBack(ListNode* plist) {assert(plist);assert(plist->next != plist);//防止对空链表进行删除ListNode* tail = plist->prev;ListNode* tailPrev = tail->prev; //需要删除节点的上一个节点tailPrev->next = plist; plist->prev = tailPrev;free(tail);tail = NULL;//防止野指针，函数内部局部变量，不置空也可以
}

2.3.3 双向链表删除pos位置的结点

// 双向链表删除pos位置的结点
void ListErase(ListNode* pos) {assert(pos);/*assert(pos != plist);*/ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);pos = NULL;
}

2.3.4 优化头删尾删

与插入一样我们同样可以使用ListErase一个接口来实现这里所有的删除：

双链表的头删：

void ListPopFront(ListNode* plist) {assert(plist);assert(plist != plist->next);//防止对空链表删除，free了头指针指向被删节点//ListNode* cur = plist->next;被删节点的下个节点//ListNode* curNext = cur->next;取消头结点与第一个节点链接//plist->next = curNext;//curNext->prev = plist;释放空间//free(cur);//cur = NULL;ListErase(plist->next);
}

双链表的尾删：

void ListPopBack(ListNode* plist) {assert(plist);assert(plist->next != plist);//防止对空链表进行删除//ListNode* tail = plist->prev;//ListNode* tailPrev = tail->prev;//tailPrev->next = plist;//plist->prev = tailPrev;//free(tail);//tail = NULL;//防止野指针，函数内部局部变量，不置空也可以ListErase(plist->prev);
}

2.4 双向链表修改节点数据接口

通过节点的地址来将所指节点的数据进行修改：

//双向链表修改数据接口
void ListUpData(ListNode* pos, LTDataType x){assert(pos);pos->data = x;
}

pos节点一般由下面的查找节点接口实现。

2.5 双向链表查找节点接口

通过数据查找节点，如果找到节点我们就返回这个节点的地址，反之，返回空：

// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x) {assert(plist);ListNode* cur = plist->next;while(cur != plist){if (cur->data == x)return cur;cur = cur->next;}//没找到return NULL;
}

三、顺序表和链表的区别

到目前为止我们已经用C语言实现了顺序表和链表的部分接口，我们也已经知道两者部分的优缺点，我们今天做一个总结：

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持 O(1)不支持：O(N)
任意位置插入或删除元素可能需要搬移元素，效率低 O(N)只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

要想了解的更详细可以去看看<<深入理解计算机系统>>

四、是否传二级指针的总结

通过我们对顺序表和链表的实现接口的过程中我们有时候需要改变其头指针的值，如对无头单链表进行头插：

在这里插入图片描述
这样由于头指针发生了改变，所以我们要传二级指针来修改这个指针的值，这样我们就不难理解为什么要创造出带哨兵位的链表了；

总结

这期我们利用C语言实现了带头双向循环链表的接口，我们充分体会到了链表对于顺序表的优点.我们下期继续，谢谢观看；
26考研一战成硕！


http://www.ppmy.cn/news/1563295.html

相关文章

如何选择 Redis 持久化方式？RDB 和 AOF 的优缺点分析

如何选择 Redis 持久化方式？RDB 和 AOF 的优缺点分析

前言 在开发中&#xff0c;Redis 通常作为缓存使用。由于其特性&#xff0c;查询数据通常比直接访问关系型数据库快得多。但如果未开启持久化&#xff0c;内存中的缓存可能会因意外丢失&#xff0c;尤其是还未同步到持久层的数据。这让持久化变得非常重要。本文将分享我对 Redi…
阅读更多...
jupyter notebook练手项目：线性回归——学习时间与成绩的关系

jupyter notebook练手项目：线性回归——学习时间与成绩的关系

线性回归——学习时间与学习成绩的关系 第1步&#xff1a;导入工具库 pandas——数据分析库&#xff0c;提供了数据结构&#xff08;如DataFrame和Series&#xff09;和数据操作方法&#xff0c;方便对数据集进行读取、清洗、转换等操作。 matplotlib——绘图库&#xff0c;p…
阅读更多...
脚本化挂在物理盘、nfs、yum、pg数据库、nginx（已上传脚本）

脚本化挂在物理盘、nfs、yum、pg数据库、nginx（已上传脚本）

文章目录 前言一、什么是脚本化安装二、使用步骤1.物理磁盘脚本挂载&#xff08;离线&#xff09;2.yum脚本化安装&#xff08;离线&#xff09;3.nfs脚本化安装&#xff08;离线&#xff09;4.pg数据库脚本化安装&#xff08;离线&#xff09;5.nginx脚本化安装&#xff08;离…
阅读更多...
第六届土木建筑及灾害防控国际学术会议暨第三届智慧城市建筑与基础设施耐久性国际学术会议（CADPC DuraBI 2025）

第六届土木建筑及灾害防控国际学术会议暨第三届智慧城市建筑与基础设施耐久性国际学术会议（CADPC DuraBI 2025）

第六届土木建筑及灾害防控国际学术会议暨第三届智慧城市建筑与基础设施耐久性国际学术会议&#xff08;CADPC & DuraBI 2025&#xff09;将于2025年2月28日-3月2日在青岛举办。会议将以“建筑技术”、“灾害预测”、“灾害防控”、“灾后重建”等主题展开学术研讨&#xff…
阅读更多...
Java IDEA中Gutter Icons图标的含义

Java IDEA中Gutter Icons图标的含义

前些天发现了一个蛮有意思的人工智能学习网站,8个字形容一下"通俗易懂&#xff0c;风趣幽默"&#xff0c;感觉非常有意思,忍不住分享一下给大家。 &#x1f449;点击跳转到教程 前言&#xff1a; 很多人刚开始用IDEA来学习编程&#xff0c;会发现下面这些图标。 但是…
阅读更多...
《视听导报》是什么类型的报纸？报纸上发文章要交版面费吗？

《视听导报》是什么类型的报纸？报纸上发文章要交版面费吗？

作为个人成果发表的重要场所&#xff0c;报纸目前正得到越来越多单位的认可。不过在投稿时&#xff0c;我们既要考虑投稿的报纸是否符合评审标准&#xff0c;也要考虑发表文章的成本是否在我们的承受范围之内。 下面就让我们以《视听导报》为例&#xff0c;了解下如何查看报纸的…
阅读更多...
【LeetCode: 240. 搜索二维矩阵 II + 指针 + 遍历】

【LeetCode: 240. 搜索二维矩阵 II + 指针 + 遍历】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…
阅读更多...
大模型训练中如何找到内存泄漏

大模型训练中如何找到内存泄漏

内存泄漏的常见原因 1.内存泄漏有可能是我们创建一个全局的list,每次iter都会往其中添加Tensor,会导致内存泄漏&#xff1b; 2.如果我们某个Tensor在计算图中的前向计算&#xff0c;但是没有参与反向更新参数&#xff0c;可能会导致内存泄漏&#xff0c;因为pytorch的内存管理…
阅读更多...
最新文章

Copyright @ 2022~2023