了解更多开源请访问：开源基础软件社区https://ost.51cto.comConceptforInterms就性能而言，嵌入式系统一般都是用C语言开发的。由于C语言标准库没有封装链表，所以嵌入式系统一般都是自己设计实现链表的数据结构。单链表是链表的一种。本文介绍OpenAtomOpenHarmony（以下简称“OpenHarmony”）中HDF软件模块定义的单向链表，并学习其设计和实现方法。它包含一些可以提高读者软件开发能力的技巧。单向链表定义在OpenHarmony的HDF软件模块中，单向链表定义在hdf_slist.h中。结构HdfSListNode*下一个;//列表中的下一个元素，或者为NULL};上面说了，每个节点都是HdfSListNode，上图中有5个节点，每个节点里面都有一个next成员，其值为内存中的下一个节点地址。由于可以通过这个地址找到下一个节点，所以图中用红色右箭头来描述这种关系。总体来说，从节点1开始，通过nextmember可以依次找到下面四个节点。从图中看，是一个逻辑链式关系。我们称这种结构为链表。单看节点5，节点5没有下一个节点，所以在设计中需要给出一个具体的值来表示。实际中，节点5的下一个成员一般填0值，表示是最后一个节点。接下来我们看一下下面的数据结构：structHdfSList{structHdfSListNode*root;};示意图如下：如上图所示，圆角矩形代表HdfSList，其根成员记录链表中某个节点的地址。为了访问整个链表，需要将根成员的值设置为第一个节点的地址。因为单向链表只支持单向查找，不支持反向查找，比如上面的错误例子。如果根记录是第二个节点的地址，则第一个节点变得不可访问。迭代器简介迭代器是用集合的概念产生的，意思是依次访问集合中的每一个元素，迭代器提供了访问这些元素的方法。对于单向链表，链表中的每个节点都是一个元素，所有节点构成一个集合。所以链表中的元素可以通过迭代器访问。迭代器需要提供的基本能力和操作范式是：反复判断（集合中还有未访问的元素）获取下一个元素的访问方式读写下一个元素（或者删除这个元素）结束迭代以上范式迭代器的用法，通过迭代器，遍历元素变得简单直接（将遍历算法封装在迭代器中），而无需考虑每次迭代的数据结构细节（数据结构有很多种，还有单链表只是其中之一）。对于本文介绍的单向链表，它封装了以下三个函数来支持迭代算法。这三个函数代表迭代器对象的初始化；集合中是否有没有参与迭代的元素；取出集合中下一个可以参与迭代的元素。voidHdfSListIteratorInit(structHdfSListIterator*iterator,structHdfSList*list);/**@brief检查列表是否有下一个节点。**@param[in]iterator迭代器的指向。**@return接下来检查的结果。*/boolHdfSListIteratorHasNext(structHdfSListIterator*iterator);/**@brief获取列表中的下一个链接并将迭代器移动到下一个。**@param[in]iterator迭代器的指向。**@return指向它的下一个元素。*/structHdfSListNode*HdfSListIteratorNext(structHdfSListIterator*iterator);迭代器实现考虑本文中描述的单链表迭代器。直观上，除了第一个节点，其他节点都可以通过next访问，第一个节点通过root访问。真的有那么简单吗？其实不是这样的，因为需要考虑节点删除的因素。如下图所示，在链表的迭代过程中，如果删除了当前节点，如何找到下一个节点呢？如上图所示，遍历时删除curr节点时，无法通过它找到下一个节点。所以这时候我们就必须使用操作curr之前链表上的previous节点，也就是上图中的prev节点，通过它的next成员找到下一个需要迭代处理的节点。因此在迭代过程中需要记录prev和curr这两个节点的位置信息。迭代的过程其实就是调整prev和curr的过程。对于不删除的情况，prev和curr依次向后移动。删除时，只移动curr。此外，第一个节点的情况需要特殊处理，所以需要额外的信息来指示是否迭代第一个元素，因为本文描述的迭代器对象包含三个信息。如下代码所示：intstepOnNext;//是否要开始遍历第二个及后续元素？/指向当前项（检测项移除）当前操作的元素可能刚操作完就从链表中移除};上面代码中prev和curr的作用上面已经详细介绍过了，stepOnNext的意思就是是否已经开始取第二个元素。即，第一个元素的获取算法与第二个元素的获取算法是分开的。结束语单链表在嵌入式开发、学习数据结构课程、开发OpenHarmony项目中都非常重要，但本文只是其中一个软件模块的单链表实现。通过对单链表实现的图解分析，特别是对迭代器的惯用用法的分析，相信读者对单链表和迭代器的理解会进一步提高。了解更多开源知识，请访问：开源基础软件社区https://ost.51cto.com。
