详细介绍链表在操作系统中定义和使用的方式

引言
链表和数组是两种不同的数据存储方式。链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。数组是把具有相同类型的若干元素按有序的形式组织起来的一种形式,数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起。本文将对这两种存储方式的优缺点做一个大致的介绍,并详细介绍链表在操作系统中定义和使用的方式。
一、链表和数组
链表是链式的存储结构,数组是顺序的存储结构,其在内存存储上的不同形式决定了其各自的特点。
链表通过指针来链接元素,链表中的结点顺序关系由指针来体现;数组将元素按次序依次存储,元素顺序关系由元素在数组中的位置(下标)确定。
链表节点的存储单元在程序执行时动态向系统申请,链表的结点个数可按需要增减;数组元素的存储单元在数组定义时分配,其元素个数是固定的,对于不是固定长度的列表,用可能最大长度的数组来描述。
链表插入删除元素不需要移动元素,且较为容易实现长度扩充,但是寻找某个元素较为困难;数组寻找某个元素较为简单,但插入与删除比较复杂。
总体来说,链表使用指针将一系列数据节点链接成数据链,相对于数组,它具有良好的动态性,建立链表时不需要提前知道数据量,可以随时分配空间,可以高效地在链表中的任意位置插入或者删除数据。操作系统中存在着大量的基础数据结构链表和链表项,理解链表对理解操作系统至关重要。
二、单向链表和双向链表
通常链表数据结构包含两部分,一部分是数据域,用于存储数据;另外一部分是指针域,用于建立与其它节点的关系。链表项中可以包含一个指向下一个链表项的指针而不包含指向上一个链表的指针,也可以两者都包含,前者称为单向链表,后者为双向链表。
oneos 物联网操作系统中提供的链表不包含数据域,使用时不是在链表结构中包含数据,而是在用户的数据结构中包含链表节点,操作系统中提供了双向链表及单向链表的一些比较通用的操作接口。
2.1 单向链表
oneos 操作系统中的单向链表包含一个节点指针,这个节点指针指向下一个节点。oneos 操作系统中的单向链表是一个非循环链表,单向链表本身首尾并非相连,单向链表中的最后一个节点指向 os_null(循环链表单向链表中的最后一个节点指向单向链表中的第一个节点),其示意图如下所示。
oneos 操作系统中单向链表节点的结构体如下所示。
struct os_slist_node{ struct os_slist_node *next; /* point to next node */};  
2.2 双向链表
oneos 操作系统中的双向链表包含了两个结点指针,一个节点指针指向下一个节点,另一个节点指针指向上一个节点。oneos 操作系统中的双向链表是一个循环链表,双向链表本身首尾相连,双向链表最后一个节点的指向下一个节点的节点指针指向第一个节点,第一个节点的指向上一个节点的节点指针指向最后一个节点,其示意图如下所示。
oneos 操作系统中双向链表节点的结构体如下所示。
struct os_list_node{ struct os_list_node *next; /* point to next node */ struct os_list_node *prev; /* point to previous node */};  
三、应用示例
单向链表应用示例
#include #include #include #include #include #include #include #define test_tag test#define student_num 10#define test_name_max 16char *name[student_num] = {xiaoming, xiaohua, xiaoqiang, xiaoli, xiaofang, zhangsan, lisi, wangwu, zhaoliu, qianqi};uint32_t score[student_num] = {70, 83, 68, 80, 88, 86, 78, 92, 55, 82};struct student_score{ os_slist_node_t list_node; char name[test_name_max]; uint32_t id; uint32_t score;};typedef struct student_score student_score_t;void single_list_sample(void){ uint32_t i = 0; os_slist_node_t list_head = os_slist_init(list_head); student_score_t *data; os_slist_node_t *node_temp; os_slist_node_t *node; log_w(test_tag, single_list_sample insert data); for (i = 0; i id = i; memset(data->name, 0, test_name_max); strncpy(data->name, name[i], test_name_max); data->score = score[i]; if (i id, data->score, data->name); os_slist_add_tail(&list_head, &data->list_node); } else { log_w(test_tag, insert front-- id:%d score:%d name:%s, data->id, data->score, data->name); os_slist_add(&list_head, &data->list_node); } } log_w(test_tag, single_list_sample show result); os_slist_for_each(node, &list_head) { data = os_slist_entry(node, student_score_t, list_node); log_w(test_tag, id:%d score:%d name:%s, data->id, data->score, data->name); } log_w(test_tag, single_list_sample list_len is:%d, os_slist_len(&list_head)); log_w(test_tag, single_list_sample delete the score less than 60); os_slist_for_each_safe(node, node_temp, &list_head) { data = os_slist_entry(node, student_score_t, list_node); if (data->score id, data->score, data->name); os_slist_del(&list_head, &data->list_node); os_free(data); } } log_w(test_tag, single_list_sample list_len is:%d, os_slist_len(&list_head)); log_w(test_tag, single_list_sample show result, and then delete); os_slist_for_each_safe(node, node_temp, &list_head) { data = os_slist_entry(node, student_score_t, list_node); log_w(test_tag, delete -- id:%d score:%d name:%s, data->id, data->score, data->name); os_slist_del(&list_head, &data->list_node); os_free(data); } log_w(test_tag, single_list_sample list_len is:%d, os_slist_len(&list_head));}sh_cmd_export(test_single_list, single_list_sample, test single list);运行结果sh>test_single_listw/test: single_list_sample insert dataw/test: insert tail -- id:0 score:70 name:xiaomingw/test: insert tail -- id:1 score:83 name:xiaohuaw/test: insert tail -- id:2 score:68 name:xiaoqiangw/test: insert tail -- id:3 score:80 name:xiaoliw/test: insert tail -- id:4 score:88 name:xiaofangw/test: insert front-- id:5 score:86 name:zhangsanw/test: insert front-- id:6 score:78 name:lisiw/test: insert front-- id:7 score:92 name:wangwuw/test: insert front-- id:8 score:55 name:zhaoliuw/test: insert front-- id:9 score:82 name:qianqiw/test: single_list_sample show resultw/test: id:9 score:82 name:qianqiw/test: id:8 score:55 name:zhaoliuw/test: id:7 score:92 name:wangwuw/test: id:6 score:78 name:lisiw/test: id:5 score:86 name:zhangsanw/test: id:0 score:70 name:xiaomingw/test: id:1 score:83 name:xiaohuaw/test: id:2 score:68 name:xiaoqiangw/test: id:3 score:80 name:xiaoliw/test: id:4 score:88 name:xiaofangw/test: single_list_sample list_len is:10w/test: single_list_sample delete the score less than 60w/test: delete -- id:8 score:55 name:zhaoliuw/test: single_list_sample list_len is:9w/test: single_list_sample show result, and then deletew/test: delete -- id:9 score:82 name:qianqiw/test: delete -- id:7 score:92 name:wangwuw/test: delete -- id:6 score:78 name:lisiw/test: delete -- id:5 score:86 name:zhangsanw/test: delete -- id:0 score:70 name:xiaomingw/test: delete -- id:1 score:83 name:xiaohuaw/test: delete -- id:2 score:68 name:xiaoqiangw/test: delete -- id:3 score:80 name:xiaoliw/test: delete -- id:4 score:88 name:xiaofangw/test: single_list_sample list_len is:0双向链表应用示例#include #include #include #include #include #include #include #define test_tag test#define student_num 10#define test_name_max 16char *name[student_num] = {xiaoming, xiaohua, xiaoqiang, xiaoli, xiaofang, zhangsan, lisi, wangwu, zhaoliu, qianqi};uint32_t score[student_num] = {70, 83, 68, 80, 88, 86, 78, 92, 55, 82};struct student_score{ os_list_node_t list_node; char name[test_name_max]; uint32_t id; uint32_t score;};typedef struct student_score student_score_t;void list_sample(void){ uint32_t i = 0; os_list_node_t list_head = os_list_init(list_head); student_score_t *data; student_score_t *data_temp; os_list_node_t *node; os_list_node_t *node_temp; log_w(test_tag, list_sample insert data); for (i = 0; i id = i; memset(data->name, 0, test_name_max); strncpy(data->name, name[i], test_name_max); data->score = score[i]; if (i id, data->score, data->name); os_list_add_tail(&list_head, &data->list_node); } else { log_w(test_tag, insert front-- id:%d score:%d name:%s, data->id, data->score, data->name); os_list_add(&list_head, &data->list_node); } } log_w(test_tag, list_sample show result); os_list_for_each_entry(data, &list_head, student_score_t, list_node) { log_w(test_tag, id:%d score:%d name:%s, data->id, data->score, data->name); } log_w(test_tag, list_sample list_len is:%d, os_list_len(&list_head)); log_w(test_tag, list_sample delete the score less than 60); os_list_for_each_entry_safe(data, data_temp, &list_head, student_score_t, list_node) { if (data->score id, data->score, data->name); os_list_del(&data->list_node); os_free(data); } } log_w(test_tag, list_sample list_len is:%d, os_list_len(&list_head)); log_w(test_tag, list_sample show result, and then delete); os_list_for_each_safe(node, node_temp, &list_head) { data = os_list_entry(node, student_score_t, list_node); log_w(test_tag, delete -- id:%d score:%d name:%s, data->id, data->score, data->name); os_list_del(&data->list_node); os_free(data); } log_w(test_tag, list_sample list_len is:%d, os_list_len(&list_head));}sh_cmd_export(test_list, list_sample, test list);运行结果sh>test_listw/test: list_sample insert dataw/test: insert tail -- id:0 score:70 name:xiaomingw/test: insert tail -- id:1 score:83 name:xiaohuaw/test: insert tail -- id:2 score:68 name:xiaoqiangw/test: insert tail -- id:3 score:80 name:xiaoliw/test: insert tail -- id:4 score:88 name:xiaofangw/test: insert front-- id:5 score:86 name:zhangsanw/test: insert front-- id:6 score:78 name:lisiw/test: insert front-- id:7 score:92 name:wangwuw/test: insert front-- id:8 score:55 name:zhaoliuw/test: insert front-- id:9 score:82 name:qianqiw/test: list_sample show resultw/test: id:9 score:82 name:qianqiw/test: id:8 score:55 name:zhaoliuw/test: id:7 score:92 name:wangwuw/test: id:6 score:78 name:lisiw/test: id:5 score:86 name:zhangsanw/test: id:0 score:70 name:xiaomingw/test: id:1 score:83 name:xiaohuaw/test: id:2 score:68 name:xiaoqiangw/test: id:3 score:80 name:xiaoliw/test: id:4 score:88 name:xiaofangw/test: list_sample list_len is:10w/test: list_sample delete the score less than 60w/test: delete -- id:8 score:55 name:zhaoliuw/test: list_sample list_len is:9w/test: list_sample show result, and then deletew/test: delete -- id:9 score:82 name:qianqiw/test: delete -- id:7 score:92 name:wangwuw/test: delete -- id:6 score:78 name:lisiw/test: delete -- id:5 score:86 name:zhangsanw/test: delete -- id:0 score:70 name:xiaomingw/test: delete -- id:1 score:83 name:xiaohuaw/test: delete -- id:2 score:68 name:xiaoqiangw/test: delete -- id:3 score:80 name:xiaoliw/test: delete -- id:4 score:88 name:xiaofangw/test: list_sample list_len is:0


打造高品质医院网络,加速医院智慧化升级
2014年全球车用MEMS传感器排名前十供应商
Xilinx VCU118评估套件实现四通道28Gbps光纤高速数据传输
南京集成电路大学的成立能否缓解人才缺口压力?
Micro OLED和Micro LED两种显示技术有哪些不同?
详细介绍链表在操作系统中定义和使用的方式
电子开关的工作原理 电子开关怎么安装
[组图]复式滤波电路
物联网和互联网之间有什么区别
Nsight DL Designer用于高效深度学习模型设计和开发
我国智能安保服务机器人已具备深厚的技术正在走向世界
为什么计算机需要操作系统?
什么是信号完整性
高智能土壤多参数测试系统的产品介绍说明
三菱XR号称合资性价比王者,悬浮式设计+混动四驱,仅售价12万
2017下半年即将发布的四款国产旗舰一加5、魅族pro7、小米mix2、小米note3,你期待谁?
RF射频电路为什么选取50欧姆作为阻抗匹配的数值呢?
意大利进口微生物快速检测仪的特点是什么
GPS的接口有哪些类型?
科普NPU、TPU、IPU是什么?