编辑“︁C 语言单链表”︁

{{DISPLAYTITLE:C语言单链表}}

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

== 基本结构 ==
单链表的每个节点包含两部分：
* '''数据域'''：存储实际数据（如整数、字符或自定义结构体）
* '''指针域'''：存储指向下一个节点的地址

用C语言结构体表示为：
<syntaxhighlight lang="c">
struct Node {
    int data;           // 数据域（示例为整型）
    struct Node* next;  // 指针域
};
</syntaxhighlight>

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

== 核心操作 ==

=== 创建节点 ===
<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>

=== 插入操作 ===

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

==== 尾部插入 ====
<syntaxhighlight lang="c">
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;
}
</syntaxhighlight>

=== 删除操作 ===

==== 按值删除 ====
<syntaxhighlight lang="c">
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);
}
</syntaxhighlight>

=== 遍历链表 ===
<syntaxhighlight lang="c">
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
</syntaxhighlight>

'''示例输出'''：
<pre>
10 -> 20 -> 30 -> NULL
</pre>

== 时间复杂度分析 ==
{| class="wikitable"
|+ 单链表操作时间复杂度
|-
! 操作 !! 时间复杂度
|-
| 访问元素 || <math>O(n)</math>
|-
| 插入/删除（头部） || <math>O(1)</math>
|-
| 插入/删除（尾部） || <math>O(n)</math>
|-
| 搜索 || <math>O(n)</math>
|}

== 实际应用案例 ==
'''学生成绩管理系统'''的实现：
<syntaxhighlight lang="c">
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类型
}
</syntaxhighlight>

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

== 常见问题解答 ==
'''Q：单链表和数组的主要区别是什么？'''
* 数组是连续内存空间，链表是非连续的
* 数组支持随机访问（O(1)），链表需要顺序访问（O(n)）
* 链表可以动态增长，数组大小固定（除非动态分配）

'''Q：何时应该选择单链表而非数组？'''
* 需要频繁在头部/中部插入删除元素时
* 数据总量不可预知或变化较大时
* 不需要随机访问元素的场景

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

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

[[Category:编程语言]]
[[Category:C]]
[[Category:C 语言高级数据结构]]