C如何參考C++中的鏈表功能定義進行實現？

一、前言

鏈表是一種在計算機科學中常用的數據結構，它在C語言中具有重要的作用。本文將介紹鏈表的定義、用途以及如何在C語言中實現鏈表，包括如何參考C++中的鏈表定義進行實現。

二、介紹

鏈表是由節點組成的數據結構，每個節點包含數據和指向下一個節點的指針。相比于數組，鏈表的長度可以動態地增長或縮小，這使得它在處理不確定數量的數據或需要頻繁插入和刪除操作的場景中非常有用。

下面是一個簡單的鏈表節點的定義：

struct?Node?{
????int?data;
????struct?Node*?next;
};

在上述定義中，struct Node 表示節點的結構體，包含一個整數類型的數據字段 data，以及一個指向下一個節點的指針 next。

三、用途

鏈表在很多場景中都有廣泛的應用。以下是一些鏈表常見的用途：

1. 數據存儲和管理：鏈表可以用于存儲和管理各種類型的數據，無論是整數、浮點數、字符串還是自定義的數據結構，鏈表都能靈活地適應。

2. 動態內存分配：鏈表允許動態地分配和釋放內存，這在處理不確定數據量或需要頻繁插入和刪除操作的情況下非常有用。

3. 隊列和棧的實現：鏈表可以用來實現隊列和棧等抽象數據類型，這些數據結構在算法和數據處理中扮演著重要的角色。

4. 圖的表示：鏈表也可以用于表示圖的數據結構，其中每個節點代表一個圖中的頂點，并通過指針連接相鄰的頂點。

四、簡單方式進行實現

在C語言中，鏈表的實現主要依賴于指針和動態內存分配。下面是一個簡單的示例，演示如何創建鏈表并添加節點：

#include?
#include?

struct?Node?{
????int?data;
????struct?Node*?next;
};

void?insertNode(struct?Node**?head,?int?value)?{
????struct?Node*?newNode?=?(struct?Node*)malloc(sizeof(struct?Node));
????newNode->data?=?value;
????newNode->next?=?*head;
????*head?=?newNode;
}

void?displayList(struct?Node*?head)?{
????struct?Node*?current?=?head;
????while?(current?!=?NULL)?{
????????printf("%d?",?current->data);
????????current?=?current->next;
????}
}

int?main()?{
????struct?Node*?head?=?NULL;

????insertNode(&head,?3);
????insertNode(&head,?7);
????insertNode(&head,?9);
????insertNode(&head,?2);

????printf("Linked?list:?");
????displayList(head);

????return?0;
}

五、參考C++鏈表進行實現

首先，我們需要了解C++中的鏈表有哪些功能，以雙向鏈表為例，以下是C++中鏈表常見的功能：

1. 插入節點：可以在鏈表的任意位置插入新的節點，將新節點鏈接到鏈表中。

2. 刪除節點：可以刪除鏈表中的指定節點，調整鏈表的鏈接關系。

3. 遍歷鏈表：可以通過遍歷鏈表，訪問鏈表中的每個節點，并對節點進行操作。

4. 搜索節點：可以按照特定的條件搜索鏈表中符合要求的節點。

5. 反轉鏈表：可以將鏈表中的節點順序顛倒，使鏈表的尾部成為頭部。

6. 獲取鏈表長度：可以計算鏈表中節點的數量，獲取鏈表的長度信息。

7. 獲取鏈表中的數據：可以獲取鏈表中指定節點的數據值，進行讀取或修改操作。

8. 合并鏈表：可以將兩個鏈表合并成一個更長的鏈表，保持節點的順序。

9. 清空鏈表：可以刪除鏈表中的所有節點，使鏈表變為空鏈表。

10. 檢測鏈表是否為空：可以判斷鏈表是否為空鏈表。

11. 迭代器：提供了一種統一的訪問容器中元素的方式

擴展功能：根據實際需求，還可以在鏈表中添加其他自定義的功能，如排序、切分等。

通過上述常見功能，通過C語言實現雙向鏈表大概需要實現以下的功能（之后還會新增）：

typedef?struct?stcotListItem
{
????struct?stcotListItem?*pPrev;
????struct?stcotListItem?*pNext;?
????void?*pData;
}?cotListItem_t;

typedef?struct
{
????uint8_t?nodeBufNum;
????cotListItem_t?*pNodeBuf;
????cotListItem_t?node;?
}?cotList_t;

//?迭代器使用(自動指向下一個)
#define?for_list_each(item,?list)?for?(const?cotListItem_t?*item?=?cotList_Begin(&list);?item?!=?cotList_End(&list);?item?=?cotList_Next(item))

//?反向迭代器使用(自動指向下一個)
#define?for_list_each_r(item,?list)?for?(const?cotListItem_t?*item?=?cotList_rBegin(&list);?item?!=?cotList_rEnd(&list);?item?=?cotList_rNext(item))

//?迭代器使用(需要在循環內調用?item?=?cotList_Next(item)?指向下一個)
#define?for_list(item,?list)?for?(const?cotListItem_t?*item?=?cotList_Begin(&list);?item?!=?cotList_End(&list);)

//?反向迭代器使用(需要在循環內調用?item?=?cotList_rNext(item)?指向下一個)
#define?for_list_r(item,?list)?for?(const?cotListItem_t?*item?=?cotList_rBegin(&list);?item?!=?cotList_rEnd(&list);)

//?獲取迭代器中的數據指針
#define?item_ptr(type,?item)????((type?*)item->pData)

