前言

在编程中，链表是一种常见的数据结构，用于存储和组织数据。传统的链表结构包含节点和数据域，而无数据域双向链表则专注于节点的连接关系，不存储额外的数据。

在有数据域的链表中，每个节点除了指针外，还包含一个数据域，用于存储实际数据。而在无数据域的链表中，节点仅包含指针，用于构建节点之间的连接关系，实际数据则存储在与节点关联的其他数据结构中。

下面我们将比较这两种链表的特点，并重点介绍无数据域的链表的实现。

有数据域链表 vs 无数据域双向链表

节点结构

有数据域链表：节点结构包含数据域和指向下一个节点的指针。
无数据域双向链表：节点结构仅包含指向前一个节点和后一个节点的指针。

内存消耗

有数据域链表：每个节点需要额外的空间来存储数据。
无数据域双向链表：节点本身不存储数据，节省了额外的空间。

访问数据

有数据域链表：可以直接从节点中访问数据域。
无数据域双向链表：需要通过其他数据结构与节点关联，才能访问数据。

应用场景

有数据域链表：适用于需要存储实际数据的场景，如链表排序、数据存储等。
无数据域双向链表：适用于只需要节点连接关系而不需要额外数据的场景，如资源管理、算法实现等。

代码比较

// 有数据域链表节点结构体
struct NodeWithData {
    int data;   // 数据域为int类型
    struct NodeWithData* prev;
    struct NodeWithData* next;
};

// 无数据域链表节点结构体
struct NodeWithoutData {
    struct NodeWithoutData* prev;
    struct NodeWithoutData* next;
};

offsetof

而实现无数据域链表，如何去访问链表元素内容则需要使用一个最为关键的宏offsetof。

offsetof 是 C 标准库中的一个宏，用于计算结构体中成员的偏移量。它的定义在头文件 stddef.h 中，使用时需要包含该头文件。

offsetof 宏接受两个参数：结构体类型和成员名，返回成员在结构体中的偏移量（以字节为单位）。

#define offsetof(type, member) ((size_t)&(((type *)0)->member))

使用 offsetof 可以方便地获取结构体中成员的偏移量，这在一些底层编程和数据结构实现中非常有用。

代码实现

下面是一个简单的示例，演示了如何使用无数据域双向链表进行插入和访问操作：

#include <stdio.h>
#include <stddef.h> // 包含offsetof宏

// 定义节点结构体
struct Node 
{
    struct Node* prev;
    struct Node* next;
};

// 定义测试结构体
struct Data 
{
    int data;
    struct Node list;
};

// 插入节点到链表尾部
void insert(struct Node* head, struct Node* newNode) 
{
    struct Node* current = head;

    while (current->next != NULL) 
    {
        current = current->next;
    }

    newNode->prev = current;
    newNode->next = NULL;
    current->next = newNode;
}

// 打印链表内容
void printList(struct Node* head) 
{
    printf("List: ");
    struct Node* current = head->next;

    while (current != NULL) 
    {
        // 通过偏移量找到Test结构体的地址
     struct Data* test = (struct Data*)((char*)current - offsetof(struct Data, list));

        printf("%d -> ", test->data);
        current = current->next;
    }

    printf("NULL\n");
}

int main() 
{
    // 创建链表头节点
    struct Node head;
    head.prev = NULL;
    head.next = NULL;

    // 创建并插入节点
    struct Data test1 = {1, {NULL, NULL}};
    struct Data test2 = {2, {NULL, NULL}};
    struct Data test3 = {3, {NULL, NULL}};

    // 插入节点到链表
    insert(&head, &test1.list);
    insert(&head, &test2.list);
    insert(&head, &test3.list);

    // 打印链表内容
    printList(&head);

    return 0;
}

在这个示例中，我们定义了一个包含指向前一个节点和后一个节点的结构体 Node，以及一个包含整数数据和 Node 结构体的结构体 Data。然后实现了插入和打印链表的函数。在打印链表内容的函数中，通过 offsetof 宏获取 Data 结构体中 listNode 成员的偏移量，从而得到节点所在的地址，进而访问节点中存储的数据。

通过这个示例，我们可以看到如何使用无数据域双向链表进行插入和访问操作，以及如何使用 offsetof 宏来方便地获取结构体中成员的偏移量。

结语

无数据域双向链表是一种轻量级的链表设计，通过精简的节点结构和高效的指针操作，可以在特定的场景下提高程序的性能和效率。

如何设计一个高效轻量的链表

前言