在C语言中，单向链表是一种动态数据结构，由多个节点（Node）组成。每个节点包含两个部分：一个是数据部分（通常是存储的实际值），另一个是指向下一个节点的指针。链表的第一个节点被称为头节点（head），最后一个节点的指针指向NULL，表示链表的结束。

单向链表的概念

• 节点 (Node)：链表的基本单元。每个节点包含数据域和指向下一个节点的指针。
• 头节点 (Head)：链表的入口点，指向链表的第一个节点。
• 尾节点 (Tail)：链表的最后一个节点，它的指针指向 NULL。
• NULL 指针：用于标识链表的结束。

单向链表与数组不同，链表节点的存储位置在内存中不是连续的，它们通过指针相互连接，因此插入或删除节点时不需要移动其他节点，但需要动态分配和释放内存。

单向链表的基本操作

• 创建链表：初始化一个空链表。
• 插入节点：在链表的头部或尾部插入节点，或者在指定位置插入。
• 删除节点：从链表中删除指定位置的节点。
• 遍历链表：从头节点开始，依次访问链表中的每个节点。
• 释放链表：释放链表中动态分配的所有节点内存。

单向链表的结构定义

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

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

基本操作实现

1. 创建新节点

// 创建新节点
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; // 初始化下一个节点指针为 NULL
    return newNode;
}

2. 插入节点到链表头部

// 插入节点到链表头部
void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = createNode(data); // 创建新节点
    newNode->next = *head; // 新节点指向原来的头节点
    *head = newNode; // 更新头节点为新节点
}

3. 在链表尾部插入节点

// 插入节点到链表尾部
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;  // 最后一个节点指向新节点
}

4. 删除节点

// 从链表中删除值为data的节点
void deleteNode(struct Node** head, int data) {
    struct Node* temp = *head, *prev = NULL;

    // 检查链表是否为空
    if (temp == NULL) {
        printf("链表为空，所以节点中找不到%s\n", data);
        return;
    }

    // 如果头节点就是要删除的节点
    if (temp != NULL && temp->data == data) {
        *head = temp->next; // 将头节点更新为下一个节点
        free(temp);         // 释放原来的头节点内存
        return;
    }

    // 遍历链表找到要删除的节点
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }

    // 如果遍历结束也没有找到要删除的节点打印提示信息
    if (temp == NULL) {
        printf("在节点中，找不到%s\n", data);
        return;
    }

    prev->next = temp->next; // 跳过要删除的节点
    free(temp);              // 释放节点内存
}

5. 遍历链表

// 遍历链表并打印每个节点的数据
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

6. 释放链表

// 释放链表的所有节点
void freeList(struct Node** head) {
    struct Node* current = *head;
    struct Node* next;

    while (current != NULL) {
        next = current->next; // 保存下一个节点
        free(current);        // 释放当前节点
        current = next;       // 移动到下一个节点
    }

    *head = NULL; // 头指针置为 NULL，表示链表已空
}

使用示例

int main() {
    struct Node* head = NULL;  // 初始化空链表

    // 插入数据
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);
    insertAtTail(&head, 4);
    insertAtTail(&head, 5);

    // 打印链表
    printf("链表内容: ");
    printList(head);

    // 删除节点
    deleteNode(&head, 3);
    printf("删除节点3后的链表: ");
    printList(head);

    // 释放链表
    freeList(&head);

    return 0;
}

运行结果

链表内容: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
删除节点3后的链表: 1 -> 2 -> 4 -> 5 -> NULL

总结

单向链表是一种常用的动态数据结构，适合频繁插入和删除操作的场景。与数组相比，它可以有效利用内存，但因为节点存储在不连续的内存中，查找操作需要从头节点遍历，时间复杂度为 O(n)。