/*
+?迭代器
???+?正向迭代器
??????+?cotList_Begin(cotList_t?*pList);
??????+?cotList_End(cotList_t?*pList);
??????+?cotList_Next(const?cotListItem_t?*pListItem);
???+?反向迭代器
??????+?cotList_rBegin(cotList_t?*pList);
??????+?cotList_rEnd(cotList_t?*pList);
??????+?cotList_rNext(const?cotListItem_t?*pListItem);
+?元素容量
??????+?cotList_Empty(cotList_t?*pList)
??????+?cotList_Size(cotList_t?*pList)
+?元素訪問
??????+?cotList_Front(cotList_t?*pList)
??????+?cotList_Back(cotList_t?*pList)
+?元素插入
???+?動態節點添加（需要在初始化時提供內存）
??????+?cotList_Insert(cotList_t?*pList,?const?void?*pdata)
??????+?cotList_PushFront(cotList_t?*pList,?const?void?*pdata)
??????+?cotList_PushBack(cotList_t?*pList,?const?cotListItem_t?*pListItem,?cotListItem_t?*pNewItem)
???+?靜態節點添加（需要自己定義節點信息后插入）
??????+?cotList_InsertItem(cotList_t?*pList,?const?cotListItem_t?*pListItem,?cotListItem_t?*pNewItem)
+?元素移除
??????+?cotList_Erase(cotList_t?*pList,?const?cotListItem_t?*pListItem)
??????+?cotList_Remove(cotList_t?*pList,?const?void?*pdata)
??????+?cotList_RemoveIf(cotList_t?*pList,?bool?(*pfnCondition)(const?void?*pData))
???+?彈出節點
??????+?cotList_PopFront(cotList_t?*pList)
??????+?cotList_PopBack(cotList_t?*pList)
+?內存交換（鏈表內存交換，減少內存拷貝）
??????+?cotList_Swap
*/

實現：

考慮到MCU小內存的使用場景，在實現中并沒有采用動態內存分配的方式進行擴展，而是提前分配內存，同時采用動態節點添加和靜態節點添加的方式實現鏈表的“元素插入”功能。

動態節點添加：在初始化時提供一片內存給到鏈表添加節點使用（這里只為節點cotListItem_t分配內存，節點中的數據指針pData指向插入元素原本的內存），在添加元素數據的時候使用內存為新的節點分配。

靜態節點添加：自己定義節點，通過通過對應的函數接口插入鏈表中，這個操作不會使用初始化提前分配內存。
好處在于：既可以節約內存開銷（甚至初始化時不分配內存，放棄動態節點添加功能），又可以臨時插入幾個元素數據（不需要定義節點）

注：C++的鏈表中插入元素時鏈表會使用新的內存保存數據，不會使用插入元素原本的內存

迭代器：

迭代器的好處：統一的訪問方式（不論是數組、鏈表還是其他容器，都可以通過迭代器進行遍歷和操作，這簡化了代碼的編寫和維護，使得代碼更加可讀和可復用），隱藏容器的內部結構（迭代器屏蔽了容器的內部結構，將訪問元素的細節隱藏起來，提供了一種抽象的視圖），安全性和穩定性（迭代器提供了安全的方式來遍歷容器，保證了正確的訪問順序和邊界條件的檢查。使用迭代器可以避免出現越界訪問或其他潛在的錯誤），支持多種遍歷方式（正向和反向遍歷）。

{
????cotList_t?list;
????cotListItem_t?nodeBuf[3];
????cotList_Init(&list,?nodeBuf,?3);

????int?data1?=?10;
????int?data2?=?20;
????int?data3?=?30;

????//?推送數據（在鏈表末尾插入數據）
????cotList_PushBack(&list,?&data1);
????cotList_PushBack(&list,?&data2);
????cotList_PushBack(&list,?&data3);

????for_list_each(item,?list)??//?正向遍歷
????{
????????printf("%d\n",?*item_ptr(int,?item));
????}
}

元素操作：

容量

提供相關接口可以知道鏈表中的元素數目。

訪問

如果不采用迭代器的話，可以訪問鏈表的首尾兩個元素節點數據。

插入

動態節點添加（需要在初始化時提供內存）

• cotList_Insert

• cotList_PushFront

• cotList_PushBack

靜態節點添加（需要自己定義節點信息后插入，不會使用初始化時提供的內存）

• cotList_InsertItem

移除

提供了多種元素移除方式，可以通過節點信息刪除（建議通過迭代器進行操作）、數據指針地址（匹配則刪除，鏈表中多個節點的數據指針都指向同一個數據時也會被刪除）、條件刪除（傳入條件的回調函數，凡是滿足條件的節點都會在鏈表中刪除）、從鏈表首尾兩端刪除

交換

兩個鏈表所有的信息都會進行交換，通過交換關鍵內存信息即可完成鏈表的交換，減少內存拷貝的性能開銷或者互斥鎖等頻繁操作的開銷。

在多線程場景下，事先定義兩個同樣內存大的鏈表，在不同的場景下使用，比如線程1僅對鏈表1插入新元素、線程2僅對鏈表2訪問后刪除，在鏈表2元素為空時和鏈表1進行交換，這樣可以保證鏈表2的操作不用考慮多線程問題，只需要對鏈表1考慮多線程問題，從而提高效率。
當然，兩個內存不一致大的鏈表也能完成鏈表的內存交換使用

其他

還有一些功能待實現，比如查找（可以參考“移除”的多種方式實現）、反轉鏈表等

六、下載鏈接

C語言擴展庫（cot）的容器功能函數中有鏈表的完整實現，有興趣的朋友可以參考：

下載鏈接（或點擊“閱讀原文”）：https://gitee.com/const-zpc/cot