数据结构————双向链表

2024-09-05 15:12
文章标签 链表 数据结构 双向

本文主要是介绍数据结构————双向链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

内存泄漏：

内存泄漏（Memory Leak）是指程序中已动态分配的内存由于某种原因程序未释放或无法释放，导致系统内存的浪费，严重时会导致程序运行缓慢甚至崩溃。这种情况在长时间运行的程序或大型系统中尤为常见，因为它会随着时间的推移逐渐累积未释放的内存。

内存泄漏的原因

  1. 忘记释放内存：这是最常见的内存泄漏原因。程序员在申请内存后，由于疏忽或其他原因，忘记了在不再需要时释放它。

  2. 异常终止：如果程序在执行过程中因为异常（如错误、崩溃等）而终止，那么它可能无法执行正常的清理代码，导致内存泄漏。

  3. 缓存机制不当：有时为了优化性能，程序会缓存一些数据。如果缓存的数据量没有得到有效控制，或者缓存的清理策略不合理，就可能导致内存泄漏。

  4. 全局变量和静态变量：全局变量和静态变量的生命周期与程序相同，如果它们被用于存储动态分配的内存地址，并且这些内存在使用完毕后没有被释放，就会导致内存泄漏。

  5. 第三方库或API的使用：使用第三方库或API时，如果没有正确遵循其内存管理规则，也可能导致内存泄漏。

valgrind: 它主要用于内存调试、内存泄漏检测以及程序性能分析。

内存碎片：

内存碎片是指系统中所有不可用的空闲内存，这些碎片之所以不能被使用，是因为负责动态分配内存的分配算法使得这些空闲的内存无法使用。内存碎片可以分为外碎片和内碎片两种类型，下面分别进行详细介绍：

一、内存碎片的定义及分类

1. 外碎片
  • 定义：外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。
  • 产生原因：频繁的内存分配和释放、不同大小的内存分配、内存对齐问题等，都可能导致外碎片的产生。
2. 内碎片
  • 定义：内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间。
  • 产生原因：假设有一块连续空闲内存空间，当某个进程请求的内存大小与空闲内存块不完全匹配时，系统可能会分配一个稍大一点的内存块给该进程，从而产生内部碎片。

二、内存碎片的产生原因

  1. 频繁的内存分配和释放：这是导致内存碎片的主要原因之一。
  2. 不同大小的内存分配：当系统中分配的内存大小不一致时，也会导致碎片的产生。
  3. 内存对齐的问题：内存分配时如果没有进行对齐，也容易导致碎片。

双向有头链表：

双向有头链表是一种链表数据结构，与单向链表不同，双向链表中的每个节点都包含两个指针：一个指向下一个节点，另一个指向前一个节点。

创建链表：

Dlink_t *creat_doulink()
{Dlink_t *pdoulink = (Dlink_t *)malloc(sizeof(Dlink_t));if(NULL == pdoulink){perror("malloc fail");return NULL;}pdoulink->phead = NULL;pdoulink->clen = 0;pthread_mutex_init(&(pdoulink->mutex),NULL);return pdoulink;
}

遍历链表：

  1. 双向遍历：由于每个节点都包含前后两个指针，因此可以很方便地从前往后或从后往前遍历链表。
