共计 2565 个字符，预计需要花费 7 分钟才能阅读完成。
概念
为了性能思考，嵌入式零碎个别应用 C 语言进行开发，因为 C 语言规范库没有封装链表，所以嵌入式零碎个别本人设计和实现链表这种数据结构。单链表是链表中的一种，本文形容 OpenAtom OpenHarmony（以下简称“OpenHarmony”）中 HDF 软件模块本人定义的单链表，并学习其设计和实现办法。其中蕴含一些技巧，能够进步读者的软件开发能力。
单链表定义
在 OpenHarmony 的 HDF 软件模块中，单链表定义在 hdf_slist.h 中。
struct HdfSListNode {struct HdfSListNode *next; // next element in list, or NULL};如上图所述，每个节点都是 HdfSListNode，上图共有 5 个节点，每个节点外部有一个 next 成员，其值为下一个节点在内存中的地址。因为能够通过这个地址找到下一个节点，所以在图外面用红色右箭头来形容这个关系。整体来看，从 1 号节点能够通过 next 成员顺次找到前面 4 个节点，从图形看，就是一个逻辑上的链关系，咱们把这种构造称为链表。
独自看 5 号节点，5 号节点没有下一个节点，所以设计上是须要给一个特定的值来示意，实现上个别把 5 号节点的 next 成员填成 0 值，表明其为最开端的节点。
接下来咱们看上面这个数据结构：
struct HdfSList {struct HdfSListNode *root;};其示意图如下：
如上图所示，圆角矩形示意的是 HdfSList，其 root 成员记录了链表中某节点的地址，为了拜访整个链表，须要将 root 成员的值设置成第 1 个节点的地址。因为单链表只反对往一个方向查找，不反对往回查找，如下面的谬误范例。如果 root 记录的是第二个节点地址，则第一个节点变得不可拜访。
迭代器简介
迭代器是随同汇合概念产生的，意思是顺次拜访汇合中的每一个元素，迭代器提供拜访这些元素的办法。对于单链表而言，链表中的每一个节点都是一个元素，所有的节点组成汇合。所以能够通过迭代器来拜访链表中的元素。
迭代器须要提供的根本能力以及操作范式是：
初始化迭代器
反复判断(汇合中还有未被拜访的元素)
获取下一个元素的拜访办法
读写下一个元素(也可能是删除这个元素)
完结上述范式展现了迭代器的用法，通过迭代器，遍历元素变得简略间接 (将遍历算法封装在迭代器中)，不必每次迭代都思考数据结构细节(数据结构品种繁多，单链表只是其中之一)。
对于本文形容的单链表，其封装了上面 3 个函数来反对迭代算法。这 3 个函数别离示意迭代器对象的初始化；汇合中是否还有元素没有参加迭代；取出汇合中下一个能够参加迭代的元素。
/* * @brief initialize iterator * * @param[in] iterator the point of iterator. * @param[in] list the point of operation list. * * @return None */
void HdfSListIteratorInit(struct HdfSListIterator *iterator, struct HdfSList *list);
/* * @brief check whether list has next node. * * @param[in] iterator the point of iterator. * * @return the result of check next. */
bool HdfSListIteratorHasNext(struct HdfSListIterator *iterator);
/* * @brief get next link in the list and move iterator to next. * * @param[in] iterator the point of iterator. * * @return point to next element of it. */
struct HdfSListNode *HdfSListIteratorNext(struct HdfSListIterator *iterator);
迭代器实现思考
对于本文所形容的单链表迭代器。直观上看，除了第一个节点，其它节点都能够通过 next 拜访到，第一个节点通过 root 拜访到。那实际上会不会就是这么简略呢？其实不然，因为须要思考到节点删除的因素。如下图，在链表迭代过程中，如果删除了以后节点，那么怎么找到下一个节点呢？
如上图所示，当在遍历过程中删除了 curr 节点时，那么通过它找到下一个节点是不可能了。所以这个时候咱们必须借助操作 curr 之前还在链表上的上一个节点，即上图的 prev 节点，通过其 next 成员，找到须要迭代解决的下一个节点。所以，迭代过程中须要记录 prev、curr 这 2 个节点的地位信息。迭代过程理论就是调整 prev 和 curr 的过程，对于不删除的状况，prev 和 curr 顺次向后挪动，删除操作时，只挪动 curr。
另外，对于第 1 个节点的状况须要非凡解决，所以须要一个额定的信息来示意是不是迭代第 1 个元素，因为本文形容的迭代器对象含有 3 个信息。如下代码所示：
struct HdfSListIterator {
int stepOnNext; // 是否行将开始遍历第二个以及之后的元素
struct HdfSListNode *prev; // points to the item before the current one 以后被操作元素的前一个元素
struct HdfSListNode *curr; // points to the current item (to detect item removal) 以后被操作的元素，可能刚操作完，被移除链表
};上述代码中 prev 和 curr 的作用曾经在后面详细描述，而 stepOnNext 的意思就是是否曾经开始取第二个元素。行将第一个元素的获取算法与第二个元素离开。
论断
在嵌入式开发中，在学习数据结构课程中，在进行 OpenHarmony 我的项目开发中，单链表都是很重要的，而本文只是其中一个软件模块的单链表实现。通过对单链表的实现的图示剖析，特地是迭代器习用法的剖析，置信读者对单链表以及迭代器的意识都会进一步晋升，更详尽的代码剖析和浏览留给读者本人进行，请参考如下代码文件：
https://gitee.com/openharmony…
https://gitee.com/openharmony…
