数据结构2 :双向链表和内核链表

2024-09-07 02:52

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

1.双向链表是一种链表数据结构,其中每个节点包含三个部分:一个数据域(存储节点的数据)、一个前驱指针(指向列表中的前一个节点)和一个后继指针(指向列表中的下一个节点)。这种结构使得遍历和修改链表变得非常灵活,因为它可以从任意一个节点开始向前或向后遍历。

2.双向链表的特点

     1. 双向遍历:可以从头节点遍历到尾节点,也可以从尾节点遍历到头节点。

     2. 方便插入和删除:在双向链表中插入或删除一个节点只需要修改相邻节点的前后指针,而不需要遍历整个链表来查找前驱或后继节点。

     3. 额外的空间开销:每个节点需要额外存储两个指针,因此相对于单向链表,双向链表占用更多内存。

3.双向链表的优点

灵活性:可以在任意位置插入或删除节点,而无需重新排列整个链表。

双向遍历:可以从头到尾或从尾到头遍历链表,提供了更高的灵活性。

方便实现复杂操作:如反转链表、合并链表等操作变得更加简单。

4。双向链表的缺点

   额外的空间开销:每个节点需要额外存储两个指针,增加了内存消耗。

  稍微复杂的操作:相对于单向链表,双向链表的操作逻辑稍微复杂一些,需要同时更新前后指针。

双向链表的创建与插入

Dlink_t *create_doulink()
{Dlink_t *pdlink = malloc(sizeof(Dlink_t));if(NULL == pdlink){perror("malloc fail");return NULL;}pdlink->phead = NULL;pdlink->clen = 0;pthread_mutex_init(&(pdlink->mutex),NULL);return pdlink;
}
int is_empty_doulink(Dlink_t *pdlink)
{return NULL == pdlink->phead;
}
int push_doulink_head(Dlink_t *pdlink,DATATYPE data)
{DLink_Node_t *pnode = malloc(sizeof(DLink_Node_t));if(NULL == pnode){perror("malloc fail");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if(is_empty_doulink(pdlink)){pdlink->phead = pnode;}else{pnode->pnext = pdlink->phead;pdlink->phead->ppre = pnode;pdlink->phead = pnode;}pdlink->clen++;return 0;
}

双向链表的查找和修改

DLink_Node_t *find_doulink(Dlink_t *pdlink,char *name)
{if(is_empty_doulink(pdlink)){return NULL;}else{DLink_Node_t *p = pdlink->phead;while(p != NULL){if(strcmp(p->data.name,name) == 0){return p;}p = p->pnext;}}return NULL;
}
DLink_Node_t *change_doulink(Dlink_t *pdlink,char *oldname,int newscore)
{if(is_empty_doulink(pdlink)){return NULL;}else{DLink_Node_t *p = find_doulink(pdlink,oldname);if(p != NULL){p->data.score = newscore;return p;}}
}

双向链表的删除和销毁

int pop_doulink_head(Dlink_t *pdlink)
{DLink_Node_t *p = pdlink->phead;if(is_empty_doulink(pdlink)){return 0;}if(1 == pdlink->clen){free(p);pdlink->phead = NULL;}else{pdlink->phead = p->pnext;p->pnext->ppre = NULL;free(p);}pdlink->clen--;return 0;
}
void destroy_doulink(Dlink_t *pdlink)
{while(!is_empty_doulink(pdlink)){pop_doulink_head(pdlink);}free(pdlink);
}

2.内核链表

 内核链表通常指的是在操作系统内核中使用的链表结构。内核链表是操作系统内核用来管理和组织内核数据结构的一种重要工具。

内核链表的特点

1. 并发安全性:内核链表需要在多处理器或多线程环境中安全地进行并发访问,通常需要使用原子操作或锁机制来保证数据的一致性。

2. 内存管理:内核链表的节点需要从内核的内存池中分配和回收,因此需要考虑内存碎片和内存使用效率等问题。

3. 高性能:内核链表需要在低级别的系统操作中提供高性能的支持,如进程调度、设备驱动等。

4. 稳定性:内核链表的实现需要非常稳定可靠,任何错误都可能导致系统崩溃或其他严重后果。

内科链表的创建和插入

KLink_t *create_klink()
{KLink_t *pklink = malloc(sizeof(KLink_t));if(NULL == pklink){perror("malloc fail");return NULL;}pklink->phead = NULL;pklink->clen = 0;pthread_mutex_init(&(pklink->mutex),NULL);return pklink;
}
int push_klink_head(KLink_t *pklink,void*p)
{KNode_t *pnode = (KNode_t *)p;pnode->ppre = NULL;pnode->pnext = NULL;pnode->pnext = pklink->phead;if(pklink->phead != NULL){pklink->phead->ppre = pnode;}pklink->phead = pnode;pklink->clen++;return 0;
}

内核链表的删除和销毁

int pop_klink_head(KLink_t *pklink)
{if(is_empty_klink(pklink)){return 0;}KNode_t *pnode = pklink->phead;if(plink->phead->pnext == NULL){pklink->phead = NULL;free(pnode);}else{pklink->phead = pnode->pnext;pklink->phead->ppre = NULL;free(pnode);}pklink->clen--;return 1;
}
void destroy_klink(KLink_t *pklink)
{while(!is_empty_klink(pklink)){pop_klink_head(pklink);}free(pklink);
}

这篇关于数据结构2 :双向链表和内核链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1143852

相关文章

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

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

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

内核启动时减少log的方式

内核引导选项 内核引导选项大体上可以分为两类:一类与设备无关、另一类与设备有关。与设备有关的引导选项多如牛毛,需要你自己阅读内核中的相应驱动程序源码以获取其能够接受的引导选项。比如,如果你想知道可以向 AHA1542 SCSI 驱动程序传递哪些引导选项,那么就查看 drivers/scsi/aha1542.c 文件,一般在前面 100 行注释里就可以找到所接受的引导选项说明。大多数选项是通过"_

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-选择排序)

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.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

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

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图