FreeRTOS实战指南 — 3.1 C语言链表

目录

1 单向链表

1.1 单链表的概念

1.2 链表增加头结点的作用

1.3 单链表的实现

2 循环链表

3 双向链表

为什么学习链表？FreeRTOS使用链表来管理任务调度，来维护不同优先级的就绪任务；许多内部数据结构，如任务控制块（TCB）也使用了链表来组织和管理；链表也被用于管理FreeRTOS中的资源，如信号量、消息队列等。使用链表能够灵活地添加、删除和遍历这些数据，从而实现高效的任务管理和调度。

1 单向链表

1.1 单链表的概念

单链表是一种基本的线性数据结构，它由一系列节点组成，每个节点包含两部分数据和指针两部分。数据部分存储节点的值，而指针部分存储指向列表中下一个节点的引用。单链表的特点是只能从首节点开始，通过逐个访问每个节点的指针来遍历整个列表。

图 单链表示意图

节点（Node）：是链表的基本单元，每个节点包含数据域和指针域。数据域存储数据，指针域存储指向下一个节点的指针。节点中有几个容易混淆的概念，下面的辨析可以帮助透彻理解链表。

头节点（Head）：是链表的第一个节点，头节点的指针域指向第一个实际的数据节点，或者在空链表中为NULL。尾节点（Tail）是链表的最后一个节点，其指针域通常指向NULL，表示链表的结束。

首元节点：链表中存储第一个数据元素的节点被称为首元节点。

头指针：头指针是一个特殊的指针，它指向链表的第一个结点的指针，若链表没有投结点，则头指针所指结点为链表的首元结点，如果链表为空，头指针通常被设置为null。

1.2 链表增加头结点的作用

便于首元结点的处理：在没有头结点的链表中，如果要删除首元结点，需要更新头指针指向下一个节点，增加头结点后，对首元结点的插入和删除操作可以和其他节点的操作一样处理，无需特殊逻辑。

（a）没有头结点

（b）有头结点

便于空表和非空表的统一处理：在没有头结点的链表中，需要区分链表是否为空。插入新节点时，如果链表为空（头指针为null），则新节点成为首元结点；如果链表非空，则新节点插入到首元结点之后。增加头结点后，链表的插入和删除操作可以统一处理，无需区分链表是否为空。头结点始终存在，头指针始终指向头结点，这样就避免了对空链表的额外检查。

1.3 单链表的实现

定义链表结构体：单链表通过一系列节点（Node）来存储数据，每个节点不仅包含数据部分，还包含一个指向下一个节点的指针。

// 定义链表节点的结构体
typedef struct ListNode {
    int value;             // 存储数据
    struct ListNode *next; // 指向下一个节点的指针
} ListNode;

实现链表的插入操作：如果链表为空（即头指针 *head 为 NULL），新节点直接成为链表的头节点。如果链表不为空，函数会遍历链表直到找到最后一个节点，然后将新节点链接到链表的末尾。

// 在链表末尾插入一个新的节点
void insertListNode(ListNode **head, int value) 
{
    // 动态分配内存空间给新节点
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    
    // 如果内存分配失败，打印错误信息并返回
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return;
    }

    // 将传入的值赋给新节点赋值
    newNode->value = value;
    newNode->next = NULL;

    // 如果链表的头指针是NULL，说明链表为空，直接将头指针指向新节点
    if (*head == NULL) {
        *head = newNode;
    } else {
        // 如果链表不为空，遍历链表找到最后一个节点
        ListNode *current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        // 将最后一个节点的next指针指向新节点，完成插入
        current->next = newNode;
    }
}

实现链表的删除操作：首先遍历链表，寻找值匹配的节点。如果找到，它会根据该节点是否是头节点来更新头指针或前一个节点的 next 指针，从而从链表中移除该节点。如果链表中没有找到匹配值的节点，则打印一条消息表示未找到。最后，释放被删除节点的内存。

