每日一博 | 数据存储，链表还是数组？

2023-02-20 318

引言

链表和数组是两种不同的数据存储方式。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。数组是把具有相同类型的若干元素按有序的形式组织起来的一种形式，数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。本文将对这两种存储方式的优缺点做一个大致的介绍，并详细介绍链表在操作系统中定义和使用的方式。

一、链表和数组

链表是链式的存储结构，数组是顺序的存储结构，其在内存存储上的不同形式决定了其各自的特点。

链表通过指针来链接元素，链表中的结点顺序关系由指针来体现；数组将元素按次序依次存储，元素顺序关系由元素在数组中的位置（下标）确定。
链表节点的存储单元在程序执行时动态向系统申请，链表的结点个数可按需要增减；数组元素的存储单元在数组定义时分配，其元素个数是固定的，对于不是固定长度的列表，用可能最大长度的数组来描述。
链表插入删除元素不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；数组寻找某个元素较为简单，但插入与删除比较复杂。

总体来说，链表使用指针将一系列数据节点链接成数据链，相对于数组，它具有良好的动态性，建立链表时不需要提前知道数据量，可以随时分配空间，可以高效地在链表中的任意位置插入或者删除数据。操作系统中存在着大量的基础数据结构链表和链表项，理解链表对理解操作系统至关重要。

二、单向链表和双向链表

