第八章：指针与链表——从零搭建动态数据结构

链表这东西，我刚开始学的时候觉得挺玄乎的。明明有数组这种现成的玩意儿，为啥还要搞个链表出来？直到我在一个嵌入式项目里，需要动态管理传感器节点的数据流——数组大小固定，根本没法应对不确定数量的数据。嗯，那时候我才真正体会到链表的价值。

说白了，链表就是一组节点，每个节点里存着数据，还存着指向下一个节点的指针。就像一串珠子，每颗珠子都知道下一颗在哪。今天我们就从最基础的单向链表开始，一步步把它玩透。

8.1 单向链表的创建与遍历

先看最基础的结构。每个节点就是一个结构体，里面有个数据域，还有个指向下一个节点的指针。

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;

创建链表，说白了就是不断分配新节点，然后把它们串起来。我个人习惯用头插法——新节点总是插在头部，这样代码写起来顺手。

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

遍历就简单了，从头节点开始，一路往下走，直到碰到 NULL。

void traverseList(Node *head) {
    Node *p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

8.2 节点的插入与删除

插入操作分三种情况：头插、尾插、中间插。头插我们已经见过了。尾插需要先找到最后一个节点。中间插则需要找到目标位置的前一个节点。

我曾经在一个通信协议栈里，需要按优先级插入数据包。那时候用的就是链表的中间插入——每次根据优先级找到合适的位置，然后插进去。

// 在指定位置之后插入
void insertAfter(Node *prev, int data) {
    if (prev == NULL) return;
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = prev->next;
    prev->next = newNode;
}

删除操作更要注意。你得先找到要删节点的前一个节点，然后绕过它。千万别忘了 free 掉内存，否则内存泄漏等着你。

void deleteNode(Node **head, int key) {
    Node *temp = *head, *prev = NULL;
    
    // 如果头节点就是要删的
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    
    // 查找要删的节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) return;  // 没找到
    
    prev->next = temp->next;
    free(temp);
}

8.3 双向链表

单向链表有个痛点：只能从头往后走，不能回头。双向链表就解决了这个问题——每个节点多了一个 prev 指针，指向前一个节点。

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

双向链表的插入和删除，说白了就是多维护一个 prev 指针。操作时要注意顺序——我习惯先搞定新节点的前后指针，再调整前后节点的指针。顺序搞反了，链表就断了。

void insertAfterDNode(DNode *prev, int data) {
    if (prev == NULL) return;
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = data;
    
    newNode->next = prev->next;
    newNode->prev = prev;
    
    if (prev->next != NULL)
        prev->next->prev = newNode;
    prev->next = newNode;
}

8.4 循环链表

循环链表就是把尾节点的 next 指向头节点，形成一个环。你想想看，这样有什么好处？从任何节点出发，都能遍历整个链表。

我记得在一个嵌入式系统的任务调度器里，就用到了循环链表。每个任务是一个节点，调度器轮流转一圈，给每个任务分配时间片。用循环链表实现这种轮询调度，简直天衣无缝。

循环链表的遍历要注意一点：不能再用 NULL 判断结尾了。你得记住起始节点，转一圈回到起点就停。

void traverseCircularList(Node *head) {
    if (head == NULL) return;
    Node *p = head;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);
    printf("\n");
}

8.5 链表的反转操作

链表反转，面试题里的常客。说白了就是把每个节点的 next 指针调个头，让最后一个变成第一个。

我常用的方法是迭代法——三个指针，逐个反转。刚开始学的时候觉得绕，画个图就清楚了。

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

还有一种递归写法，代码更简洁，但理解起来需要点功夫。我个人更推荐迭代法，调试起来方便，也不容易栈溢出。

// 递归反转（供参考）
Node* reverseRecursive(Node *head) {
    if (head == NULL || head->next == NULL)
        return head;
    Node *newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

嗯，链表的内容就讲到这里。从单向到双向，从循环到反转，每一步都是环环相扣的。你把这些基础操作练熟了，后面学更复杂的数据结构就会轻松很多。

---