7. 结构体与链表：单向链表的实现、动态内存管理、常见操作（增删改查）

好，我们进入一个非常实战的话题——链表。说实话，很多初学者学完结构体之后，觉得它就是个打包数据的工具。但一旦把结构体和指针、动态内存结合起来，威力就出来了。链表，就是这种结合的典型代表。

我个人习惯把链表比作“手拉手的一串节点”。每个节点里存着数据，还存着一个指向下一个节点的指针。就这么简单。但就是这种简单的结构，能解决数组很多解决不了的问题——比如动态扩容、高效插入删除。

7.1 单向链表的结构定义

先看最基本的节点长什么样。每个节点就是一个结构体，里面至少两个成员：一个存数据，一个存指针。

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域，指向下一个节点
} Node;

注意这里有个小坑：结构体内部引用自身类型时，必须用 struct Node，不能用 Node。因为 typedef 还没生效呢。嗯，这个我当年刚学的时候也栽过跟头。

7.2 动态内存管理：创建与销毁节点

链表的核心优势在于动态分配内存。我们用 malloc 在堆上创建节点，用 free 释放。

// 创建新节点
Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 销毁整个链表
void destroyList(Node **head) {
    Node *current = *head;
    Node *next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

7.3 常见操作：增删改查

链表操作的核心就是“遍历 + 指针操作”。说白了，就是顺着 next 指针一个个找，找到目标位置后，改指针指向。

7.3.1 插入操作

插入分三种情况：头部插入、尾部插入、中间插入。我重点讲头部插入和中间插入，因为尾部插入其实就是中间插入的特例。

// 头部插入
void insertAtHead(Node **head, int data) {
    Node *newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 在指定位置之后插入
void insertAfter(Node *prevNode, int data) {
    if (prevNode == NULL) {
        printf("前驱节点不能为 NULL\n");
        return;
    }
    Node *newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

你想想看，为什么头部插入要传二级指针？因为我们要修改头指针本身。如果只传一级指针，函数内部修改的是指针的副本，外部头指针不会变。这个细节，面试经常考。

7.3.2 删除操作

删除比插入稍微麻烦一点，因为你要找到待删节点的前驱节点。单向链表只能往后走，不能回头，所以得用一个指针跟着。

// 删除第一个值为 data 的节点
void deleteNode(Node **head, int data) {
    if (*head == NULL) return;

    Node *temp = *head;
    Node *prev = NULL;

    // 如果头节点就是要删的
    if (temp != NULL && temp->data == data) {
        *head = temp->next;
        free(temp);
        return;
    }

    // 查找要删的节点
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }

    // 没找到
    if (temp == NULL) return;

    // 断开链接
    prev->next = temp->next;
    free(temp);
}

7.3.3 查找与修改

查找就是遍历，修改就是找到后直接赋值。没什么花哨的。

// 查找节点
Node* search(Node *head, int data) {
    Node *current = head;
    while (current != NULL) {
        if (current->data == data)
            return current;
        current = current->next;
    }
    return NULL;
}

// 修改节点值
void update(Node *head, int oldData, int newData) {
    Node *target = search(head, oldData);
    if (target != NULL) {
        target->data = newData;
    } else {
        printf("未找到节点\n");
    }
}

7.4 链表操作的核心逻辑图

下面这张图，把单向链表的核心操作流程画出来了。我建议你多看几遍，理解指针是怎么“跳舞”的。

7.5 完整示例：一个简单的通讯录链表

光说不练假把式。我写了一个小例子，把增删改查串起来。你可以直接跑跑看。

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

typedef struct Contact {
    char name[32];
    char phone[16];
    struct Contact *next;
} Contact;

Contact* createContact(const char *name, const char *phone) {
    Contact *c = (Contact*)malloc(sizeof(Contact));
    if (!c) { printf("内存不足\n"); exit(1); }
    strcpy(c->name, name);
    strcpy(c->phone, phone);
    c->next = NULL;
    return c;
}

void addContact(Contact **head, const char *name, const char *phone) {
    Contact *newC = createContact(name, phone);
    newC->next = *head;
    *head = newC;
}

void deleteContact(Contact **head, const char *name) {
    Contact *cur = *head, *prev = NULL;
    while (cur && strcmp(cur->name, name) != 0) {
        prev = cur;
        cur = cur->next;
    }
    if (!cur) { printf("未找到 %s\n", name); return; }
    if (!prev) *head = cur->next;
    else prev->next = cur->next;
    free(cur);
}

void updateContact(Contact *head, const char *name, const char *newPhone) {
    Contact *cur = head;
    while (cur && strcmp(cur->name, name) != 0)
        cur = cur->next;
    if (cur) strcpy(cur->phone, newPhone);
    else printf("未找到 %s\n", name);
}

void printList(Contact *head) {
    while (head) {
        printf("姓名: %s, 电话: %s\n", head->name, head->phone);
        head = head->next;
    }
}

int main() {
    Contact *list = NULL;
    addContact(&list, "张三", "13800138000");
    addContact(&list, "李四", "13900139000");
    addContact(&list, "王五", "13700137000");
    printf("当前通讯录:\n");
    printList(list);

    deleteContact(&list, "李四");
    printf("\n删除李四后:\n");
    printList(list);

    updateContact(list, "张三", "13600136000");
    printf("\n修改张三电话后:\n");
    printList(list);

    // 记得释放内存
    destroyList(&list);
    return 0;
}

链表这东西，说白了就是“指针的舞蹈”。你多写几遍，手熟了自然就理解了。我在项目中用过很多次链表——从简单的任务队列，到复杂的内存池管理，底层逻辑都是这一套。嗯，今天就到这里，你自己动手试试看。

---