现在位置: 首页 > C 语言数据结构与算法 > 正文

数据结构 - 链表

链表（Linked List）是一种由若干个节点通过指针依次连接而成的线性数据结构。

与数组不同，链表中的元素在内存中并不要求连续存放。

链表的基本概念与节点结构

链表的每个节点包含两部分：数据域（data）存储实际数据，指针域（next）指向下一个节点。

链表节点结构与内存中的链式关系

上图展示了链表在内存中的实际样貌。每个节点通过 malloc 在堆上独立分配，因此它们在内存中可以不连续。节点之间通过 next 指针串联，最后一个节点的 next 指向 NULL 表示链表结束。

在 C 语言中，链表节点通过结构体来定义：

实例

#include <stdio.h>
#include <stdlib.h>  /* malloc, free */

/* 链表节点结构体
   data：数据域，存储整型数据
   next：指针域，指向下一个同类型节点 */
struct Node {
    int data;
    struct Node* next;
};

/* 创建一个新节点
   参数 value: 节点的数据值
   返回值：指向新节点的指针，分配失败返回 NULL */
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = value;   /* 设置数据 */
    newNode->next = NULL;    /* 新节点的 next 初始化为 NULL */
    return newNode;
}

struct Node* next 是一种自引用结构，即结构体内部包含一个指向同类型结构体的指针。这是构建所有链式数据结构（链表、树、图）的核心技术。

单链表的基本操作

创建链表与遍历

实例

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

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

/* 遍历并打印链表的所有节点
   从头节点开始，沿着 next 指针逐个访问，直至 NULL */
void traverse(struct Node* head) {
    struct Node* current = head;  /* 从头部开始 */
    printf("链表内容: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;  /* 移动到下一个节点 */
    }
    printf("NULL\n");
}

/* 创建包含 n 个节点的链表（1, 2, 3, ..., n） */
struct Node* createList(int n) {
    if (n <= 0) return NULL;

    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    struct Node* tail = head;  /* tail 始终指向最后一个节点 */
    for (int i = 2; i <= n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = NULL;
        tail->next = newNode;  /* 将新节点连接到链表末尾 */
        tail = newNode;           /* 更新 tail 指针 */
    }
    return head;
}

int main() {
    struct Node* head = createList(5);
    traverse(head);
    /* 输出: 链表内容: 1 -> 2 -> 3 -> 4 -> 5 -> NULL */
    return 0;
}

插入操作

链表插入与删除操作的指针调整过程

上图展示了链表插入和删除时指针变化的完整过程。理解指针的调整顺序非常关键：如果顺序错误，会导致链表断裂或内存泄漏。

实例

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

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

/* 在链表头部插入新节点（头插法）
   时间复杂度：O(1)
   返回值：新的头节点指针 */
struct Node* insertAtHead(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = head;  /* 新节点指向原头节点 */
    return newNode;         /* 新节点成为新的头节点 */
}

/* 在链表尾部插入新节点（尾插法）
   时间复杂度：O(n)，需要遍历到尾部 */
struct Node* insertAtTail(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        return newNode;  /* 空链表，新节点即为头节点 */
    }

    struct Node* current = head;
    while (current->next != NULL) {
        current = current->next;  /* 遍历到最后一个节点 */
    }
    current->next = newNode;  /* 尾部节点指向新节点 */
    return head;
}

/* 在指定位置后插入新节点
   时间复杂度：O(n)，需要先找到 prevNode */
void insertAfter(struct Node* prevNode, int value) {
    if (prevNode == NULL) {
        printf("前驱节点不能为空\n");
        return;
    }
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    /* 关键：先让新节点指向后继，再让前驱指向新节点 */
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

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

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 30);  /* 链表: 30 */
    head = insertAtHead(head, 20);  /* 链表: 20 -> 30 */
    head = insertAtHead(head, 10);  /* 链表: 10 -> 20 -> 30 */

    printf("头插后: "); printList(head);  /* 输出: 10 20 30 */

    head = insertAtTail(head, 40);  /* 链表: 10 -> 20 -> 30 -> 40 */
    printf("尾插后: "); printList(head);  /* 输出: 10 20 30 40 */

    insertAfter(head->next, 25);    /* 在 20 后面插入 25 */
    printf("中间插入后: "); printList(head);
    /* 输出: 10 20 25 30 40 */
    return 0;
}

删除操作

实例

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

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

/* 删除链表头部节点
   时间复杂度：O(1)
   返回值：新的头节点指针 */
struct Node* deleteHead(struct Node* head) {
    if (head == NULL) return NULL;

    struct Node* temp = head;   /* 保存旧头节点 */
    head = head->next;          /* 头指针后移 */
    free(temp);                 /* 释放旧头节点的内存 */
    return head;
}

/* 删除链表中第一个值为 target 的节点
   时间复杂度：O(n)，需要遍历查找目标节点 */
struct Node* deleteByValue(struct Node* head, int target) {
    if (head == NULL) return NULL;

    /* 特殊情况：目标值在头节点 */
    if (head->data == target) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    /* 遍历查找目标节点的前驱节点 */
    struct Node* current = head;
    while (current->next != NULL && current->next->data != target) {
        current = current->next;
    }

    /* 找到目标节点，进行删除 */
    if (current->next != NULL) {
        struct Node* temp = current->next;
        current->next = current->next->next;  /* 跳过目标节点 */
        free(temp);  /* 释放目标节点内存 */
    }
    return head;
}

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

int main() {
    /* 构建链表: 10 -> 20 -> 30 -> 40 */
    struct Node* head = NULL;
    int vals[] = {10, 20, 30, 40};
    for (int i = 3; i >= 0; i--) {
        struct Node* n = (struct Node*)malloc(sizeof(struct Node));
        n->data = vals[i];
        n->next = head;
        head = n;
    }
    printf("原始链表: "); printList(head);  /* 输出: 10 20 30 40 */

    head = deleteHead(head);
    printf("删除头部后: "); printList(head);  /* 输出: 20 30 40 */

    head = deleteByValue(head, 30);
    printf("删除 30 后: "); printList(head);  /* 输出: 20 40 */
    return 0;
}

链表的删除操作中，free() 至关重要。如果只调整指针而不释放被删除节点的内存，就会造成内存泄漏。在 C 语言中，每次 malloc 都必须有对应的 free。

链表 vs 数组的对比

数组与链表全方位对比

对比维度数组链表
内存布局连续存储分散存储，通过指针连接
随机访问O(1)O(n)
头部插入/删除O(n)O(1)
尾部插入/删除O(1)O(1)（有尾指针时）/ O(n)（无尾指针）
中间插入/删除O(n)O(1)（已知位置）
空间开销仅数据本身数据 + 指针（每个节点多 8 字节（64位））
缓存友好度高（空间局部性）低（节点分散）
容量固定（静态数组）动态增长

理解这种权衡取舍，是数据结构选型的核心能力之一。

如果数据量在运行前已知且不会频繁变化，且需要频繁的随机访问，数组是更好的选择。

如果数据量会频繁增删且规模不确定，链表这类动态结构则更加灵活。

返回顶部
© 2026 菜鸟教程
备案号：闽ICP备15012807号-1

∧