链表(C)

本文最后更新于 2024年6月25日 早上

本文主要说明C的链表实现,方式来源于rt-thread,实际好像是来源于linux内核,后者没看过,不清楚咯。这种链表就很科学,通用性很高。也扔到了github仓库中,list文件夹下。

1 双向链表

1.1 与传统链表的不同

传统链表是怎么实现的呢,随便搜索”链表 C”打开个链接都基本相同,定义一个结构体,然后结构体的一个成员是一个指向此结构体的指针。如下:

1
2
3
4
typedef struct sLinkList{
int data;
struct sLinkList *next;
} LinkList;

这种方式就很死板,不同使用场景就需要定义新的结构体,实现新的链表。但接下来这种方式就把链表相关操作抽取了出来,弄成了一个可重复利用的工具。

1.2 使用

首先来看看这种链表的使用方式

  • 定义新的结构体,只需要加入一个链表成员即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    typedef struct text
    {
    int data;
    list_t list;
    int data2;
    }test_t;

    typedef struct text2
    {
    int data;
    list_t list;
    }test_t2;
  • 然后将三个结构体数据连接起来

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //三个示例的节点,链表部分为0则表示未连接状态
    static test_t node1={1,{0,0},1};
    static test_t node2={2,{0,0},2};
    static test_t node3={3,{0,0},3};

    //将三个节点关联起来
    void main()
    {
    list_t head;//新建了一个链表,关联所有加入的节点
    list_init(&head);

    //分别将节点加入
    list_inster_after(&head,&node1.list);
    list_inster_after(&head,&node2.list);
    list_inster_after(&head,&node3.list);
    }

  • 然后就是获取链表中节点的信息

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void test(list_t *head)
    {
    test_t *object;
    printf("len=%d\n",list_len(head));

    list_t *temp=0;
    //轮询链表,第一个节点为头指针所指所以是temp=head->next
    //由于是循环链表,所以最后一个节点指向了头temp!=head
    //切换到下一个节点temp=temp->next
    for(temp=head->next;temp!=head;temp=temp->next)
    {
    //使用此宏可以由结构体的链表成员得到此节点的首地址
    object = LIST_ENTER(temp,test_t,list);
    printf("node:data=%d\n",object->data);
    }
    }

1.3 实现

1.3.1 获取结构体首地址的关键宏

1
2
3
4
5
6
7
/*!
* @brief 成员地址-成员偏移=首地址
* &((type *)0)->member :将0转化为结构体指针,则起始地址为0,然后成员以0为基础进行偏移,所得的便是member成员的偏移量
* (char *)(ptr):控制运算时步长为1字节
*/
#define LIST_ENTER(ptr, type, member) \
((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

不看看别人的代码长长见识,我自己想是肯定弄不出这么巧妙的方式的。
这里通过传入结构体链表成员指针、结构体、结构体链表成员来计算结构节点的首地址。
我们都知道,在实例一个结构体的时候,里面成员存储位置是连续的,例如下列结构体

1
2
3
4
5
6
7
typedef struct tt
{
char a;
char b;
char c;
}tt_t;
tt_t t;

如果t.a的地址是0x407970,那么t.b的地址则是0x407971,&((tt_t *)0)->b的意思则是如果t.a的地址是0,那么t.b的地址是多少呢,很显示就是1了,这样就得到了改成员相较于首地址的偏移量。
所以在实际下列结构体时,我们先知道了一个指针指向了list_t list这个成员,然后也知道了改成员相较于首地址的便宜了,那么直接相减便得到了节点的首地址咯。

1
2
3
4
5
6
typedef struct text
{
int data;
list_t list;
int data2;
}test_t;

1.3.2 初始化链表

这里函数均使用了内联的方式,也就在调用的时候是直接将函数代码复制到相应位置的。
初始化也即将头节点的首尾指针相连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*!
* 环形链表
*/
struct sList
{
struct sList *next;
struct sList *prev;
};
typedef struct sList list_t;

static __inline void list_init(list_t *l)
{
l->next = l->prev = l;
}

1.3.3 插入新节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* @brief 在指向链表节点前插入
* @param l 插入的链表
* @param n 新节点
*/
static __inline void list_inster_after(list_t *l, list_t *n)
{
l->next->prev = n;
n->next = l->next;

l->next = n;
n->prev = l;
}

/**
* @brief 在指向链表节点后插入
* @param l 插入的链表
* @param n 新节点
*/
static __inline void list_insert_before(list_t *l, list_t *n)
{
l->prev->next = n;
n->prev = l->prev;

l->prev = n;
n->next = l;
}

1.3.4 删除新节点

1
2
3
4
5
6
7
8
9
10
11
/**
* @brief 从链表中删除此节点
* @param n 待删除节点.
*/
static __inline void list_remove(list_t *n)
{
n->next->prev = n->prev;
n->prev->next = n->next;

n->next = n->prev = n;
}

1.3.5 获取链表长度

仍然传入链表头,然后轮询,直到最后一个节点指向了链表头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @brief 获取链表长度
* @param l the list to get.
*/
static __inline unsigned int list_len(const list_t *l)
{
unsigned int len = 0;
const list_t *p = l;
while (p->next != l)
{
p = p->next;
len ++;
}

return len;
}

链表(C)
https://blog.kala.love/posts/70fbd584/
作者
久远·卡拉
发布于
2021年4月7日
许可协议