// 用于删除链表中值为指定值的节点
void deleteListNode(ListNode **head, int value) {
    // current用于遍历链表，初始指向头节点
    ListNode *current = *head;
    // prev用于指向当前节点的前一个节点，初始为NULL
    ListNode *prev = NULL;

    // 遍历链表，寻找值为指定值的节点
    while (current != NULL && current->value != value) {
        prev = current;            // 更新prev为当前节点
        current = current->next;  // 移动current到下一个节点
    }

    // 如果current为NULL，说明没有找到值为指定值的节点
    if (current == NULL) {
        printf("Value %d not found in the list\n", value);
        return;
    }

    // 如果prev为NULL，说明要删除的是头节点
    if (prev == NULL) {
        *head = current->next;  // 将头指针指向头节点的下一个节点
    } else {
        // 如果prev不为NULL，说明要删除的不是头节点
        prev->next = current->next;  // 将前一个节点的next指针指向要删除节点的下一个节点
    }

    // 释放被删除节点的内存
    free(current);
}

2 循环链表

循环链表的最后一个节点的指针不是指向 NULL，而是指向链表的第一个节点，形成一个环。这种结构使得链表的遍历可以连续进行，直到再次回到起点。

循环单链表的操作和单链表基本一致，差别仅在于:当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。在单链表中，判别条件为p!=NULL或p->next!=NULL，而循环单链表的判别条件为p != 头指针或p->next != 头指针。

3 双向链表

双向链表每个节点包含数据部分和两个指针，分别指向前一个节点和后一个节点，这种结构可以在链表中向前或向后遍历。

定义双向链表：双向链表每个节点包含一个整数数据和两个指针，分别指向链表中的前一个节点和后一个节点。这种结构使得在链表中向前或向后遍历以及插入和删除节点变得更加高效。

/* 定义双向链表 */
typedef struct DouLinkNode {
    int data;                 // 存储节点数据
    struct DouLinkNode *prev; // 指向前一个节点的指针
    struct DouLinkNode *next; // 指向下一个节点的指针
} DouLinkNode;

插入结点：在双向链表的末尾插入一个新的节点。如果链表为空，新节点成为头节点。如果链表不为空，遍历链表找到最后一个节点，并将新节点链接到末尾，同时更新最后一个节点的 next 指针和新节点的 prev 指针。

// 定义一个函数，用于在双向链表末尾插入一个新的节点
void insertDouLinkNode(DouLinkNode **head, int data)
{
    // 创建一个新的节点，存储给定的数据
    DouLinkNode* newNode = createDouLinkNode(data);
    // 如果内存分配失败，则返回
    if (newNode == NULL) return;

    // 如果链表为空，新节点成为头节点
    if (*head == NULL) {
        *head = newNode;
    } else {
        // 如果链表不为空，找到链表的最后一个节点
        DouLinkNode* current = *head;
        // 遍历链表直到最后一个节点
        while (current->next != NULL) {
            current = current->next;
        }
        // 将新节点链接到链表的末尾
        current->next = newNode;
        // 设置新节点的前驱指针
        newNode->prev = current;
    }
}

删除结点：从双向链表中删除一个具有特定数据值的节点。首先检查头节点是否是要删除的节点，如果是，更新头节点并释放原头节点的内存。如果不是，遍历链表找到要删除的节点，然后根据节点的位置更新前驱和后继节点的指针，并释放要删除节点的内存。

// 定义一个函数，用于从双向链表中删除一个具有特定数据值的节点
void deleteDouLinkNode(DouLinkNode **head, int data) {
    // 初始化当前节点指针为头节点
    DouLinkNode *current = *head, *temp = NULL;
    // 如果链表为空，则不执行任何操作
    if (*head == NULL) return;

    // 如果头节点就是要删除的节点
    if (current->data == data) {
        // 更新头节点为下一个节点
        *head = current->next;
        // 如果新的头节点不为空，更新其前驱指针为NULL
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
        // 释放原头节点的内存
        free(current);
        return;
    }

    // 遍历链表寻找要删除的节点
    while (current != NULL && current->data != data) {
        current = current->next;
    }

    // 如果没有找到要删除的节点，返回
    if (current == NULL) return;
    // 保存要删除节点的前一个节点
    temp = current->prev;
    // 如果要删除的节点后面还有节点，更新后一个节点的前驱指针

    if (current->next != NULL) {
        current->next->prev = temp;
    } else {
        // 如果没有后继节点，说明当前节点是最后一个节点，更新前一个节点的后继指针为NULL
        temp->next = NULL;
    }
    // 释放要删除节点的内存
    free(current);
}