02 数据结构 ——链表（静态/循环/双向/LINUX内核链表）
四、静态链表
-
静态链表的节点存储在一段连续内存中，通过节点中称为游标的一个正整数来访问后继节点
typedef StaticNode
{
TYPE data; // 数据域
int index; // 游标
}StaticNode;
int main()
{
StaticNode arr[100] = {};
arr[0].data = 1;
arr[0].index = 5;
arr[5].index = 3;
arr[3].index = 8;
arr[8].index = -1;
}
-
在静态链表中进行插入、删除时，只需要修改游标的值即可不需要拷贝内存，也能达到链表的效果
-
但是也牺牲了随机访问节点的功能，而且链表的优点也有缺失。
-
是给没有指针的编程语言提供一种操作单链表的方式。
五、循环链表
-
循环链表的最后一个节点的next不再指向NULL，而是指向头节点。如果是单链表就称为单循环链表
-
好处是能够通过任意节点可以遍历整个链表
六、双向链表（双向循环链表）
-
所谓的双向链表就是链表节点中有两个指针域，一个指向前一个节点，叫做前趋指针（prev），另一个指向后一个节点，称为后继指针（next）
-
因此可以从后往前遍历链表，对于要访问链表后半部的节点的操作效率更高
// 双向链表的节点结构
typedef struct ListNode
{
struct ListNode* prev; // 前趋
TYPE data;
struct ListNode* next; // 后继
}ListNode;
-
在双向链表的基础上，让最后一个节点的next指向头节点，让头节点的prev指向最后一个节点，构成了双向循环链表
七、Linux内核链表
-
在普通的链表中，目前面临无法做到任何类型的数据都可以存储的问题。
-
Linux内核链表是一种通用的双向循环链表，面对通用的问题，Linux内核链表的节点干脆不存储任何数据域，只有指针域，节点只负责串联起每个节点，不负责存储数据。
-
如果要使用Linux内核链表时，把节点放入到数据中。
目的：根据结构体中某个成员的地址，能够计算出所在结构体的首地址，从而用户在设计Linux内核链表的节点时，不需要一定放在在数据的首位成员，增加可用性 // 计算出结构体type的成员mem所在的地址距离第一个成员位置的字节数 #define offsetof(type,mem) \ ((unsigned long)(&(((type*)0)->mem))) // 根据结构成员mem的地址(ptr) 计算出它所在结构(type)变量的首地址 // ptr要计算的某个节点的地址 type是ptr所在结构体名 mem是它的结构成员名 #define node_to_obj(ptr,type,mem) \ ((type*)((char*)ptr - offsetof(type,mem)))
原文地址：https://blog.csdn.net/weixin_65029285/article/details/140504393
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！