30、动态数据结构（一）：链表的概念与分类

说实话，很多初学者一听到「链表」两个字，心里就开始打鼓。我当年也是这样。数组用得好好的，为什么要搞个链表出来？

其实原因很简单——数组是静态的，一旦定义好大小，想改就麻烦了。你想想看，如果程序运行时数据量不确定，或者需要频繁插入删除，数组就显得很笨重。这时候，链表就派上用场了。

什么是链表？

链表是一种动态数据结构。它的每个元素（我们叫它「节点」）不光存数据，还存着下一个节点的地址。就像寻宝游戏一样，你找到第一个线索，它告诉你第二个线索在哪，第二个又指向第三个……直到最后一个节点指向空。

我习惯把链表想象成一列火车。每节车厢（节点）里装着货物（数据），车厢之间用挂钩（指针）连起来。你可以随时加一节车厢，也可以卸掉一节，非常灵活。

链表的分类

链表不是只有一种。根据指针的连接方式，主要分为三类：

1. 单向链表

这是最基础的形式。每个节点只存一个指针，指向下一个节点。最后一个节点的指针指向 NULL。

单向链表的优点是结构简单，实现容易。缺点也很明显——只能从头往后找，不能回头。我在项目中遇到过需要频繁查找前驱节点的场景，单向链表就有点力不从心了。

2. 双向链表

双向链表在节点里多存了一个指针，指向前一个节点。这样你就可以双向遍历了。

你想想看，如果我要删除某个节点，单向链表需要从头遍历找到它的前驱节点，时间复杂度是 O(n)。而双向链表直接通过 prev 指针就能找到，时间复杂度 O(1)。

嗯，这里要注意：双向链表虽然方便，但每个节点多占了一个指针的内存。空间换时间，看你怎么权衡。

3. 循环链表

循环链表是单向链表的一个变种。它的最后一个节点不指向 NULL，而是指向头节点，形成一个环。

我曾经在实现一个任务调度器时用过循环链表。每个任务轮流执行，执行完一个就移到下一个，周而复始。用循环链表实现这种「轮转」逻辑，简直不要太顺手。

节点的定义

在 C 语言里，链表节点通常用结构体来定义。我习惯这样写：

// 单向链表节点
struct ListNode {
    int data;               // 数据域
    struct ListNode *next;  // 指针域，指向下一个节点
};

// 双向链表节点
struct DListNode {
    int data;                // 数据域
    struct DListNode *prev;  // 指向前一个节点
    struct DListNode *next;  // 指向后一个节点
};

为什么用 struct ListNode *next 而不是 ListNode *next？因为在 C 语言里，结构体还没定义完的时候，你不能直接用别名。用 struct 关键字是标准写法。

用 typedef 取别名后，代码会更简洁：

typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

// 现在可以直接用 ListNode 了
ListNode *head = NULL;

链表的创建

创建链表，说白了就是不断创建节点，然后把它们串起来。我一般用两种方式：头插法和尾插法。

头插法

每次新节点都插在链表头部。新节点的 next 指向原来的头节点，然后更新头指针指向新节点。

ListNode* createByHead(int arr[], int n) {
    ListNode *head = NULL;
    for (int i = 0; i < n; i++) {
        ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
        newNode->data = arr[i];
        newNode->next = head;  // 新节点指向原来的头
        head = newNode;        // 更新头指针
    }
    return head;
}

头插法有个特点：最后插入的节点在链表最前面。如果你按顺序插入 1、2、3，最终链表是 3→2→1。顺序是反的。

尾插法

尾插法维护一个尾指针，每次新节点都加在链表末尾。这样插入顺序和链表顺序一致。

ListNode* createByTail(int arr[], int n) {
    ListNode *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
        newNode->data = arr[i];
        newNode->next = NULL;
        
        if (head == NULL) {
            head = newNode;   // 第一个节点
            tail = newNode;
        } else {
            tail->next = newNode;  // 尾节点指向新节点
            tail = newNode;        // 更新尾指针
        }
    }
    return head;
}

我个人更推荐尾插法，因为顺序更符合直觉。但头插法在某些场景下也有优势，比如实现栈的时候。

链表的遍历

遍历链表很简单，从头节点开始，沿着 next 指针一路走，直到遇到 NULL。

void printList(ListNode *head) {
    ListNode *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;  // 移动到下一个节点
    }
    printf("\n");
}

这里有个细节：遍历时不要直接移动头指针 head，否则你就找不到链表头了。用一个临时指针 cur 来遍历，这是基本操作。

链表 vs 数组

为了让你更直观地理解链表和数组的区别，我整理了一个对比表：

对比项	数组	链表
内存空间	连续	不连续
大小调整	固定，不易扩展	动态，灵活
随机访问	O(1)，直接下标	O(n)，需要遍历
插入/删除	O(n)，需要移动元素	O(1)，只需改指针
额外内存	无	每个节点多一个指针

说白了，数组适合「读多写少」的场景，链表适合「写多读少」的场景。没有绝对的好坏，看需求。

知识体系总览

下面这张图帮你梳理了本章的核心知识点：

这张图把链表的核心脉络都串起来了。从分类到操作，再到节点定义，每一步都环环相扣。你把这个图记在脑子里，链表的基本功就算打牢了。

链表是动态数据结构的入门，也是面试的高频考点。单向链表、双向链表、循环链表，这三种形式你都要能随手写出来。节点的定义、链表的创建和遍历，这些基础操作要练到肌肉记忆。

嗯，这一章的内容就到这里。链表的世界才刚刚打开，后面还有插入、删除、反转等操作等着你。慢慢来，把基础打扎实了，后面的路就好走了。

---