首页 > 编程笔记

C语言链表

C语言中的链表是一种非常重要的数据结构，它可以动态地分配内存空间，实现高效的数据操作。链表由一系列的节点构成，每个节点包含了数据和一个指向下一个节点的指针。在本文中，我们将详细介绍 C语言链表的实现方法，同时提供完整的源代码和运行结果。

链表的基本概念

链表是由若干个节点组成的数据结构，每个节点包含两部分：数据和指向下一个节点的指针。链表中的节点可以是任意类型的数据，通常使用结构体来表示。在 C语言中，定义一个链表节点的结构体如下：
struct ListNode {
    int data;           // 节点数据
    struct ListNode* next;  // 指向下一个节点的指针
};
链表中的第一个节点称为头节点，最后一个节点称为尾节点。头节点和尾节点都没有数据，只是为了方便操作而设置的。在链表中插入一个节点，就是将新节点插入到某个节点之后，删除一个节点，就是将该节点从链表中删除，并将其前一个节点的指针指向该节点的下一个节点。

链表的优点是可以动态地分配内存空间，可以在程序运行时动态地添加或删除节点，而且不会浪费内存空间。但是，链表的缺点是访问节点需要遍历整个链表，效率比较低。

链表的实现

下面是 C语言中链表的实现代码，其中包括链表的创建、插入、删除、遍历等操作。我们使用一个简单的整数链表作为例子，完整的源代码如下： 
#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
struct ListNode {
    int data;
    struct ListNode* next;
};

// 创建链表
struct ListNode* createList() {
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    return head;
}

// 在链表尾部插入一个节点
void insertNode(struct ListNode* head, int data) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->data = data;
    newNode->next = NULL;
    struct ListNode* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
}

// 删除一个节点
void deleteNode(struct ListNode* head, int data) {
    struct ListNode* p = head->next;
    struct ListNode* pre = head;
    while (p != NULL) {
        if (p->data == data) {
            pre->next = p->next;
            free(p);
            return;
        }
        pre = p;
        p = p->next;
    }
}

// 遍历链表
void traverseList(struct ListNode* head) {
    struct ListNode* p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    // 创建链表
    struct ListNode* head = createList();
   
    // 在链表尾部插入节点
    insertNode(head, 1);
    insertNode(head, 2);
    insertNode(head, 3);
    insertNode(head, 4);
    insertNode(head, 5);
   
    // 遍历链表
    traverseList(head);
   
    // 删除节点
    deleteNode(head, 3);
   
    // 遍历链表
    traverseList(head);
   
    return 0;
}
运行结果如下：

1 2 3 4 5
1 2 4 5

在这个例子中，我们首先创建了一个空链表，然后插入了 5 个节点，节点的数据分别为 1、2、3、4 和 5。接着，我们遍历了整个链表，输出了每个节点的数据。然后，我们删除了节点 3，并再次遍历了链表，可以看到节点 3 已经被成功删除。

总结

链表是一种非常重要的数据结构，在 C语言中实现链表也是非常常见的。链表的优点是可以动态地分配内存空间，实现高效的数据操作。

但是，链表的缺点是访问节点需要遍历整个链表，效率比较低。在实际开发中，需要根据实际情况选择使用链表还是其他数据结构。

推荐阅读