C如何参考C++中的链表功能定义进行实现？

一、前言

链表是一种在计算机科学中常用的数据结构，它在C语言中具有重要的作用。本文将介绍链表的定义、用途以及如何在C语言中实现链表，包括如何参考C++中的链表定义进行实现。

二、介绍

链表是由节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。相比于数组，链表的长度可以动态地增长或缩小，这使得它在处理不确定数量的数据或需要频繁插入和删除操作的场景中非常有用。

下面是一个简单的链表节点的定义：

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

在上述定义中，struct Node 表示节点的结构体，包含一个整数类型的数据字段 data，以及一个指向下一个节点的指针 next。

三、用途

链表在很多场景中都有广泛的应用。以下是一些链表常见的用途：

1. 数据存储和管理：链表可以用于存储和管理各种类型的数据，无论是整数、浮点数、字符串还是自定义的数据结构，链表都能灵活地适应。

2. 动态内存分配：链表允许动态地分配和释放内存，这在处理不确定数据量或需要频繁插入和删除操作的情况下非常有用。

3. 队列和栈的实现：链表可以用来实现队列和栈等抽象数据类型，这些数据结构在算法和数据处理中扮演着重要的角色。

4. 图的表示：链表也可以用于表示图的数据结构，其中每个节点代表一个图中的顶点，并通过指针连接相邻的顶点。

四、简单方式进行实现

在C语言中，链表的实现主要依赖于指针和动态内存分配。下面是一个简单的示例，演示如何创建链表并添加节点：

#include <stdio.h>
#include <stdlib.h>

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