深入理解C语言链表：数据结构的基石

在C语言的编程宇宙中，链表就像是一座稳固的基石，支撑着众多复杂程序的构建。它以独特的魅力和强大的功能，在解决各类编程难题时发挥着至关重要的作用。今天，就让我们一同深入探索链表的奥秘。

一、链表初相识

二、链表的结构定义

三、链表的基本操作大揭秘

（一）创建新节点

（二）插入节点

头部插入

尾部插入

（三）删除节点

（四）遍历链表

四、链表的优势与应用场景

（一）优势

（二）应用场景

一、链表初相识

链表是一种线性数据结构，与内存中连续存储数据的数组截然不同，链表的元素在内存中的存储位置是离散的。它由一系列节点（Node）串连而成，每个节点都包含两个关键部分：

数据域：用于存储实际的数据，可以是整数、字符，甚至是复杂的结构体等各种数据类型。

指针域：存储着下一个节点在内存中的地址，通过指针将各个节点按顺序连接起来，形成一条“链”。链表的最后一个节点的指针通常指向NULL，作为链表结束的标志。

二、链表的结构定义

在C语言中，借助结构体（struct）来定义链表节点，示例如下：

c

// 定义链表节点结构

struct Node {

    int data; // 数据域，这里存储整数

    struct Node* next; // 指针域，指向下一个节点

};

在这个定义中， struct Node 代表链表节点的类型。 data 成员用于存放具体的数据（这里设定为 int 类型）； next 是一个指针，指向 struct Node 类型的对象，即下一个链表节点，如此构建起链表的链式结构。

三、链表的基本操作大揭秘

（一）创建新节点

创建新节点是链表操作的基础，每当要向链表添加新元素时，都需先创建一个新节点。

c

// 创建新节点的函数

struct Node* createNode(int value) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    if (newNode == NULL) {

        // 内存分配失败，通常是系统内存不足的情况

        fprintf(stderr, "内存分配失败\n");

        return NULL;

    }

    newNode->data = value;

    newNode->next = NULL;

    return newNode;

}

此函数中，首先使用 malloc 函数为新节点分配内存空间。若内存分配成功，将传入的值赋给新节点的数据域 data ，并将指针域 next 初始化为 NULL ，表示该新节点暂时是链表的最后一个节点。若内存分配失败，打印错误信息并返回 NULL 。

（二）插入节点

插入节点是常用操作，可在链表不同位置插入，常见的有头部插入和尾部插入。

头部插入

c

// 在链表头部插入节点的函数

struct Node* insertAtHead(struct Node* head, int value) {

    struct Node* newNode = createNode(value);

    if (newNode != NULL) {

        newNode->next = head;

        head = newNode;

    }

    return head;

}

头部插入时，先创建新节点 newNode 。然后让新节点的 next 指针指向当前头节点 head ，将新节点连接到原链表头部。最后，更新 head 为新节点，使其成为链表的头节点。

尾部插入

c

// 在链表尾部插入节点的函数

struct Node* insertAtTail(struct Node* head, int value) {

    struct Node* newNode = createNode(value);

    if (newNode == NULL) {

        return head;

    }

    if (head == NULL) {

        head = newNode;

    } else {

        struct Node* current = head;

        while (current->next != NULL) {

            current = current->next;

        }

        current->next = newNode;

    }

    return head;

}

尾部插入时，若链表为空（ head 为 NULL ），直接将新节点赋值给 head ，新节点成为链表唯一节点。若链表不为空，通过循环遍历找到链表最后一个节点（即 current->next 为 NULL 的节点），然后将最后一个节点的 next 指针指向新节点，完成添加。

（三）删除节点

删除节点操作相对复杂，需先找到要删除节点的前一个节点，再修改其指针，绕过要删除的节点。

c

// 删除指定值节点的函数

struct Node* deleteNode(struct Node* head, int value) {

    if (head == NULL) {

        return head;

    }

    if (head->data == value) {

        struct Node* temp = head;

        head = head->next;

        free(temp);

        return head;

    }

    struct Node* current = head;

    while (current->next != NULL && current->next->data != value) {

        current = current->next;

    }

    if (current->next != NULL) {

        struct Node* temp = current->next;

        current->next = current->next->next;

        free(temp);

    }

    return head;

}

首先判断链表是否为空，若为空则直接返回 head 。若头节点数据是要删除的值，用临时指针 temp 保存头节点，更新 head 为头节点的下一个节点，释放 temp 指向的头节点内存，返回新的 head 。若要删除的节点不是头节点，通过循环找到其前一个节点 current 。若找到要删除的节点，用临时指针 temp 保存，将 current 的 next 指针指向要删除节点的下一个节点，绕过该节点，最后释放 temp 指向节点的内存。

（四）遍历链表

遍历链表是访问每个节点数据的过程，通常用循环结构实现。

c

// 遍历链表并打印节点数据的函数

void traverseList(struct Node* head) {

    struct Node* current = head;

    while (current != NULL) {

        printf("%d -> ", current->data);

        current = current->next;

    }

    printf("NULL\n");

}