C语言中linklist如何实现高效操作？-C语言-盈思创科技

什么是链表？

链表是一种线性数据结构，但它与数组不同，链表中的元素在内存中不是连续存储的。

（图片来源网络，侵删）

想象一下一列火车：

数组：就像一节节固定连接好的车厢，车厢的编号是连续的（0, 1, 2...），你不能轻易地在中间插入或删除一节车厢，因为这需要移动后面所有的车厢。
链表：就像一列每节车厢都带有一个挂钩的火车，每节车厢（我们称之为节点）不仅装载了货物（数据），还连着下一节车厢的挂钩（指针），你可以轻松地断开任意两个车厢之间的连接，并在中间插入新的车厢，而不影响其他车厢。

核心特点：

动态大小：链表的大小可以在运行时动态地增加或减少。
非连续存储：节点分散在内存的任意位置，通过指针连接。
高效的插入/删除：在已知位置插入或删除一个节点的时间复杂度是 O(1)，非常高效，但查找一个节点需要 O(n) 的时间。

链表的基本组成

链表由一系列节点组成，每个节点包含两部分：

数据域：存储实际的数据，可以是 int、float、char，甚至是复杂的结构体。
指针域：存储指向下一个节点的内存地址，这是链表的“灵魂”，它将所有节点串联起来。

对于单向链表,最后一个节点的指针域指向 NULL，表示链表的结束。

（图片来源网络，侵删）

节点结构体定义（C语言）：

// 定义一个数据为整型的节点
typedef struct Node {
    int data;             // 数据域
    struct Node* next;    // 指针域，指向下一个同类型的节点
} Node;

注意：在 C 语言中，struct Node* next; 必须写成 struct Node*，因为此时 Node 这个别名（typedef）还没有完全定义完成，而在 C++ 中，可以直接写 Node* next;。

链表的类型

最常见的链表类型有：

单向链表
（图片来源网络，侵删）
- 节点只有一个 next 指针，只能从头到尾遍历。
- Head -> Node1 -> Node2 -> ... -> NULL
双向链表
- 节点有两个指针：next 和 prev（previous），可以从前向后或从后向前遍历。
- Head <-> Node1 <-> Node2 <-> ... <-> NULL
循环链表
- 单向或双向链表的最后一个节点不指向 NULL，而是指向头节点，形成一个环。
- 循环单向链表：Head -> Node1 -> Node2 -> ... -> Head
- 循环双向链表：Head <-> Node1 <-> Node2 <-> ... <-> Head

我们这里重点讲解最基础的单向链表。

单向链表的完整实现

下面是一个完整的、可运行的 C 语言程序，展示了如何创建、遍历、插入和删除单向链表。

#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 1. 定义节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 函数声明
void printList(Node* head);
Node* insertAtBeginning(Node* head, int data);
Node* insertAtEnd(Node* head, int data);
Node* deleteNode(Node* head, int key);
void freeList(Node* head);
int main() {
    Node* head = NULL; // 初始化一个空链表，头指针为 NULL
    // 2. 在链表头部插入节点
    printf("在头部插入 10, 20, 30:\n");
    head = insertAtBeginning(head, 10);
    head = insertAtBeginning(head, 20);
    head = insertAtBeginning(head, 30);
    printList(head); // 输出: 30 -> 20 -> 10 -> NULL
    // 3. 在链表尾部插入节点
    printf("\n在尾部插入 40, 50:\n");
    head = insertAtEnd(head, 40);
    head = insertAtEnd(head, 50);
    printList(head); // 输出: 30 -> 20 -> 10 -> 40 -> 50 -> NULL
    // 4. 删除一个节点
    printf("\n删除值为 10 的节点:\n");
    head = deleteNode(head, 10);
    printList(head); // 输出: 30 -> 20 -> 40 -> 50 -> NULL
    // 5. 释放整个链表占用的内存
    printf("\n释放链表...\n");
    freeList(head);
    head = NULL; // 防止悬垂指针
    printList(head); // 输出: (空)
    return 0;
}
// 打印链表
void printList(Node* head) {
    if (head == NULL) {
        printf("(空链表)\n");
        return;
    }
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
// 在链表头部插入一个新节点
// 时间复杂度: O(1)
Node* insertAtBeginning(Node* head, int data) {
    // 1. 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        return head;
    }
    newNode->data = data;
    newNode->next = NULL;
    // 2. 将新节点的 next 指向原来的头节点
    newNode->next = head;
    // 3. 将头指针指向新节点
    head = newNode;
    return head;
}
// 在链表尾部插入一个新节点
// 时间复杂度: O(n)
Node* insertAtEnd(Node* head, int data) {
    // 1. 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        return head;
    }
    newNode->data = data;
    newNode->next = NULL;
    // 2. 如果链表为空，新节点就是头节点
    if (head == NULL) {
        head = newNode;
        return head;
    }
    // 3. 遍历链表，找到最后一个节点
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    // 4. 将最后一个节点的 next 指向新节点
    current->next = newNode;
    return head;
}
// 删除第一个值为 key 的节点
// 时间复杂度: O(n)
Node* deleteNode(Node* head, int key) {
    Node* current = head;
    Node* prev = NULL;
    // 情况1: 要删除的节点是头节点
    if (current != NULL && current->data == key) {
        head = current->next; // 头指针后移
        free(current);        // 释放旧头节点的内存
        return head;
    }
    // 情况2: 遍历链表，寻找要删除的节点
    while (current != NULL && current->data != key) {
        prev = current;
        current = current->next;
    }
    // 情况3: 如果没找到 key
    if (current == NULL) {
        printf("未找到值为 %d 的节点，\n", key);
        return head;
    }
    // 情况4: 找到了，prev->next 指向 current->next，跳过 current
    prev->next = current->next;
    free(current); // 释放内存
    return head;
}
// 释放整个链表的内存
void freeList(Node* head) {
    Node* current = head;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next; // 先保存下一个节点的地址
        free(current);            // 释放当前节点
        current = nextNode;       // 移动到下一个节点
    }
}

