C 语言链表基础

C语言链表基础

介绍

链表（Linked List）是C语言中一种重要的动态数据结构，它通过指针将一组零散的内存块串联起来，每个内存块称为一个节点（Node）。与数组不同，链表不需要连续的内存空间，可以高效地进行插入和删除操作。链表广泛应用于操作系统、文件系统、数据库等领域。

链表主要分为：

• 单向链表：每个节点包含数据和指向下一个节点的指针。
• 双向链表：节点包含指向前一个和后一个节点的指针。
• 循环链表：尾节点指向头节点，形成环形结构。

单向链表的结构

一个单向链表的节点通常由两部分组成： 1. 数据域：存储实际数据。 2. 指针域：存储指向下一个节点的地址。

用C语言结构体表示如下：

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

链表的基本操作

创建链表

以下代码演示如何创建一个包含3个节点的单向链表：

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

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

int main() {  
    // 创建3个节点  
    struct Node* head = NULL;  
    struct Node* second = NULL;  
    struct Node* third = NULL;  

    head = (struct Node*)malloc(sizeof(struct Node));  
    second = (struct Node*)malloc(sizeof(struct Node));  
    third = (struct Node*)malloc(sizeof(struct Node));  

    // 赋值并链接节点  
    head->data = 1;  
    head->next = second;  

    second->data = 2;  
    second->next = third;  

    third->data = 3;  
    third->next = NULL;  

    // 遍历链表并打印  
    struct Node* current = head;  
    while (current != NULL) {  
        printf("%d -> ", current->data);  
        current = current->next;  
    }  
    printf("NULL\n");  

    return 0;  
}

输出：

  
1 -> 2 -> 3 -> NULL  

插入节点

在链表中插入节点分为： 1. 头部插入 2. 尾部插入 3. 中间插入

以下示例展示在头部插入新节点：

  
void insertAtHead(struct Node** head_ref, int new_data) {  
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));  
    new_node->data = new_data;  
    new_node->next = *head_ref;  
    *head_ref = new_node;  
}

删除节点

删除指定值的节点：

  
void deleteNode(struct Node** head_ref, int key) {  
    struct Node* temp = *head_ref, *prev = NULL;  

    if (temp != NULL && temp->data == key) {  
        *head_ref = 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);  
}

链表的可视化表示

使用Mermaid绘制单向链表：

graph LR A[Head] --> B[1] B --> C[2] C --> D[3] D --> E[NULL]

实际应用案例

场景：实现一个简单的学生成绩管理系统，使用链表动态添加和删除学生记录。

  
struct Student {  
    int id;  
    char name[50];  
    float grade;  
    struct Student* next;  
};  

void addStudent(struct Student** head, int id, char* name, float grade) {  
    struct Student* new_student = (struct Student*)malloc(sizeof(struct Student));  
    new_student->id = id;  
    strcpy(new_student->name, name);  
    new_student->grade = grade;  
    new_student->next = *head;  
    *head = new_student;  
}

时间复杂度分析

链表操作的复杂度：

• 访问：$O(n)$
• 插入/删除（已知位置）：$O(1)$
• 搜索：$O(n)$

常见问题与注意事项

1. 内存泄漏：每次调用malloc()后必须调用free()。 2. 空指针检查：操作前需验证指针是否为NULL。 3. 头节点处理：插入/删除头节点时需要特殊处理。

总结

链表是C语言中灵活的数据结构，适合动态数据管理。掌握其核心操作（创建、插入、删除、遍历）是学习高级数据结构（如树、图）的基础。通过实践案例（如学生管理系统）可以加深理解。