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)))
​