通常链表数据结构包含两部分，一部分是数据域，用于存储数据；另外一部分是指针域，用于建立与其它节点的关系。链表项中可以包含一个指向下一个链表项的指针而不包含指向上一个链表的指针，也可以两者都包含，前者称为单向链表，后者为双向链表。

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 <oneos_config.h>#include <dlog.h>#include <os_errno.h>#include <shell.h>#include <string.h>#include <os_memory.h>#include <os_list.h>
#define TEST_TAG        "TEST"
#define STUDENT_NUM     10#define TEST_NAME_MAX   16
char *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 < STUDENT_NUM; i++)
    {
        data = os_malloc(sizeof(student_score_t));
        data->id = i;
        memset(data->name, 0, TEST_NAME_MAX);
        strncpy(data->name, name[i], TEST_NAME_MAX);
        data->score = score[i];
        if (i < STUDENT_NUM/2)
        {
            LOG_W(TEST_TAG, "insert tail -- id:%d score:%d name:%s", data->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 < 60)
        {
            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));
    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_list
W/TEST: single_list_sample insert data
W/TEST: insert tail -- id:0 score:70 name:xiaoming
W/TEST: insert tail -- id:1 score:83 name:xiaohua
W/TEST: insert tail -- id:2 score:68 name:xiaoqiang
W/TEST: insert tail -- id:3 score:80 name:xiaoli
W/TEST: insert tail -- id:4 score:88 name:xiaofang
W/TEST: insert front-- id:5 score:86 name:zhangsan
W/TEST: insert front-- id:6 score:78 name:lisi
W/TEST: insert front-- id:7 score:92 name:wangwu
W/TEST: insert front-- id:8 score:55 name:zhaoliu
W/TEST: insert front-- id:9 score:82 name:qianqi
W/TEST: single_list_sample show result
W/TEST: id:9 score:82 name:qianqi
W/TEST: id:8 score:55 name:zhaoliu
W/TEST: id:7 score:92 name:wangwu
W/TEST: id:6 score:78 name:lisi
W/TEST: id:5 score:86 name:zhangsan
W/TEST: id:0 score:70 name:xiaoming
W/TEST: id:1 score:83 name:xiaohua
W/TEST: id:2 score:68 name:xiaoqiang
W/TEST: id:3 score:80 name:xiaoli
W/TEST: id:4 score:88 name:xiaofang
W/TEST: single_list_sample list_len is:10
W/TEST: single_list_sample delete the score less than 60
W/TEST: delete -- id:8 score:55 name:zhaoliu
W/TEST: single_list_sample list_len is:9
W/TEST: single_list_sample show result, and then delete
W/TEST: delete -- id:9 score:82 name:qianqi
W/TEST: delete -- id:7 score:92 name:wangwu
W/TEST: delete -- id:6 score:78 name:lisi
W/TEST: delete -- id:5 score:86 name:zhangsan
W/TEST: delete -- id:0 score:70 name:xiaoming
W/TEST: delete -- id:1 score:83 name:xiaohua
W/TEST: delete -- id:2 score:68 name:xiaoqiang
W/TEST: delete -- id:3 score:80 name:xiaoli
W/TEST: delete -- id:4 score:88 name:xiaofang
W/TEST: single_list_sample list_len is:0

双向链表应用示例

#include <oneos_config.h>#include <dlog.h>#include <os_errno.h>#include <shell.h>#include <string.h>#include <os_memory.h>#include <os_list.h>
#define TEST_TAG        "TEST"
#define STUDENT_NUM     10#define TEST_NAME_MAX   16
char *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 < STUDENT_NUM; i++)
    {
        data = os_malloc(sizeof(student_score_t));
        data->id = i;
        memset(data->name, 0, TEST_NAME_MAX);
        strncpy(data->name, name[i], TEST_NAME_MAX);
        data->score = score[i];
        if (i < STUDENT_NUM/2)
        {
            LOG_W(TEST_TAG, "insert tail -- id:%d score:%d name:%s", data->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 < 60)
        {
            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));
    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_list
W/TEST: list_sample insert data
W/TEST: insert tail -- id:0 score:70 name:xiaoming
W/TEST: insert tail -- id:1 score:83 name:xiaohua
W/TEST: insert tail -- id:2 score:68 name:xiaoqiang
W/TEST: insert tail -- id:3 score:80 name:xiaoli
W/TEST: insert tail -- id:4 score:88 name:xiaofang
W/TEST: insert front-- id:5 score:86 name:zhangsan
W/TEST: insert front-- id:6 score:78 name:lisi
W/TEST: insert front-- id:7 score:92 name:wangwu
W/TEST: insert front-- id:8 score:55 name:zhaoliu
W/TEST: insert front-- id:9 score:82 name:qianqi
W/TEST: list_sample show result
W/TEST: id:9 score:82 name:qianqi
W/TEST: id:8 score:55 name:zhaoliu
W/TEST: id:7 score:92 name:wangwu
W/TEST: id:6 score:78 name:lisi
W/TEST: id:5 score:86 name:zhangsan
W/TEST: id:0 score:70 name:xiaoming
W/TEST: id:1 score:83 name:xiaohua
W/TEST: id:2 score:68 name:xiaoqiang
W/TEST: id:3 score:80 name:xiaoli
W/TEST: id:4 score:88 name:xiaofang
W/TEST: list_sample list_len is:10
W/TEST: list_sample delete the score less than 60
W/TEST: delete -- id:8 score:55 name:zhaoliu
W/TEST: list_sample list_len is:9
W/TEST: list_sample show result, and then delete
W/TEST: delete -- id:9 score:82 name:qianqi
W/TEST: delete -- id:7 score:92 name:wangwu
W/TEST: delete -- id:6 score:78 name:lisi
W/TEST: delete -- id:5 score:86 name:zhangsan
W/TEST: delete -- id:0 score:70 name:xiaoming
W/TEST: delete -- id:1 score:83 name:xiaohua
W/TEST: delete -- id:2 score:68 name:xiaoqiang
W/TEST: delete -- id:3 score:80 name:xiaoli
W/TEST: delete -- id:4 score:88 name:xiaofang
W/TEST: list_sample list_len is:0

更详细的API介绍欢迎前往OneOS官网文档中心查看。

文档中心 (10086.cn)

OneOS源码仓库：https://gitee.com/cmcc-oneos/OneOS

微信关注我们

原文链接：https://my.oschina.net/u/5443273/blog/7782411

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

Solon v2.1.4 发布，支持 Java、Kotlin、Groovy

本次发布，重点测试和验证了在 java、kotlin、groovy 三种 jvm 语言里，开箱即用的特性。并发布 Solon Initializr： https://solon.noear.org/start/ （也即将发布 idea 插件）最近，与小诺开源团队合作发布了：Snowy-Solon（ https://gitee.com/xiaonuoadmin/snowy-solon）有用户说原来他的电脑运行 snowy ，需要50秒启动占2g内存，现在只用5秒启动占300m内存有用户说原来启动 snowy 要15秒，现在3秒多点（不同电脑表现不同）有用户说原来认为是骗人的，现在信了（指更快、更小）有用户说他们的招聘要求已标注 “熟悉 Solon 框架的优先考虑”（这是难得好的新开始） Solon 应用开发框架的生态包括： 150 来个能力扩展插件 java、kotlin、groovy 三种语言开箱即用的特性官网与交流群 solon initializr 用户落地的开源或商业项目 Solon 生产力价值：更快、更小。带来IT成本、运维成本下降更简单。节省人力成本 So...

2023-02-21

363

EasyNode 是一个简易的个人 Linux 服务器管理面板 (webSSH&webSFTP)。功能简介多服务器管理。通过websocket实时更新服务器基本信息:系统、公网IP、CPU、内存、硬盘、网卡等基于浏览器解决SSH&SFTP跨端烦恼——Web SSH&Web SFTP 在线编辑文件

2023-02-21

330

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。