C语言数据结构之链表实现

链表的基本概念

链表是什么

链表是一种常见的数据结构，与数组不同，它并不在内存中连续存储数据。在链表中，每个数据元素都被封装在一个称为节点（Node）的结构中，这些节点通过指针相互连接，形成一个链式结构。这种结构使得链表在插入和删除操作上具有高效性，尤其适用于需要频繁进行数据插入和删除的场景。

链表与数组的区别

1. 内存存储方式

   • 数组：数组在内存中是连续存储的，这意味着数组中的元素在内存地址上是紧密相连的。例如，定义一个整型数组 int arr[5];，假设 arr[0] 的内存地址为 0x1000，由于每个 int 类型通常占用4个字节，那么 arr[1] 的地址就是 0x1004，arr[2] 的地址是 0x1008，以此类推。
   • 链表：链表的节点在内存中是分散存储的，每个节点通过指针指向下一个节点。节点的内存分配是动态的，它们并不一定在相邻的内存位置。

2. 插入和删除操作

   • 数组：在数组中插入或删除元素时，如果要在数组中间某个位置插入一个元素，需要将该位置之后的所有元素向后移动（插入操作）或向前移动（删除操作）。例如，在一个长度为 n 的数组 a 的第 i 个位置插入元素 x，需要将 a[i] 到 a[n - 1] 的元素依次向后移动一个位置，时间复杂度为 $O(n)$。
   • 链表：链表在插入和删除操作上效率更高。以单链表为例，要在链表的某个节点之后插入一个新节点，只需修改几个指针的指向即可。同样，删除一个节点也只需调整相关指针，时间复杂度为 $O(1)$（前提是已经找到了要操作的节点）。

3. 访问元素方式

   • 数组：可以通过索引直接访问数组中的任意元素，时间复杂度为 $O(1)$。例如，对于数组 arr，可以直接通过 arr[i] 访问第 i 个元素。
   • 链表：链表只能从链表头开始，通过指针逐个遍历节点来访问特定位置的元素。如果要访问链表中的第 n 个节点，需要从头节点开始，依次沿着指针移动 n - 1 次，时间复杂度为 $O(n)$。

单链表的实现

单链表节点的定义

在C语言中，我们使用结构体来定义单链表的节点。每个节点包含两个部分：数据部分和指针部分。数据部分用于存储实际的数据，指针部分用于指向下一个节点。以下是单链表节点的结构体定义示例：

// 定义单链表节点
struct ListNode {
    int data;  // 数据部分，这里假设存储整数
    struct ListNode *next;  // 指针部分，指向下一个节点
};

在上述代码中，struct ListNode 定义了一个单链表节点。data 成员用于存储整数类型的数据，next 成员是一个指向 struct ListNode 类型的指针，用于连接下一个节点。需要注意的是，在定义结构体时，由于 next 指针指向的是自身类型 struct ListNode，所以这里必须使用 struct ListNode 完整名称，而不能直接使用 ListNode（在C语言中，结构体标签在定义完成前是不完整类型，不能直接使用缩写形式）。

创建单链表

1. 创建新节点 首先，我们需要一个函数来创建新的节点。这个函数接受一个数据值作为参数，并返回一个指向新创建节点的指针。

// 创建新节点
struct ListNode* createNode(int value) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

在 createNode 函数中，使用 malloc 函数为新节点分配内存空间。如果内存分配失败，malloc 会返回 NULL，此时函数输出错误信息并返回 NULL。如果分配成功，将传入的值赋给新节点的 data 成员，并将 next 指针初始化为 NULL，表示这是链表的最后一个节点（新创建的节点初始时没有后续节点），最后返回指向新节点的指针。

2. 头插法创建单链表 头插法是指每次将新节点插入到链表的头部。这种方法创建链表的时间复杂度为 $O(n)$，其中 n 是链表中节点的个数。

// 头插法创建单链表
struct ListNode* createListByHeadInsertion(int values[], int size) {
    struct ListNode* head = NULL;
    for (int i = 0; i < size; i++) {
        struct ListNode* newNode = createNode(values[i]);
        if (newNode == NULL) {
            // 处理内存分配失败的情况
            // 这里简单地释放已创建的节点并返回NULL
            while (head != NULL) {
                struct ListNode* temp = head;
                head = head->next;
                free(temp);
            }
            return NULL;
        }
        newNode->next = head;
        head = newNode;
    }
    return head;
}

