一、链表是什么？

想象一下寻宝游戏。你手上有一张纸条，上面写着“第一个宝藏在A点”，还附有一条线索：“下一个宝藏的位置写在A点的宝藏盒里”。

你跑到A点，打开盒子，拿到了第一个宝藏，并找到了一张新的纸条，上面写着：“下一个宝藏在B点”。于是你又跑到B点... 直到你打开一个盒子，发现里面的纸条写着“游戏结束”。

这个寻宝游戏就是链表的工作方式：

• 每个宝藏盒 就是一个 节点 (Node)。

• 宝藏 就是节点里存储的 数据 (Data)。

• 指向下一个位置的纸条 就是指向下一个节点的 指针 (Pointer)。

• 你手上的第一张纸条 就是指向链表开头的 头指针 (Head)。

• 写着“游戏结束”的纸条 就是一个 空指针 (NULL)，表示链表的结尾。

与数组不同，链表的“宝藏盒”（节点）在内存中不需要是连续存放的。它们可以散落在内存的任何地方，依靠指针这条“线索”将它们串联起来。

二、构建链表的基石

1、示例

在C语言中，我们用结构体来定义链表的节点。一个最简单的单向链表节点 Node 包含两个部分：

1. 数据域 (Data part)：存放我们想要存储的实际数据，比如一个整数、一个浮点数，甚至是另一个结构体。

2. 指针域 (Pointer part)：一个指向同类型结构体的指针，用于链接到下一个节点。

#include <stdio.h>
#include <stdlib.h> // 为了使用 malloc 和 free

// 1. 定义链表节点结构体
struct Node {
    int data;               // 数据域：我们在这里存一个整数
    struct Node *next;      // 指针域：指向下一个节点的指针
};

struct Node *next; 是最关键的部分。它定义了一个名为 next 的成员，这个成员是一个指针，它指向的类型是 struct Node，也就是它自己。正是这种“自我引用”的结构，使得节点可以一个接一个地串起来。

2、可视化链表结构

假设我们有一个链表存储了 10 -> 20 -> 30：

• 我们有一个 head 指针，指向第一个节点。

• 第一个节点的数据是 10，它的 next 指针指向第二个节点。

• 第二个节点的数据是 20，它的 next 指针指向第三个节点。

• 第三个节点的数据是 30，它的 next 指针是 NULL，表示链表结束。

内存中的样子（示意图）：

head
    |
    V
+-------+------+     +-------+------+     +-------+------+
| data: | next | --> | data: | next | --> | data: | next | --> NULL
|  10   |  * --|-->  |  20   |  * --|-->  |  30   | NULL |
+-------+------+     +-------+------+     +-------+------+

三、一个完整的结构

#include <stdio.h>
#include <stdlib.h>

// 节点定义
struct Node {
    int data;
    struct Node *next;
};

// 函数：创建一个新节点
// 这是我们的“盒子工厂”，生产一个新的、独立的节点
struct Node* createNode(int data) {
    // 1. 申请内存空间
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        exit(1);
    }
    // 2. 初始化节点
    newNode->data = data;  // 放入数据
    newNode->next = NULL;  // 新节点默认不指向任何地方
    return newNode;
}

// 函数：在链表头部插入节点 (最高效的插入方式)
void insertAtBeginning(struct Node** head_ref, int new_data) {
    // 1. 创建新节点
    struct Node* new_node = createNode(new_data);
    
    // 2. 让新节点的 next 指向当前的 head
    new_node->next = *head_ref;
    
    // 3. 更新 head 指针，让它指向新的头部
    *head_ref = new_node;
}

// 函数：在链表尾部插入节点
void insertAtEnd(struct Node** head_ref, int new_data) {
    // 1. 创建新节点
    struct Node* new_node = createNode(new_data);
    
    // 2. 如果链表是空的，新节点就是头节点
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    
    // 3. 否则，遍历到链表的最后一个节点
    struct Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }
    
    // 4. 将最后一个节点的 next 指向新节点
    last->next = new_node;
}

// 函数：删除一个具有特定值的节点
void deleteNode(struct Node** head_ref, int key) {
    struct Node *temp = *head_ref, *prev = NULL;

    // Case 1: 如果要删除的节点是头节点
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next; // 改变头
        free(temp);             // 释放旧的头节点内存
        return;
    }

    // Case 2: 遍历链表查找要删除的节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // 如果没找到这个值的节点
    if (temp == NULL) {
        printf("值为 %d 的节点未找到。\n", key);
        return;
    }

    // Case 3: 找到了节点，断开链接
    prev->next = temp->next;
    free(temp); // 释放内存
}


// 函数：遍历并打印链表
void printList(struct Node* node) {
    printf("链表内容: ");
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

// 函数：释放整个链表的内存
void freeList(struct Node** head_ref) {
    struct Node *current = *head_ref;
    struct Node *next_node;
    while (current != NULL) {
        next_node = current->next; // 先保存下一个节点的地址
        free(current);             // 再释放当前节点
        current = next_node;       // 移动到下一个节点
    }
    *head_ref = NULL; // 将头指针设为NULL，防止野指针
}

// 主函数，演示所有操作
int main() {
    // 初始化一个空链表
    struct Node* head = NULL;

    printf("在尾部插入 10, 20, 30...\n");
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    printList(head); // 链表内容: 10 -> 20 -> 30 -> NULL

    printf("\n在头部插入 5...\n");
    insertAtBeginning(&head, 5);
    printList(head); // 链表内容: 5 -> 10 -> 20 -> 30 -> NULL

    printf("\n删除节点 20...\n");
    deleteNode(&head, 20);
    printList(head); // 链表内容: 5 -> 10 -> 30 -> NULL
    
    printf("\n删除头节点 5...\n");
    deleteNode(&head, 5);
    printList(head); // 链表内容: 10 -> 30 -> NULL
    
    printf("\n尝试删除不存在的节点 99...\n");
    deleteNode(&head, 99);
    printList(head);

    printf("\n释放整个链表...\n");
    freeList(&head);
    printList(head); // 链表内容: NULL

    return 0;
}

四、链表 vs. 数组：我应该用哪个？

总结一下何时使用：

• 使用数组：

  • 当你预先知道元素的数量，且数量不怎么变化时。

  • 当你需要频繁地、快速地通过索引访问任何元素时（随机访问是主要需求）。

  • 当内存空间非常宝贵，不希望有指针的额外开销时。

• 使用链表：

  • 当你无法预知元素的数量，需要一个可以动态增长的数据结构时。

  • 当插入和删除操作非常频繁时（尤其是在列表的头部或尾部）。

  • 当随机访问不是主要需求时。