前言侵入式链表和之前研究的链表有所不同以前普通的链表想要获取到节点的数据只需要拿到指向节点的指针就可以访问结构体内存放的数据但是侵入式链表不同指针也是结构体的成员我们没法通过指针去直接访问节点的数据因为他存放的地址不是结构体的地址我找了不少的资料说什么container_of说是Linux内核实现的。container_of这个玩意网上面的说法其实有一定的误导性我刚开始看以为是类似windows API提供的函数接口直接调着用就行了经过研究我想多了他最多只提供了offsetof内存偏移算法这玩意只是一个宏名还是自己要定义实现的。。。。为什么只能是宏为什么是宏而不是我定义一个函数调着用。这是因为在c/c中是不能将类型作为参数的他是需要传入形参这个说法好像也不是很标准大致这么个意思函数要传入某个类型的变量而宏替换就可以达到。实现#define container_of(ptr, type, member) \ ((type*)((char*)(ptr) - offsetof(type, member)))这一实现是不是很新奇我很少用宏也可能是我孤陋寡闻来一起见识下宏的多行写法。这里的\其实就是上一行没写完拼接一下和下面的等价#define container_of(ptr, type, member) ((type*)((char*)(ptr) - offsetof(type, member)))比如说有以下结构体struct Student { int id; char name[32]; IntrusiveNode by_id; // 按 id 排序的链表 IntrusiveNode by_name; // 按名字排序的链表 }; // 同一个学生可以同时在两个链表里不冲突他的内部包含的节点我们可以看到在物理内存上他是在结构体的最后面我们如果想要通过节点去访问数据就需要做内存偏移拿到结构体的地址64位struct Student { int id; // 4 字节 [0 ~ 3] char name[32]; // 32 字节 [4 ~ 35] // ↑ 到 35 号字节结束36 不是 8 的倍数所以填充对齐 // 填充 // 4 字节 [36 ~ 39] ← 为了对齐补上的 IntrusiveNode by_id; // 16 字节 [40 ~ 55] ← 偏移量 40 IntrusiveNode by_name; // 16 字节 [56 ~ 71] ← 偏移量 56 };结构体地址 节点地址 - 偏移地址使用方法Student stu{100, Tom, {}, {}}; // 拿 by_id 的偏移地址算回去 IntrusiveNode* p1 stu.by_id; // p1 0x...28 (stu 40) Student* s1 container_of(p1, Student, by_id); // → (Student*)( (char*)p1 - offsetof(Student, by_id) ) // → (Student*)( (char*)p1 - 40 ) // 减 40回到 stu 首地址 // 拿 by_name 的偏移地址算回去 IntrusiveNode* p2 stu.by_name; // p2 0x...38 (stu 56) Student* s2 container_of(p2, Student, by_name); // → (Student*)( (char*)p2 - 56 ) // 减 56回到 stu 首地址侵入式链表侵入式链表可以理解为就是一根绳子结构体就是一个带钩子的衣架他有一个哨兵节点不存任何的值链表初始化的时候自己的next指向自己的prev自循环head ───┐ ↑ │ └───────┘ prev ←→ next 自环void InsertBetween(intrusivelist* prev,intrusivelist* next,intrusivelist* newnode){ newnode-next next; newnode-prev prev; next-prevprev-next newnode; }通用插入函数我们的链表设计的每个节点都有两个指针一个指向前面一个指向后面在这里操作和普通链表的差不多原理就是我们要将节点插入到两个节点之间要先断开他们彼此指向的指针然后将新节点和胶水一样将链表链接起来。这个实现在后面的连接环节都会用到。void InsertBetween(intrusivelist* prev,intrusivelist* next,intrusivelist* newnode){ newnode-next next; newnode-prev prev; next-prevprev-next newnode; }头插法这个我刚开始理解偏了以为是插入到哨兵节点的前面实际上正确的理解方式应该是哨兵节点的后面原来头一个接在哨兵节点的节点的前面。理解了这个就很好实现了bool InsertHead(intrusivelist* head,intrusivelist* newnode){ InsertBetween(head,head-next,newnode); return true; }尾插法尾插法同理找到尾节点逻辑上是在head的前面尾节点的后面的位置插入。bool InsertTail(intrusivelist* head,intrusivelist* newnode){ InsertBetween(head-prev,head,newnode); return true; }删除一个节点到删除的环节了这个位置需要格外的注意没有处理好会内存泄漏在链表上的结构体对象是在堆上创建的我们删除一个节点的时候不是删除他内部的节点那么比如结构体有id、姓名之类的参数就直接内存泄漏了我们在处理好前后节点的指针以后需要通过container_of去偏移找到结构体地址释放整个结构体这里是最关键的地方。这个选择删除节点的依据是学生ID前面拿到结构体指针后可以访问结构体的ID一项进行比对bool IntrasiveDeleteOneNode(intrusivelist* node){ node-prev-nextnode-next; node-next-prevnode-prev; student_node* stu container_of(node,student_node,student_node); delete stu; return true; }调用者: [head] [target] (用完就扔了) ↑ 不需要改 函数: 改了前节点和后节点的指针 ✅删除整个链表这个删除逻辑哨兵节点必须是最后删除的有两个临时指针操作一个负责删除当前指针一个负责指向下一个指针因为当前节点释放以后操作删除的指针会悬空需要给他重新赋值。还有一个需要注意的是这回删除的传参是二级指针因为要把哨兵节点也删掉相当于拆楼了bool IntrasiveDeleteAll(intrusivelist** head){ if(!head||!*head){ printf(传入的头节点不存在\n); return false; } printf(开始删除节点\n); intrusivelist* cur (*head)-next; while(cur ! *head){ intrusivelist* next cur-next; student_node* stu container_of(cur, student_node, student_node); delete stu; cur next; } delete *head; *head nullptr; printf(删除完毕\n); return true; }调用者: [head] ← 这个变量必须被置空 ↑ 函数: 必须改到这里 一级指针改不了 → 必须二级指针场景比喻参数删单个节点你从书架上拿一本书扔掉书架位置不用管一级指针删整个链表你把整个书架拆了得告诉别人这里没书架了二级指针剩下的操作基本都是复用上面的逻辑这里就不过多赘述了关于之前实现的普通链表以及侵入式链表功能实现我将他们都做好也测试过了感兴趣的可以自己下载跑着看看免费开源但我不保证平台有没有动手脚注意编码utf-8 with bom不然会报一些奇怪的错误