C语言LinkNode如何实现链表操作？

LinkNode 本身不是一个 C 语言的关键字或内置类型，而是我们程序员为了构建链表这种数据结构而自定义的一种结构体，它的核心思想是：每个节点不仅存储数据本身，还存储指向下一个节点的“指针”。

什么是链表？

链表是一种线性数据结构，但它与数组不同，链表的元素在内存中不是连续存储的，它由一系列节点组成,每个节点包含两部分：

1. 数据域：存储实际的数据。
2. 指针域：存储指向下一个节点的内存地址。

最后一个节点的指针域通常指向 NULL,表示链表的结束。

一个简单的比喻： 想象一列火车，每节车厢就是一个 LinkNode，车厢里的人和货物就是数据域，而车厢之间的连接钩就是指针域，你通过连接钩可以从一节车厢找到下一节车厢，直到最后一节车厢（没有连接钩了）。

如何定义 LinkNode 结构体？

在 C 语言中，我们使用 struct 关键字来定义 LinkNode。

基本定义

最简单的 LinkNode 只包含一个指向下一个节点的指针。

// 定义一个链表节点
struct LinkNode {
    int data;             // 数据域，这里以存储整数为例
    struct LinkNode* next; // 指针域，指向下一个同类型的节点
};

关键点解释：

• struct LinkNode：这是结构体的类型名。
• int data;：这是数据部分，你可以根据需要修改它的类型，char、float、double，甚至是一个复杂的 struct。
• struct LinkNode* next;：这是指针部分，它存储的是另一个 struct LinkNode 类型的变量的地址。 表示这是一个指针，struct LinkNode 表示它指向的数据类型。next 是我们常用的命名，表示“下一个”。

更通用的定义（使用 typedef）

为了方便使用，我们通常会用 typedef 为 struct LinkNode 创建一个简短的别名，Node。

#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 使用 typedef 定义节点类型，代码会更简洁
typedef struct LinkNode {
    int data;
    struct LinkNode* next;
} Node;
// 现在可以直接使用 Node 来代替 struct LinkNode
Node* head; // 声明一个指向链表头节点的指针

链表的基本操作

链表的核心操作包括创建、插入、删除、遍历和销毁。

a. 创建节点（动态内存分配）

链表的节点是在程序运行时通过动态内存分配创建的，通常使用 malloc 函数。

// 创建一个新节点，并初始化其数据
Node* createNode(int value) {
    // 1. 为新节点分配内存
    Node* newNode = (Node*)malloc(sizeof(Node));
    // 2. 检查内存是否分配成功
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return NULL; // 分配失败，返回空指针
    }
    // 3. 初始化新节点的数据域和指针域
    newNode->data = value;
    newNode->next = NULL; // 新创建的节点默认是链表的最后一个节点
    return newNode;
}

*newNode->data 和 `(newNode).data是等价的**，->` 是通过指针访问结构体成员的简洁语法。

b. 插入节点（头部插入）

在链表的头部插入一个新节点非常高效，时间复杂度为 O(1)。

// 在链表头部插入一个新节点
void insertAtHead(Node** headRef, int value) {
    // 1. 创建新节点
    Node* newNode = createNode(value);
    // 2. 将新节点的 next 指向原来的头节点
    newNode->next = *headRef;
    // 3. 更新头节点指针，使其指向新节点
    // 注意：这里我们传入的是指向 head 指针的指针 (Node**)，
    // 因为 head 本身是指针，我们需要在函数内部修改它。
    *headRef = newNode;
}

c. 遍历链表

从头节点开始，沿着 next 指针依次访问每个节点，直到 next 为 NULL。

// 遍历并打印链表中的所有数据
void printList(Node* head) {
    Node* current = head; // 从头节点开始
    printf("链表内容: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next; // 移动到下一个节点
    }
    printf("NULL\n");
}

d. 释放链表内存

使用 malloc 分配的内存，如果不手动 free，会造成内存泄漏，我们需要遍历整个链表,并释放每个节点的内存。

// 释放整个链表的内存
void freeList(Node** headRef) {
    Node* current = *headRef;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next; // 先保存下一个节点的地址
        free(current);            // 释放当前节点
        current = nextNode;       // 移动到下一个节点
    }
    *headRef = NULL; // 将头指针置为 NULL，防止悬空指针
}

完整示例代码

下面是一个完整的 C 程序，展示了如何定义 LinkNode 并执行上述基本操作。

#include <stdio.h>
#include <stdlib.h>
// 使用 typedef 定义节点类型
typedef struct LinkNode {
    int data;
    struct LinkNode* next;
} Node;
// 函数声明
Node* createNode(int value);
void insertAtHead(Node** headRef, int value);
void printList(Node* head);
void freeList(Node** headRef);
int main() {
    // 初始化一个空链表（头指针为 NULL）
    Node* head = NULL;
    // 在头部插入一些数据
    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtHead(&head, 30);
    insertAtHead(&head, 40);
    // 打印链表
    printList(head); // 预期输出: 40 -> 30 -> 20 -> 10 -> NULL
    // 释放链表内存
    freeList(&head);
    // 再次打印，验证链表是否已清空
    printList(head); // 预期输出: 链表内容: NULL
    return 0;
}
// --- 函数实现 ---
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return NULL;
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}
void insertAtHead(Node** headRef, int value) {
    Node* newNode = createNode(value);
    newNode->next = *headRef;
    *headRef = newNode;
}
void printList(Node* head) {
    Node* current = head;
    printf("链表内容: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
void freeList(Node** headRef) {
    Node* current = *headRef;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    *headRef = NULL;
}

链表的优缺点

优点：

1. 动态大小：可以在运行时动态地增加或减少节点,不像数组有固定大小。
2. 高效的插入和删除：在已知节点位置的情况下，插入和�除操作的时间复杂度为 O(1)，而数组需要移动大量元素，为 O(n)。
3. 内存利用率高：不需要预先分配连续的大块内存。

缺点：

1. 随机访问效率低：访问第 i 个元素必须从头节点开始遍历，时间复杂度为 O(n)，而数组可以通过索引直接访问，为 O(1)。
2. 额外的内存开销：每个节点都需要额外的空间来存储指针。
3. 实现复杂：相比于数组，链表的指针操作（如插入、删除）更容易出错，需要仔细处理边界条件（如空链表、只有一个节点的链表）。

LinkNode 是构建链表的基本模块，理解 LinkNode 的结构（数据 + 指针）以及如何通过指针操作来管理节点，是掌握 C 语言中动态数据结构的关键，从 LinkNode 出发，你可以进一步学习更复杂的链表变体，如双向链表（每个节点有 prev 和 next 指针）和循环链表（尾节点的 next 指向头节点）。