C 语言单链表

单链表（Singly Linked List）是C语言中最基础的高级数据结构之一，它由一系列节点（Node）组成，每个节点包含数据域和指向下一个节点的指针域。与数组不同，单链表在内存中是非连续存储的，通过指针实现动态内存分配和灵活的数据操作。

基本结构

单链表的每个节点包含两部分：

• 数据域：存储实际数据（如整数、字符或自定义结构体）
• 指针域：存储指向下一个节点的地址

用C语言结构体表示为：

struct Node {
    int data;           // 数据域（示例为整型）
    struct Node* next;  // 指针域
};

graph LR A[节点1] -->|next| B[节点2] B -->|next| C[节点3] C -->|next| NULL

核心操作

创建节点

#include <stdlib.h>

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败！");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

插入操作

头部插入

void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

尾部插入

void insertAtTail(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

删除操作

按值删除

void deleteNode(struct Node** head, int key) {
    struct 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);
}

遍历链表

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

示例输出：

10 -> 20 -> 30 -> NULL

时间复杂度分析

单链表操作时间复杂度

操作	时间复杂度
访问元素	$O(n)$
插入/删除（头部）	$O(1)$
插入/删除（尾部）	$O(n)$
搜索	$O(n)$

实际应用案例

学生成绩管理系统的实现：

struct Student {
    char name[50];
    int score;
};

void addStudentRecord(struct Node** head) {
    struct Student newStudent;
    printf("输入学生姓名: ");
    scanf("%s", newStudent.name);
    printf("输入学生成绩: ");
    scanf("%d", &newStudent.score);
    
    insertAtTail(head, newStudent); // 需要修改节点结构体以支持Student类型
}

内存管理注意事项

1. 每次调用malloc()后必须检查返回值 2. 删除节点后必须使用free()释放内存 3. 避免内存泄漏（如修改链表指针时丢失原有节点引用） 4. 多线程环境下需要添加同步机制

常见问题解答

Q：单链表和数组的主要区别是什么？

• 数组是连续内存空间，链表是非连续的
• 数组支持随机访问（O(1)），链表需要顺序访问（O(n)）
• 链表可以动态增长，数组大小固定（除非动态分配）

Q：何时应该选择单链表而非数组？

• 需要频繁在头部/中部插入删除元素时
• 数据总量不可预知或变化较大时
• 不需要随机访问元素的场景

进阶技巧

• 快慢指针法：用于检测环、找中间节点等
• 递归处理：反向打印链表等操作
• 哨兵节点：简化边界条件处理

通过系统学习单链表，学习者将为理解更复杂的数据结构（如双向链表、树、图等）奠定坚实基础。