詳細(xì)介紹鏈表在操作系統(tǒng)中定義和使用的方式

引言

鏈表和數(shù)組是兩種不同的數(shù)據(jù)存儲(chǔ)方式。鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。數(shù)組是把具有相同類型的若干元素按有序的形式組織起來(lái)的一種形式，數(shù)組中的各元素的存儲(chǔ)是有先后順序的，它們?cè)趦?nèi)存中按照這個(gè)先后順序連續(xù)存放在一起。本文將對(duì)這兩種存儲(chǔ)方式的優(yōu)缺點(diǎn)做一個(gè)大致的介紹，并詳細(xì)介紹鏈表在操作系統(tǒng)中定義和使用的方式。

一、鏈表和數(shù)組

鏈表是鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，數(shù)組是順序的存儲(chǔ)結(jié)構(gòu)，其在內(nèi)存存儲(chǔ)上的不同形式?jīng)Q定了其各自的特點(diǎn)。

鏈表通過(guò)指針來(lái)鏈接元素，鏈表中的結(jié)點(diǎn)順序關(guān)系由指針來(lái)體現(xiàn)；數(shù)組將元素按次序依次存儲(chǔ)，元素順序關(guān)系由元素在數(shù)組中的位置（下標(biāo)）確定。

鏈表節(jié)點(diǎn)的存儲(chǔ)單元在程序執(zhí)行時(shí)動(dòng)態(tài)向系統(tǒng)申請(qǐng)，鏈表的結(jié)點(diǎn)個(gè)數(shù)可按需要增減；數(shù)組元素的存儲(chǔ)單元在數(shù)組定義時(shí)分配，其元素個(gè)數(shù)是固定的，對(duì)于不是固定長(zhǎng)度的列表，用可能最大長(zhǎng)度的數(shù)組來(lái)描述。

鏈表插入刪除元素不需要移動(dòng)元素，且較為容易實(shí)現(xiàn)長(zhǎng)度擴(kuò)充，但是尋找某個(gè)元素較為困難；數(shù)組尋找某個(gè)元素較為簡(jiǎn)單，但插入與刪除比較復(fù)雜。

總體來(lái)說(shuō)，鏈表使用指針將一系列數(shù)據(jù)節(jié)點(diǎn)鏈接成數(shù)據(jù)鏈，相對(duì)于數(shù)組，它具有良好的動(dòng)態(tài)性，建立鏈表時(shí)不需要提前知道數(shù)據(jù)量，可以隨時(shí)分配空間，可以高效地在鏈表中的任意位置插入或者刪除數(shù)據(jù)。操作系統(tǒng)中存在著大量的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)鏈表和鏈表項(xiàng)，理解鏈表對(duì)理解操作系統(tǒng)至關(guān)重要。

二、單向鏈表和雙向鏈表

通常鏈表數(shù)據(jù)結(jié)構(gòu)包含兩部分，一部分是數(shù)據(jù)域，用于存儲(chǔ)數(shù)據(jù)；另外一部分是指針域，用于建立與其它節(jié)點(diǎn)的關(guān)系。鏈表項(xiàng)中可以包含一個(gè)指向下一個(gè)鏈表項(xiàng)的指針而不包含指向上一個(gè)鏈表的指針，也可以兩者都包含，前者稱為單向鏈表，后者為雙向鏈表。

OneOS 物聯(lián)網(wǎng)操作系統(tǒng)中提供的鏈表不包含數(shù)據(jù)域，使用時(shí)不是在鏈表結(jié)構(gòu)中包含數(shù)據(jù)，而是在用戶的數(shù)據(jù)結(jié)構(gòu)中包含鏈表節(jié)點(diǎn)，操作系統(tǒng)中提供了雙向鏈表及單向鏈表的一些比較通用的操作接口。

2.1 單向鏈表

OneOS 操作系統(tǒng)中的單向鏈表包含一個(gè)節(jié)點(diǎn)指針，這個(gè)節(jié)點(diǎn)指針指向下一個(gè)節(jié)點(diǎn)。OneOS 操作系統(tǒng)中的單向鏈表是一個(gè)非循環(huán)鏈表，單向鏈表本身首尾并非相連，單向鏈表中的最后一個(gè)節(jié)點(diǎn)指向 OS_NULL（循環(huán)鏈表單向鏈表中的最后一個(gè)節(jié)點(diǎn)指向單向鏈表中的第一個(gè)節(jié)點(diǎn)），其示意圖如下所示。

OneOS 操作系統(tǒng)中單向鏈表節(jié)點(diǎn)的結(jié)構(gòu)體如下所示。

struct os_slist_node
{
    struct os_slist_node *next;     /* Point to next node */
};

2.2 雙向鏈表

OneOS 操作系統(tǒng)中的雙向鏈表包含了兩個(gè)結(jié)點(diǎn)指針，一個(gè)節(jié)點(diǎn)指針指向下一個(gè)節(jié)點(diǎn)，另一個(gè)節(jié)點(diǎn)指針指向上一個(gè)節(jié)點(diǎn)。OneOS 操作系統(tǒng)中的雙向鏈表是一個(gè)循環(huán)鏈表，雙向鏈表本身首尾相連，雙向鏈表最后一個(gè)節(jié)點(diǎn)的指向下一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)指針指向第一個(gè)節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)的指向上一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)指針指向最后一個(gè)節(jié)點(diǎn)，其示意圖如下所示。

OneOS 操作系統(tǒng)中雙向鏈表節(jié)點(diǎn)的結(jié)構(gòu)體如下所示。

struct os_list_node
{
    struct os_list_node *next;      /* Point to next node */
    struct os_list_node *prev;      /* point to previous node */
};

三、應(yīng)用示例

單向鏈表應(yīng)用示例

#include #include #include #include #include #include #include 
#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 #include #include #include #include #include #include 
#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