指针与链表：单向链表的创建、遍历、插入、删除

链表这东西，我当年刚学的时候也觉得挺绕的。说白了，它就是一堆节点串在一起，每个节点里存着数据，还存着一个指向下一个节点的指针。跟数组不一样，链表不用连续的内存空间，想插就插，想删就删，灵活得很。

我个人习惯把链表想象成一列火车。每个车厢就是一个节点，车厢之间用挂钩连接——这个挂钩就是指针。火车头是头指针，最后一个车厢后面没东西了，指针就指向 NULL。

1. 单向链表的结构定义

先看看节点长什么样。每个节点包含两部分：数据域和指针域。数据域可以是你想存的任何东西，指针域就存下一个节点的地址。

// 定义链表节点结构
typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域，指向下一个节点
} Node;

这里有个细节要注意：struct Node *next 这个写法，是因为在结构体内部还没定义完，不能直接用 Node *next。嗯，这是 C 语言的语法限制，写多了就习惯了。

2. 创建链表——从无到有

创建链表，说白了就是不断往里面加节点。我一般用头插法或者尾插法。头插法快，但顺序是反的；尾插法保持顺序，但需要维护一个尾指针。

先看头插法：

// 头插法创建链表
Node* createList_head(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;
}

尾插法呢？

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

我的经验：在实际项目中，我更喜欢尾插法。因为数据顺序跟输入顺序一致，调试的时候一眼就能看出问题。头插法虽然代码短，但顺序反了容易把人搞晕。

3. 遍历链表——挨个串门

遍历链表很简单，从头节点开始，顺着 next 指针一路往下走，直到碰到 NULL 为止。

// 遍历链表并打印
void printList(Node *head) {
    Node *p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;  // 移动到下一个节点
    }
    printf("\n");
}

你想想看，这个 while 循环的条件是 p != NULL。如果 p 是 NULL 了，说明已经走到链表末尾了。我曾经见过有人写成 p->next != NULL，结果最后一个节点永远打印不出来——这就是典型的边界条件没处理好。

4. 插入节点——见缝插针

插入操作分三种情况：插在头部、插在中间、插在尾部。核心思路就是：先找到位置，再调整指针。

// 在指定位置插入节点（位置从0开始）
Node* insertNode(Node *head, int pos, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    
    // 插在头部
    if (pos == 0) {
        newNode->next = head;
        return newNode;
    }
    
    // 找到插入位置的前一个节点
    Node *prev = head;
    for (int i = 0; i < pos - 1 && prev != NULL; i++) {
        prev = prev->next;
    }
    
    if (prev == NULL) {
        printf("位置无效\n");
        free(newNode);
        return head;
    }
    
    // 插入节点
    newNode->next = prev->next;
    prev->next = newNode;
    
    return head;
}

注意：插入操作一定要先让新节点指向后面的节点，再让前面的节点指向新节点。顺序搞反了，链表就断了。我曾经在调试一个通信协议栈时犯过这个错，查了整整一个下午才发现是顺序问题。

5. 删除节点——精准拆除

删除操作比插入稍微麻烦一点，因为要释放内存。C 语言不像 Java 有垃圾回收，你不 free，内存就泄漏了。

// 删除指定位置的节点
Node* deleteNode(Node *head, int pos) {
    if (head == NULL) return NULL;
    
    Node *temp;
    
    // 删除头节点
    if (pos == 0) {
        temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    // 找到要删除节点的前一个节点
    Node *prev = head;
    for (int i = 0; i < pos - 1 && prev->next != NULL; i++) {
        prev = prev->next;
    }
    
    if (prev->next == NULL) {
        printf("位置无效\n");
        return head;
    }
    
    // 删除节点
    temp = prev->next;
    prev->next = temp->next;
    free(temp);
    
    return head;
}

删除操作的核心就三步：找到前驱节点、绕过要删的节点、释放内存。少一步都不行。

6. 链表操作的核心逻辑图

下面这张图把链表的核心操作串起来了，你看看就明白了：

单向链表核心操作流程图 头节点 节点A 节点B 节点C NULL 插入操作： 1. 创建新节点 2. 新节点->next = 前驱节点->next 3. 前驱节点->next = 新节点 删除操作： 1. 找到要删除节点的前驱节点 2. 前驱节点->next = 要删节点->next 3. free(要删节点)

7. 完整示例——把上面这些串起来

我写个完整的例子，你直接复制就能跑：

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

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

// 尾插法创建
Node* createList(int arr[], int n) {
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

// 遍历
void printList(Node *head) {
    Node *p = head;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 插入
Node* insertNode(Node *head, int pos, int val) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = val;
    if (pos == 0) {
        newNode->next = head;
        return newNode;
    }
    Node *prev = head;
    for (int i = 0; i < pos - 1 && prev; i++)
        prev = prev->next;
    if (!prev) { free(newNode); return head; }
    newNode->next = prev->next;
    prev->next = newNode;
    return head;
}

// 删除
Node* deleteNode(Node *head, int pos) {
    if (!head) return NULL;
    Node *temp;
    if (pos == 0) {
        temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    Node *prev = head;
    for (int i = 0; i < pos - 1 && prev->next; i++)
        prev = prev->next;
    if (!prev->next) return head;
    temp = prev->next;
    prev->next = temp->next;
    free(temp);
    return head;
}

int main() {
    int arr[] = {10, 20, 30, 40};
    Node *head = createList(arr, 4);
    
    printf("原始链表: ");
    printList(head);
    
    head = insertNode(head, 2, 25);
    printf("插入后: ");
    printList(head);
    
    head = deleteNode(head, 0);
    printf("删除头节点后: ");
    printList(head);
    
    return 0;
}

核心要点总结：

  • 链表节点包含数据域和指针域，指针域存放下一个节点的地址
  • 创建链表常用尾插法，保持数据顺序
  • 遍历链表用 while 循环，条件判断 p != NULL
  • 插入操作先连后断，顺序不能反
  • 删除操作记得 free 释放内存，防止泄漏
  • 所有操作都要考虑边界情况：空链表、头节点、尾节点

链表这东西，说白了就是指针的灵活运用。你只要把每个节点的 next 指针想象成一根线，串起来就是链表。我在实际项目中用链表处理过动态数据流、任务队列、内存池管理，几乎每个嵌入式系统里都能看到它的身影。多写几遍，自然就熟了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →