XinYueC 项目 XList 链表家族详解：从单链到双链，再到原子操作

大家好继上一篇介绍XVector动态数组后今天我们来深入探讨XinYueC项目中另一个重量级容器——XList链表家族。这个家族非常庞大包含了单向链表、双向链表以及支持原子操作的无锁单向链表旨在满足各种不同场景下的需求。无论你是需要一个简单的数据序列还是在高并发环境下进行高效的数据操作XList家族都能为你提供强大的支持1. 项目背景与设计哲学XList模块的设计延续了XVector的核心思想泛型、安全、高效、可扩展。它同样基于 C 语言实现并通过虚函数表vtable机制模拟面向对象特性使得不同类型的链表可以共享一套统一的操作接口。XList家族成员XListSLinked: 基础单向链表内存占用小插入/删除操作快。XListDLinked: 双向链表支持双向遍历功能更强大。XListSLinkedAtomic: 基于 CAS (Compare-And-Swap) 的无锁单向链表专为多线程高并发场景设计。XListBase: 所有链表的抽象基类定义了通用接口和迭代器。所有源码均已开源欢迎访问我的 Gitee 仓库https://gitee.com/xin___yue/XinYueC/tree/develop/2. 核心文件与架构XList模块采用分层设计结构清晰文件类型功能描述XListBase.h/.c抽象基类定义所有链表共有的基础结构、虚函数表和通用方法如size,isEmpty。XListBase_iterator.h迭代器提供适用于所有链表的正向迭代器。XListSLinked.h/.c单向链表实现基础单向链表的具体逻辑。XListSLinked_virtual.c虚函数包含XListSLinked的核心操作push_back,pop_front等并初始化其 vtable。XListDLinked.h/.c双向链表实现功能更丰富的双向链表。XListSLinkedAtomic.h/.c原子链表实现基于原子操作的无锁单向链表。3. 快速入门如何使用 XListSLinked 和 XListDLinked3.1 创建与销毁使用方式与XVector非常相似通过宏可以快速创建。#include XListSLinked.h // 或者 #include XListDLinked.h int main() { // 创建一个存储 int 的单向链表 XListSLinked* list XListSLinked_Create(int); // XListDLinked* list XListDLinked_Create(int); // 双向链表 if (list NULL) { return -1; } // ... 使用 list ... // 销毁链表 XListSLinked_delete_base(list); // 或 XListDLinked_delete_base return 0; }3.2 基本操作增删改查链表的核心优势在于高效的头尾操作// 在头部/尾部添加元素 XListSLinked_Push_Front_Base(list, int, 10); XListSLinked_Push_Back_Base(list, int, 20); // 访问头部/尾部元素 int head XListSLinked_Front_Base(list, int); int tail XListSLinked_Back_Base(list, int); // 从头部/尾部移除元素 XListSLinked_pop_front_base(list); XListSLinked_pop_back_base(list); // 注意单向链表的 pop_back 是 O(n) 操作注意对于XListSLinked单向链表pop_back操作需要从头遍历到尾时间复杂度为 O(n)。而XListDLinked双向链表由于有尾指针pop_back是 O(1) 操作。3.3 插入与删除指定位置// 在索引1的位置插入元素30 XListSLinked_insert_base(list, 1, (int){30}); // 删除索引为0的元素 XListSLinked_removeAt_base(list, 0);4. 强大的迭代器系统XList家族继承了XVector优秀的迭代器设计让你可以轻松遍历链表。// 正向遍历单向或双向链表 for_each_iterator(list, XListSLinked, it) { // 或 XListDLinked int* value (int*)XListBase_iterator_data(it); printf(%d , *value); } printf(\n);对于XListDLinked双向链表你还可以使用反向迭代器。5. 高级特性XListSLinkedAtomic 无锁链表这是XList家族中最硬核的成员XListSLinkedAtomic利用 CPU 的原子指令如__atomic_compare_exchange_n实现了无锁Lock-Free的并发安全链表。5.1 为什么需要它在传统的多线程程序中我们通常使用互斥锁mutex来保护共享数据。但在高并发、低延迟的场景下锁竞争会成为性能瓶颈。无锁数据结构通过精心设计的算法避免了锁的使用从而极大地提升了并发性能。5.2 如何使用XListSLinkedAtomic的 API 设计与其他链表保持一致但内部实现完全不同。#include XListSLinkedAtomic.h int main() { XListSLinkedAtomic* atomic_list XListSLinkedAtomic_Create(int); // 在多线程环境中这些操作是线程安全的 XListSLinkedAtomic_Push_Front_Base(atomic_list, int, 100); XListSLinkedAtomic_Push_Back_Base(atomic_list, int, 200); // ... 其他线程可以同时进行 push/pop 操作 ... XListSLinkedAtomic_delete_base(atomic_list); return 0; }重要提示虽然XListSLinkedAtomic的push和pop操作是无锁且线程安全的但像size()这样的聚合操作在无锁环境下很难高效实现因此可能不被支持或效率较低。它的主要应用场景是作为生产者-消费者队列。6. 内存管理与自定义析构和XVector一样XList也支持为存储的复杂数据类型设置自定义的析构函数。typedef struct { char* name; int id; } MyData; void my_data_destructor(void* data) { MyData* d (MyData*)data; free(d-name); } int main() { XListSLinked* list XListSLinked_create(sizeof(MyData)); XContainerSetDataDeinitMethod(list, my_data_destructor); // ... 添加 MyData 对象 ... // 销毁时会自动调用 my_data_destructor 释放每个元素的资源 XListSLinked_delete_base(list); return 0; }总结XList链表家族为 C 语言开发者提供了从基础到高级、从单线程到多线程的完整链表解决方案。日常开发优先选择XListDLinked功能全面使用方便。内存极度敏感可以选择XListSLinked牺牲部分功能换取更小的内存开销。高并发场景XListSLinkedAtomic是你的不二之选它能让你的程序在多核 CPU 上飞驰。希望这篇文章能帮助你更好地掌握XList的使用。如果你对无锁编程或者 C 语言容器设计感兴趣强烈建议阅读源码相信你会有更多收获欢迎大家在评论区交流讨论也别忘了去 Gitee 仓库 点个 Star 支持一下