前言

在編程中，鏈表是一種常見的數據結構，用于存儲和組織數據。傳統的鏈表結構包含節點和數據域，而無數據域雙向鏈表則專注于節點的連接關系，不存儲額外的數據。

在有數據域的鏈表中，每個節點除了指針外，還包含一個數據域，用于存儲實際數據。而在無數據域的鏈表中，節點僅包含指針，用于構建節點之間的連接關系，實際數據則存儲在與節點關聯的其他數據結構中。

下面我們將比較這兩種鏈表的特點，并重點介紹無數據域的鏈表的實現。

有數據域鏈表 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 宏來方便地獲取結構體中成員的偏移量。

結語

無數據域雙向鏈表是一種輕量級的鏈表設計，通過精簡的節點結構和高效的指針操作，可以在特定的場景下提高程序的性能和效率。