在 createListByHeadInsertion 函数中，首先初始化链表头指针 head 为 NULL，表示空链表。然后遍历给定的数组 values，对于每个值，调用 createNode 函数创建一个新节点。如果新节点创建失败，释放已创建的链表节点并返回 NULL。如果新节点创建成功，将新节点的 next 指针指向当前的头节点 head，然后更新 head 为新节点，这样新节点就成为了链表的头节点。

3. 尾插法创建单链表 尾插法是将新节点插入到链表的尾部。与头插法不同，尾插法创建的链表节点顺序与输入数据的顺序一致。

// 尾插法创建单链表
struct ListNode* createListByTailInsertion(int values[], int size) {
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    for (int i = 0; i < size; i++) {
        struct ListNode* newNode = createNode(values[i]);
        if (newNode == NULL) {
            // 处理内存分配失败的情况
            // 这里简单地释放已创建的节点并返回NULL
            while (head != NULL) {
                struct ListNode* temp = head;
                head = head->next;
                free(temp);
            }
            return NULL;
        }
        if (tail == NULL) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

在 createListByTailInsertion 函数中，同样先初始化链表头指针 head 和尾指针 tail 为 NULL。遍历数组 values，创建新节点。如果新节点创建失败，释放已创建节点并返回 NULL。如果链表为空（即 tail 为 NULL），则将 head 和 tail 都指向新节点，因为此时新节点既是头节点也是尾节点。如果链表不为空，将当前尾节点的 next 指针指向新节点，然后更新 tail 为新节点，这样新节点就被添加到了链表的尾部。

遍历单链表

遍历单链表是指依次访问链表中的每个节点。这是一个基本操作，常用于打印链表中的数据、查找特定节点等。

// 遍历单链表并打印节点数据
void traverseList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

在 traverseList 函数中，使用一个指针 current 从链表头 head 开始。在 while 循环中，只要 current 不为 NULL，就打印当前节点的数据，并将 current 移动到下一个节点（即 current = current->next）。当 current 为 NULL 时，表示已经到达链表末尾，此时退出循环并打印 NULL 以表示链表结束。

查找单链表中的节点

查找单链表中特定数据值的节点是一个常见操作。我们可以通过遍历链表，逐个比较节点的数据值来实现。

// 在单链表中查找值为target的节点
struct ListNode* searchList(struct ListNode* head, int target) {
    struct ListNode* current = head;
    while (current != NULL) {
        if (current->data == target) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

在 searchList 函数中，同样使用指针 current 从链表头开始遍历。在每次循环中，比较当前节点的 data 成员与目标值 target。如果找到匹配的节点，返回该节点的指针；如果遍历完整个链表都没有找到，返回 NULL。

插入节点到单链表

1. 在指定节点后插入新节点 在单链表的指定节点后插入新节点是一种常见的插入操作。

// 在指定节点后插入新节点
void insertAfter(struct ListNode* prevNode, int value) {
    if (prevNode == NULL) {
        printf("前一个节点不能为NULL\n");
        return;
    }
    struct ListNode* newNode = createNode(value);
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return;
    }
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

在 insertAfter 函数中，首先检查前一个节点 prevNode 是否为 NULL，如果是则输出错误信息并返回。然后调用 createNode 函数创建新节点，如果内存分配失败，输出错误信息并返回。接着，将新节点的 next 指针指向 prevNode 的下一个节点，再将 prevNode 的 next 指针指向新节点，这样就完成了在 prevNode 之后插入新节点的操作。

2. 在单链表头部插入新节点 在单链表头部插入新节点，也就是头插法的一种具体应用。

// 在单链表头部插入新节点
struct ListNode* insertAtHead(struct ListNode* head, int value) {
    struct ListNode* newNode = createNode(value);
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->next = head;
    return newNode;
}

在 insertAtHead 函数中，创建新节点。如果内存分配失败，输出错误信息并返回原链表头 head。然后将新节点的 next 指针指向原链表头 head，最后返回新节点作为新的链表头。

删除单链表中的节点

1. 删除指定节点 删除单链表中的指定节点需要先找到该节点的前一个节点，然后调整指针来绕过要删除的节点。

// 删除单链表中值为target的节点
struct ListNode* deleteNode(struct ListNode* head, int target) {
    struct ListNode* current = head;
    struct ListNode* prev = NULL;
    while (current != NULL && current->data != target) {
        prev = current;
        current = current->next;
    }
    if (current == NULL) {
        printf("未找到值为 %d 的节点\n", target);
        return head;
    }
    if (prev == NULL) {
        head = current->next;
    } else {
        prev->next = current->next;
    }
    free(current);
    return head;
}

在 deleteNode 函数中，使用 current 指针遍历链表，prev 指针记录 current 的前一个节点。在循环中，查找值为 target 的节点。如果遍历完链表都未找到，输出提示信息并返回原链表头 head。如果找到要删除的节点，分两种情况处理：如果要删除的节点是头节点（即 prev 为 NULL），则将链表头更新为 current 的下一个节点；否则，将 prev 的 next 指针指向 current 的下一个节点，从而绕过 current 节点。最后，使用 free 函数释放 current 节点所占用的内存空间，并返回更新后的链表头。

2. 删除单链表的头节点 删除单链表的头节点是一种特殊情况，相对简单一些。

// 删除单链表的头节点
struct ListNode* deleteHead(struct ListNode* head) {
    if (head == NULL) {
        printf("链表为空，无法删除头节点\n");
        return NULL;
    }
    struct ListNode* temp = head;
    head = head->next;
    free(temp);
    return head;
}

在 deleteHead 函数中，首先检查链表是否为空，如果为空输出提示信息并返回 NULL。如果链表不为空，使用一个临时指针 temp 保存头节点，然后将链表头 head 更新为头节点的下一个节点，接着释放 temp 所指向的头节点内存空间，最后返回更新后的链表头。

双链表的实现

双链表节点的定义

双链表与单链表的区别在于，双链表的节点不仅有一个指向下一个节点的指针，还有一个指向前一个节点的指针。这使得双链表在某些操作上更加灵活，例如可以双向遍历链表。以下是双链表节点的结构体定义：

// 定义双链表节点
struct DoublyListNode {
    int data;
    struct DoublyListNode *prev;
    struct DoublyListNode *next;
};

在上述代码中，struct DoublyListNode 定义了一个双链表节点。data 成员用于存储数据，prev 指针指向前一个节点，next 指针指向后一个节点。

创建双链表

1. 创建新的双链表节点 与单链表类似，我们需要一个函数来创建新的双链表节点。

// 创建新的双链表节点
struct DoublyListNode* createDoublyNode(int value) {
    struct DoublyListNode* newNode = (struct DoublyListNode*)malloc(sizeof(struct DoublyListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

在 createDoublyNode 函数中，使用 malloc 分配内存，检查分配是否成功。如果成功，初始化节点的数据、前向指针和后向指针都为 NULL，最后返回新节点的指针。

2. 头插法创建双链表 头插法创建双链表时，每次将新节点插入到链表的头部。

// 头插法创建双链表
struct DoublyListNode* createDoublyListByHeadInsertion(int values[], int size) {
    struct DoublyListNode* head = NULL;
    for (int i = 0; i < size; i++) {
        struct DoublyListNode* newNode = createDoublyNode(values[i]);
        if (newNode == NULL) {
            // 处理内存分配失败的情况
            // 这里简单地释放已创建的节点并返回NULL
            while (head != NULL) {
                struct DoublyListNode* temp = head;
                head = head->next;
                free(temp);
            }
            return NULL;
        }
        if (head != NULL) {
            head->prev = newNode;
            newNode->next = head;
        }
        head = newNode;
    }
    return head;
}

在 createDoublyListByHeadInsertion 函数中，初始化链表头 head 为 NULL。遍历数组 values，创建新节点。如果新节点创建失败，释放已创建节点并返回 NULL。如果链表不为空，将当前头节点的 prev 指针指向新节点，新节点的 next 指针指向当前头节点。最后更新 head 为新节点，使其成为链表的头节点。

3. 尾插法创建双链表 尾插法创建双链表时，将新节点插入到链表的尾部。

// 尾插法创建双链表
struct DoublyListNode* createDoublyListByTailInsertion(int values[], int size) {
    struct DoublyListNode* head = NULL;
    struct DoublyListNode* tail = NULL;
    for (int i = 0; i < size; i++) {
        struct DoublyListNode* newNode = createDoublyNode(values[i]);
        if (newNode == NULL) {
            // 处理内存分配失败的情况
            // 这里简单地释放已创建的节点并返回NULL
            while (head != NULL) {
                struct DoublyListNode* temp = head;
                head = head->next;
                free(temp);
            }
            return NULL;
        }
        if (tail == NULL) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }
    return head;
}

在 createDoublyListByTailInsertion 函数中，初始化链表头 head 和尾 tail 为 NULL。遍历数组创建新节点，若创建失败则释放已创建节点并返回 NULL。如果链表为空，将 head 和 tail 都指向新节点。如果链表不为空，将当前尾节点的 next 指针指向新节点，新节点的 prev 指针指向当前尾节点，然后更新 tail 为新节点。

遍历双链表

双链表可以双向遍历，下面分别给出正向遍历和反向遍历的函数。

1. 正向遍历双链表

// 正向遍历双链表并打印节点数据
void traverseDoublyListForward(struct DoublyListNode* head) {
    struct DoublyListNode* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

在 traverseDoublyListForward 函数中，从链表头 head 开始，通过 next 指针逐个访问节点并打印数据，直到遇到 NULL 指针表示链表结束。

2. 反向遍历双链表

// 反向遍历双链表并打印节点数据
void traverseDoublyListBackward(struct DoublyListNode* tail) {
    struct DoublyListNode* current = tail;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}

在 traverseDoublyListBackward 函数中，从链表尾 tail 开始，通过 prev 指针逐个访问节点并打印数据，直到遇到 NULL 指针表示链表结束。

查找双链表中的节点

查找双链表中特定值的节点与单链表类似，但双链表可以根据具体情况选择从头部还是尾部开始查找，以提高效率。

// 在双链表中查找值为target的节点
struct DoublyListNode* searchDoublyList(struct DoublyListNode* head, int target) {
    struct DoublyListNode* current = head;
    while (current != NULL) {
        if (current->data == target) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

在 searchDoublyList 函数中，从链表头 head 开始遍历，比较每个节点的数据与目标值 target，找到则返回节点指针，未找到则返回 NULL。

插入节点到双链表

1. 在指定节点后插入新节点 在双链表的指定节点后插入新节点需要调整多个指针。

// 在指定节点后插入新节点到双链表
void insertAfterDoubly(struct DoublyListNode* prevNode, int value) {
    if (prevNode == NULL) {
        printf("前一个节点不能为NULL\n");
        return;
    }
    struct DoublyListNode* newNode = createDoublyNode(value);
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return;
    }
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    prevNode->next = newNode;
}

在 insertAfterDoubly 函数中，首先检查前一个节点 prevNode 是否为 NULL。然后创建新节点，若内存分配失败则返回。接着调整指针：新节点的 next 指向 prevNode 的下一个节点，prev 指向 prevNode。如果 prevNode 的下一个节点不为 NULL，则将其 prev 指针指向新节点。最后将 prevNode 的 next 指针指向新节点。

2. 在双链表头部插入新节点

// 在双链表头部插入新节点
struct DoublyListNode* insertAtHeadDoubly(struct DoublyListNode* head, int value) {
    struct DoublyListNode* newNode = createDoublyNode(value);
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    if (head != NULL) {
        head->prev = newNode;
        newNode->next = head;
    }
    return newNode;
}

在 insertAtHeadDoubly 函数中，创建新节点，若内存分配失败则返回原链表头 head。如果链表不为空，调整头节点的 prev 指针和新节点的 next 指针，最后返回新节点作为新的链表头。

删除双链表中的节点

1. 删除指定节点 删除双链表中的指定节点需要调整前后节点的指针。

// 删除双链表中值为target的节点
struct DoublyListNode* deleteDoublyNode(struct DoublyListNode* head, int target) {
    struct DoublyListNode* current = head;
    while (current != NULL && current->data != target) {
        current = current->next;
    }
    if (current == NULL) {
        printf("未找到值为 %d 的节点\n", target);
        return head;
    }
    if (current->prev != NULL) {
        current->prev->next = current->next;
    } else {
        head = current->next;
    }
    if (current->next != NULL) {
        current->next->prev = current->prev;
    }
    free(current);
    return head;
}

在 deleteDoublyNode 函数中，查找值为 target 的节点。若未找到则输出提示并返回原链表头 head。若找到，分情况调整指针：如果当前节点不是头节点，将前一个节点的 next 指针指向当前节点的下一个节点；如果当前节点是头节点，更新链表头为当前节点的下一个节点。同时，如果当前节点不是尾节点，将后一个节点的 prev 指针指向当前节点的前一个节点。最后释放当前节点的内存空间并返回更新后的链表头。

2. 删除双链表的头节点

// 删除双链表的头节点
struct DoublyListNode* deleteHeadDoubly(struct DoublyListNode* head) {
    if (head == NULL) {
        printf("链表为空，无法删除头节点\n");
        return NULL;
    }
    struct DoublyListNode* temp = head;
    head = head->next;
    if (head != NULL) {
        head->prev = NULL;
    }
    free(temp);
    return head;
}

在 deleteHeadDoubly 函数中，检查链表是否为空。若不为空，使用临时指针 temp 保存头节点，更新链表头为头节点的下一个节点。如果新的头节点不为 NULL，将其 prev 指针设为 NULL。最后释放 temp 所指向的头节点内存空间并返回更新后的链表头。

循环链表的实现

循环单链表的实现

1. 循环单链表节点的定义 循环单链表的节点定义与普通单链表相同，但链表的最后一个节点的 next 指针指向链表头节点，形成一个环。

// 定义循环单链表节点
struct CircularListNode {
    int data;
    struct CircularListNode *next;
};

2. 创建循环单链表

// 创建循环单链表
struct CircularListNode* createCircularList(int values[], int size) {
    if (size == 0) {
        return NULL;
    }
    struct CircularListNode* head = createNode(values[0]);
    struct CircularListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = createNode(values[i]);
        current = current->next;
    }
    current->next = head;
    return head;
}

在 createCircularList 函数中，如果数组大小为 0，返回 NULL。否则，创建第一个节点并设为头节点 head。然后遍历数组创建其他节点，并将最后一个节点的 next 指针指向头节点，形成循环链表。

3. 遍历循环单链表 遍历循环单链表需要注意避免陷入无限循环，通常使用一个标志或者记录起始节点来控制循环。

// 遍历循环单链表
void traverseCircularList(struct CircularListNode* head) {
    if (head == NULL) {
        return;
    }
    struct CircularListNode* current = head;
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    printf("%d\n", current->data);
}

在 traverseCircularList 函数中，首先检查链表是否为空。如果不为空，使用 do - while 循环遍历链表，直到再次回到头节点。

循环双链表的实现

1. 循环双链表节点的定义 循环双链表节点与普通双链表节点定义相同，但头节点的 prev 指针指向尾节点，尾节点的 next 指针指向头节点。

// 定义循环双链表节点
struct CircularDoublyListNode {
    int data;
    struct CircularDoublyListNode *prev;
    struct CircularDoublyListNode *next;
};

2. 创建循环双链表

// 创建循环双链表
struct CircularDoublyListNode* createCircularDoublyList(int values[], int size) {
    if (size == 0) {
        return NULL;
    }
    struct CircularDoublyListNode* head = createDoublyNode(values[0]);
    struct CircularDoublyListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = createDoublyNode(values[i]);
        current->next->prev = current;
        current = current->next;
    }
    current->next = head;
    head->prev = current;
    return head;
}

在 createCircularDoublyList 函数中，类似地处理数组大小为 0 的情况。创建第一个节点作为头节点，遍历数组创建其他节点并连接。最后将尾节点与头节点连接起来，形成循环双链表。

3. 遍历循环双链表 循环双链表可以双向遍历，以下是正向遍历的示例。

// 正向遍历循环双链表
void traverseCircularDoublyListForward(struct CircularDoublyListNode* head) {
    if (head == NULL) {
        return;
    }
    struct CircularDoublyListNode* current = head;
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    printf("%d\n", current->data);
}

在 traverseCircularDoublyListForward 函数中，同样检查链表是否为空，然后使用 do - while 循环正向遍历循环双链表，直到再次回到头节点。

链表应用场景

1. 操作系统中的进程调度 在操作系统中，进程调度常使用链表来管理进程。每个进程可以表示为链表中的一个节点，节点包含进程的相关信息，如进程ID、优先级、状态等。通过链表，操作系统可以方便地进行进程的插入（新进程创建）、删除（进程结束）和调度（根据优先级等调整进程顺序）。

2. 哈希表的冲突解决 在哈希表中，当发生哈希冲突（即不同的键值映射到相同的哈希地址）时，链表常被用于解决冲突。在每个哈希桶中维护一个链表，当有新的键值对映射到该桶时，如果桶中已有元素，就将新元素以链表节点的形式插入到链表中。这样可以在不改变哈希表结构的基础上处理冲突。

3. 实现栈和队列 链表可以很方便地实现栈和队列。对于栈，可以使用头插法和头删法来实现栈的压入和弹出操作，链表头就相当于栈顶。对于队列，可以使用尾插法和头删法来实现入队和出队操作，链表头为队头，链表尾为队尾。

通过以上对链表的详细介绍，包括单链表、双链表、循环链表的实现以及链表的应用场景，相信读者对C语言中链表这种数据结构有了更深入的理解和掌握，可以在实际编程中灵活运用链表来解决各种问题。