核心操作解析

操作	描述	时间复杂度	备注
创建节点	使用 `malloc` 在堆上分配内存，并初始化数据域和指针域。	O(1)	忘记 `malloc` 会导致无法创建节点。
遍历	从 `head` 开始，使用一个临时指针（如 `current`），不断 `current = current->next` 直到 `NULL`。	O(n)	最基本的操作。
头部插入	创建新节点，使其 `next` 指向当前 `head`，然后更新 `head` 为新节点。	O(1)	链表最大的优势之一，非常快。
尾部插入	需要先遍历到链表末尾，然后将最后一个节点的 `next` 指向新节点。	O(n)	因为需要遍历，所以比头部插入慢。
指定位置插入	需要先找到插入位置的前一个节点，然后修改其 `next` 指针。	O(n)	查找位置是耗时的部分。
删除节点	需要找到要删除的节点及其前一个节点，修改前一个节点的 `next` 指针以“绕过”要删除的节点，`free` 掉它。	O(n)	找到节点是耗时的部分。
头部删除	直接将 `head` 指向 `head->next`，并 `free` 原来的 `head`。	O(1)	和头部插入一样高效。
内存释放	必须遍历整个链表，并对每个节点调用 `free`。	O(n)	极其重要！否则会造成内存泄漏。

链表 vs. 数组

特性	链表	数组
内存分配	动态，非连续	静态或动态，连续
大小	动态可变	创建后大小固定（C语言中）
插入/删除	在已知位置很快 (O(1))	很慢 (O(n))，需要移动元素
随机访问	慢 (O(n))，必须从头遍历	极快 (O(1))，可通过 `arr[index]` 直接访问
内存占用	每个节点都需要额外的空间存储指针	无额外开销
缓存性能	较差，节点分散	较好，数据连续，CPU缓存友好

如何选择？

如果你需要频繁地在序列中间插入和删除元素,且不关心随机访问速度，选择链表。
如果你需要频繁地通过索引访问元素,或者元素数量基本固定，选择数组。

常见面试问题与陷阱

如何找到链表的中间节点？

快慢指针法：设置两个指针 slow 和 fast，都从头开始。slow 每次走一步，fast 每次走两步，当 fast 到达链表末尾时，slow 正好在中间。

代码思路:

Node* findMiddle(Node* head) {
    if (head == NULL) return NULL;
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow; // slow 指向中间节点
}

如何判断链表是否有环？

同样是快慢指针法：如果链表有环，fast 指针最终会追上 slow 指针，如果没有环，fast 会先到达 NULL。

代码思路:

int hasCycle(Node* head) {
    if (head == NULL) return 0;
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return 1; // 有环
        }
    }
    return 0; // 无环
}

反转一个链表？

需要三个指针：prev, current, next，遍历链表，不断将 current->next 指向 prev。

代码思路:

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    while (current != NULL) {
        Node* nextNode = current->next; // 保存下一个节点
        current->next = prev;           // 反转指针
        prev = current;                  // prev 前移
        current = nextNode;              // current 前移
    }
    return prev; // prev 成为新的头节点
}

最大的陷阱：内存泄漏
- 在 C 语言中，所有用 malloc 或 calloc 分配的内存，都必须用 free 释放，如果一个程序长时间运行，不断地创建链表节点而不释放，最终会耗尽系统内存，导致程序崩溃。freeList 函数是链表操作的标配。

希望这份详细的解释能帮助你完全理解 C 语言中的链表！

C语言中linklist如何实现高效操作？

什么是链表？

链表的基本组成

链表的类型

单向链表的完整实现

核心操作解析

链表 vs. 数组

常见面试问题与陷阱

相关文章

目录[+]