點擊上方藍色字體了解更多的嵌入式編程實用技能。
如果你覺得該文章對你有幫助，歡迎點贊+關注
在編程中，鏈表是一種常見的數據結構，用于存儲和組織數據。傳統的鏈表結構包含節點和數據域，而無數據域雙向鏈表則專注于節點的連接關系，不存儲額外的數據。
在有數據域的鏈表中，每個節點除了指針外，還包含一個數據域，用于存儲實際數據。而在無數據域的鏈表中，節點僅包含指針，用于構建節點之間的連接關系，實際數據則存儲在與節點關聯的其他數據結構中。
下面我們將比較這兩種鏈表的特點，并重點介紹無數據域的鏈表的實現。
有數據域鏈表：節點結構包含數據域和指向下一個節點的指針。
無數據域雙向鏈表：節點結構僅包含指向前一個節點和后一個節點的指針。
有數據域鏈表：每個節點需要額外的空間來存儲數據。
無數據域雙向鏈表：節點本身不存儲數據，節省了額外的空間。
有數據域鏈表：可以直接從節點中訪問數據域。
無數據域雙向鏈表：需要通過其他數據結構與節點關聯，才能訪問數據。
有數據域鏈表：適用于需要存儲實際數據的場景，如鏈表排序、數據存儲等。
無數據域雙向鏈表：適用于只需要節點連接關系而不需要額外數據的場景，如資源管理、算法實現等。
//?有數據域鏈表節點結構體
struct?NodeWithData?{
????int?data;???//?數據域為int類型
????struct?NodeWithData*?prev;
????struct?NodeWithData*?next;
};
//?無數據域鏈表節點結構體
struct?NodeWithoutData?{
????struct?NodeWithoutData*?prev;
????struct?NodeWithoutData*?next;
};
而實現無數據域鏈表，如何去訪問鏈表元素內容則需要使用一個最為關鍵的宏offsetof。
offsetof 是 C 標準庫中的一個宏，用于計算結構體中成員的偏移量。它的定義在頭文件 stddef.h 中，使用時需要包含該頭文件。
offsetof 宏接受兩個參數：結構體類型和成員名，返回成員在結構體中的偏移量（以字節為單位）。
define offsetof(type, member) ((size_t)&(((type *)0)->member))使用 offsetof 可以方便地獲取結構體中成員的偏移量，這在一些底層編程和數據結構實現中非常有用。
下面是一個簡單的示例，演示了如何使用無數據域雙向鏈表進行插入和訪問操作：
#include?
#include??//?包含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 宏來方便地獲取結構體中成員的偏移量。
無數據域雙向鏈表是一種輕量級的鏈表設計，通過精簡的節點結構和高效的指針操作，可以在特定的場景下提高程序的性能和效率。