void doulink_for_each(DLink_t *pdoulink, int dir)
{if (is_empty_doulink(pdoulink))return;DLink_Node_t *p = pdoulink->phead;if (dir)//正向{while (p != NULL){printf("%d %s %d\n", p->data.id, p->data.name, p->data.score);p = p->pnext;}}else//反向{while (p->pnext != NULL){p = p->pnext;}while (p != NULL){printf("%d %s %d\n", p->data.id, p->data.name, p->data.score);p = p->ppre;}}printf("\n");}

头插：

int push_doulink_head(Dlink_t *pdoulink,DataType data)
{Dlink_Node_t *pnode =(Dlink_Node_t*) malloc(sizeof(Dlink_Node_t));if(NULL == pnode){perror("fail malloc");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if(is_empty_doulink(pdoulink)){pdoulink->phead = pnode;}else{pnode->pnext = pdoulink->phead;pdoulink->phead->ppre = pnode;pdoulink->phead = pnode;}pdoulink->clen++;return 0;
}

尾插：

int push_doulink_end(Dlink_t *pdoulink,DataType data)
{Dlink_Node_t *pnode = (Dlink_Node_t *)malloc(sizeof(Dlink_Node_t));if(pnode == NULL){perror("fail malloc");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if(is_empty_doulink(pdoulink)){pdoulink->phead = pnode;}else{Dlink_Node_t *p = pdoulink->phead;while(p->pnext != NULL){p = p->pnext;}p->pnext = pnode;pnode->ppre = p;}pdoulink->clen++;return 0;
}

头删：

int pop_doulink_head(Dlink_t *plink)
{if(is_empty_doulink(plink)){return 0;}Dlink_Node_t *p = plink->phead;plink->phead = p->pnext;p->ppre = NULL;free(p);plink->clen--;return 0;
}

尾删：

int pop_doulink_end(Dlink_t *plink)
{if(is_empty_doulink(plink))return 0;Dlink_Node_t *p = plink->phead;if(NULL == p->pnext){pop_doulink_head(plink);}while(p->pnext->pnext != NULL){p = p->pnext;}free(p->pnext);p->ppre = p;p->pnext = NULL;plink->clen--;
}

查找：

Dlink_Node_t *find_data(Dlink_t *plink,char *name)
{if(is_empty_doulink(plink))return  0;int i = 1;Dlink_Node_t *p = plink->phead;while(p != NULL){if(strcmp(name, p->data.name)==0){break;}p = p->pnext;if(p == NULL){return NULL;}}return p;
}

修改：

int change_data(Dlink_t *plink,char *name,int score)
{Dlink_Node_t *ptmp;ptmp = find_data(plink,name);Dlink_Node_t *p = plink->phead;while(p->pnext != NULL){if(p == ptmp){p->data.score = score;}p = p->pnext;}return 0;
}

销毁：

void destroy_doulink(Dlink_t *plink)
{while(!is_empty_doulink(plink)){     pop_doulink_head(plink);}free(plink);
}

双向链表的优势

双向链表相比于单向链表，具有以下几个显著的优势：

  1. 双向遍历能力：
    • 双向链表中的每个节点都包含两个指针，一个指向前一个节点（ppre），另一个指向下一个节点（pnext）。这种结构使得双向链表可以从链表的任何一个节点开始，向前或向后遍历整个链表。相比之下，单向链表只能从头节点开始，逐个节点向后遍历，无法直接向前遍历。
  2. 高效的插入和删除操作：
    • 在双向链表中插入或删除节点时，由于可以直接访问要插入或删除节点的前一个和/或后一个节点，因此可以更加高效地执行这些操作。例如，在双向链表中删除一个节点时，只需要修改该节点前后两个节点的指针，使其绕过被删除的节点即可，而不需要像单向链表那样可能需要遍历整个链表来找到要删除节点的前一个节点。
  3. 空间效率：
    • 虽然双向链表中的每个节点需要额外的空间来存储指向前一个节点的指针，但从整体来看，它在内存使用上仍然具有较高的灵活性。链表可以在运行时动态地分配和释放内存，而不需要像数组那样预先分配固定大小的内存块。这种动态内存分配的特性使得双向链表在处理不确定大小的数据集时更加灵活。

单向链表的优势

  1. 内存占用较少：
    单向链表的每个节点只需要存储一个指向下一个节点的指针（以及存储数据所需的空间）。而双向链表的每个节点除了存储数据外，还需要存储两个指针：一个指向前一个节点，另一个指向下一个节点。因此，在内存使用方面，单向链表更为节省。

  2. 实现更简单：
    从实现的角度来看，单向链表的结构更为简单直接，因为它只涉及到一个方向的链接。这意味着在编写代码时，你可能需要处理更少的边界情况和指针操作，尤其是在实现一些基本的链表操作时（如插入和删除）。

  3. 特定的应用场景：
    在某些特定的应用场景中，你可能只需要单向遍历链表，而不需要反向遍历。例如，当实现一个简单的栈（后进先出）或队列（先进先出）时，单向链表就足够了，因为它提供了所需的顺序访问功能，而无需额外的反向遍历能力。

  4. 兼容性：
    在某些旧的或资源受限的系统中，双向链表的额外内存开销可能是一个问题。在这些情况下，单向链表由于其较小的内存占用而成为更合适的选择。

  5. 性能优势（在某些情况下）：
    虽然这一点可能并不总是成立，但在某些特定的情况下，单向链表可能具有更好的性能。例如，在遍历链表时，如果只需要从头到尾遍历一次，并且不需要反向遍历，那么单向链表可能会由于更简单的结构和更少的指针操作而表现出更好的缓存局部性，从而在某些情况下提高性能。

这篇关于数据结构————双向链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1139308。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2