前言

在編程中，鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)和組織數(shù)據(jù)。傳統(tǒng)的鏈表結(jié)構(gòu)包含節(jié)點(diǎn)和數(shù)據(jù)域，而無數(shù)據(jù)域雙向鏈表則專注于節(jié)點(diǎn)的連接關(guān)系，不存儲(chǔ)額外的數(shù)據(jù)。

在有數(shù)據(jù)域的鏈表中，每個(gè)節(jié)點(diǎn)除了指針外，還包含一個(gè)數(shù)據(jù)域，用于存儲(chǔ)實(shí)際數(shù)據(jù)。而在無數(shù)據(jù)域的鏈表中，節(jié)點(diǎn)僅包含指針，用于構(gòu)建節(jié)點(diǎn)之間的連接關(guān)系，實(shí)際數(shù)據(jù)則存儲(chǔ)在與節(jié)點(diǎn)關(guān)聯(lián)的其他數(shù)據(jù)結(jié)構(gòu)中。

下面我們將比較這兩種鏈表的特點(diǎn)，并重點(diǎn)介紹無數(shù)據(jù)域的鏈表的實(shí)現(xiàn)。

有數(shù)據(jù)域鏈表 vs 無數(shù)據(jù)域雙向鏈表

節(jié)點(diǎn)結(jié)構(gòu)

有數(shù)據(jù)域鏈表：節(jié)點(diǎn)結(jié)構(gòu)包含數(shù)據(jù)域和指向下一個(gè)節(jié)點(diǎn)的指針。
無數(shù)據(jù)域雙向鏈表：節(jié)點(diǎn)結(jié)構(gòu)僅包含指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的指針。

內(nèi)存消耗

有數(shù)據(jù)域鏈表：每個(gè)節(jié)點(diǎn)需要額外的空間來存儲(chǔ)數(shù)據(jù)。
無數(shù)據(jù)域雙向鏈表：節(jié)點(diǎn)本身不存儲(chǔ)數(shù)據(jù)，節(jié)省了額外的空間。

訪問數(shù)據(jù)

有數(shù)據(jù)域鏈表：可以直接從節(jié)點(diǎn)中訪問數(shù)據(jù)域。
無數(shù)據(jù)域雙向鏈表：需要通過其他數(shù)據(jù)結(jié)構(gòu)與節(jié)點(diǎn)關(guān)聯(lián)，才能訪問數(shù)據(jù)。

應(yīng)用場景

有數(shù)據(jù)域鏈表：適用于需要存儲(chǔ)實(shí)際數(shù)據(jù)的場景，如鏈表排序、數(shù)據(jù)存儲(chǔ)等。
無數(shù)據(jù)域雙向鏈表：適用于只需要節(jié)點(diǎn)連接關(guān)系而不需要額外數(shù)據(jù)的場景，如資源管理、算法實(shí)現(xiàn)等。

代碼比較

// 有數(shù)據(jù)域鏈表節(jié)點(diǎn)結(jié)構(gòu)體 struct NodeWithData { int data; // 數(shù)據(jù)域?yàn)閕nt類型 struct NodeWithData* prev; struct NodeWithData* next; }; // 無數(shù)據(jù)域鏈表節(jié)點(diǎn)結(jié)構(gòu)體 struct NodeWithoutData { struct NodeWithoutData* prev; struct NodeWithoutData* next; };

offsetof

而實(shí)現(xiàn)無數(shù)據(jù)域鏈表，如何去訪問鏈表元素內(nèi)容則需要使用一個(gè)最為關(guān)鍵的宏offsetof。

offsetof是 C 標(biāo)準(zhǔn)庫中的一個(gè)宏，用于計(jì)算結(jié)構(gòu)體中成員的偏移量。它的定義在頭文件stddef.h中，使用時(shí)需要包含該頭文件。

offsetof宏接受兩個(gè)參數(shù)：結(jié)構(gòu)體類型和成員名，返回成員在結(jié)構(gòu)體中的偏移量（以字節(jié)為單位）。

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

使用 offsetof 可以方便地獲取結(jié)構(gòu)體中成員的偏移量，這在一些底層編程和數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)中非常有用。

代碼實(shí)現(xiàn)

下面是一個(gè)簡單的示例，演示了如何使用無數(shù)據(jù)域雙向鏈表進(jìn)行插入和訪問操作：

#include  #include  // 包含offsetof宏 // 定義節(jié)點(diǎn)結(jié)構(gòu)體 struct Node { struct Node* prev; struct Node* next; }; // 定義測試結(jié)構(gòu)體 struct Data { int data; struct Node list; }; // 插入節(jié)點(diǎn)到鏈表尾部 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;
} // 打印鏈表內(nèi)容 void printList(struct Node* head) { printf("List: "); struct Node* current = head->next; while (current != NULL) 
 { // 通過偏移量找到Test結(jié)構(gòu)體的地址 struct Data* test = (struct Data*)((char*)current - offsetof(struct Data, list)); printf("%d -> ", test->data);
 current = current->next;
 } printf("NULL\n");
} int main() { // 創(chuàng)建鏈表頭節(jié)點(diǎn) struct Node head; head.prev = NULL;
 head.next = NULL; // 創(chuàng)建并插入節(jié)點(diǎn) struct Data test1 = {1, {NULL, NULL}}; struct Data test2 = {2, {NULL, NULL}}; struct Data test3 = {3, {NULL, NULL}}; // 插入節(jié)點(diǎn)到鏈表 insert(&head, &test1.list);
 insert(&head, &test2.list);
 insert(&head, &test3.list); // 打印鏈表內(nèi)容 printList(&head); return 0;
}

在這個(gè)示例中，我們定義了一個(gè)包含指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的結(jié)構(gòu)體 Node，以及一個(gè)包含整數(shù)數(shù)據(jù)和 Node 結(jié)構(gòu)體的結(jié)構(gòu)體 Data。然后實(shí)現(xiàn)了插入和打印鏈表的函數(shù)。在打印鏈表內(nèi)容的函數(shù)中，通過 offsetof 宏獲取 Data 結(jié)構(gòu)體中 listNode 成員的偏移量，從而得到節(jié)點(diǎn)所在的地址，進(jìn)而訪問節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)。

通過這個(gè)示例，我們可以看到如何使用無數(shù)據(jù)域雙向鏈表進(jìn)行插入和訪問操作，以及如何使用 offsetof 宏來方便地獲取結(jié)構(gòu)體中成員的偏移量。