1868_C语言单向链表的实现

Grey

全部学习内容汇总： GitHub - GreyZhang/c_basic: little bits of c.

1868_C语言中简单的链表实现

简单整理一下链表的实现，这一次结合前面看到的一些代码简单修改做一个小结。

主题由来介绍

以前工作之中链表的使用其实不多，主要是控制类的软件设计中基本上不允许free以及malloc的存在。如果有这样的需求，一般来说也会直接用数组来实现。不过，有一些较为安全的存储分配机制之后，或许这个也可以重新考虑一下。这一次，我就是在看完了FreeRTOS的一部分代码之后考虑是否以后在我的工具箱中增加一点链表等功能模块。

信息整理分析

节点数据结构

typedef struct list_node
{
??? struct list_node * p_next_node;
??? uint32_t data;
} list_node_t;

单向链表的组成元素

单向链表的组成：head、元素、end。其中，head一般用来做链表的引用并且标记开头的位置。end，可以通过指向NULL或者一个指定的节点来实现。采用指向NULL的方式较为简单，而且还可以节省一个节点空间。

list_node_t *head;
list_node_t *node1;
list_node_t *node2;
list_node_t *node3;

测试接口

int main(void)
{
??? <<a_linked_list_feination>>

??? <<memory_allocation>>

??? <<linked_data_exp>>

??? <<link_all_nodes>>

??? <<set_linked_list_head>>

??? return 0;
}

节点的存储空间分配

node1 = malloc(sizeof(list_node_t));
node2 = malloc(sizeof(list_node_t));
node3 = malloc(sizeof(list_node_t));

数据更新示例

node1->data = 1U;
node2->data = 2U;
node3->data = 3U;

设置链表head

head = node1;

所需要的头文件

#include <stdlib.h>
#include <stdint.h>

节点链接

node1->p_next_node = node2;
node2->p_next_node = node3;
node3->p_next_node = NULL;

测试代码构建

<<included_files>>
<<node_struct_type_defination>>
<<test_code_main>>

运行情况

以上是测试运行的效果，可以看得出来存储指向之间的关系。

小结

这一次只是进行了一个链表构建的梳理，没有对链表的操作进行展开性的阐述与尝试。链表的数据结构以及处理方式可以在很多高级的算法中得到应用，而嵌入式中很多通信机制的处理以及任务调度等实现的一些基本的方法也是链表。但是，在复杂的应用中用到更多的可能是双向链表。不过用到的基本操作不外乎还是指针的处理操作，只是在数据处理中会增加更复杂的处理要求。

当我们看到链表的应用的时候，通常与与内存的动态分配以及释放结合到一起的。为什么这样做呢？或者是，直接在链表中加入一个静态分配的节点对象是否可以呢？从基本的处理操作上看显然是可以的，但是这种使用方式会带来一些风险。比如说，一个链表提供了一个数据处理的缓冲区，然而里面出现了来源于同一数据源的两份或者多份数据的时候，动态的存储分配可以很容易处理掉。然而静态的处理可能会丢失数据甚至导致链表节点指向的紊乱。如果考虑链接静态的处理对象的时候，最好还是增加一些节点是否已经存在等检查手段。