本文将详细讲解单链表的各种操作，包括链表的创建、遍历、查找（按位置和按值）、删除指定位置节点以及内存释放。每个函数都将配以代码和原理解释，帮助读者深入理解单链表的实现机制。

1. 链表结构定义

typedef int ElementType;

typedef struct LinkList{
    ElementType data;
    struct LinkList* next;
} Link;

原理解释：

定义了一个链表节点结构体，包含数据域data和指针域next

ElementType使用typedef定义，便于后续修改数据类型

每个节点通过next指针指向下一个节点，形成链式结构

2. 尾插法创建链表

int linked_list_random_position_delete_tail_insert(Link** head_pointer) {
    if(head_pointer == NULL) {
        printf("input the data is incorrect!\n");
        return -1;
    }
    // 创建头结点
    Link* head_node = (Link* ) malloc(sizeof(Link));
    if(head_node == NULL) {
        printf("create head_node memory allocation failed!\n");
        return -1;
    }
    // 将头指针指向头结点, 并将头结点的指针域赋值为 NULL（表示最后一个元素标识）
    *head_pointer = head_node;
    head_node -> next = NULL;

    // 尾指针：用于标记最后一个尾结点的
    Link* tail_pointer = head_node;

    // 开始创建有效的节点
    ElementType element;
    scanf("%d", &element);
    while(element != 9999) {
        // 创建新的结点
        Link* new_node = (Link* ) malloc(sizeof(Link));
        if(new_node == NULL) {
            printf("create new_node memory allocation failed!\n");
            return -1;
        }
        new_node -> data = element;
        new_node -> next = tail_pointer -> next;
        tail_pointer -> next = new_node;
        tail_pointer = new_node;
        scanf("%d", &element);
    }
    printf("linked list create success!\n");
    return 1;
}

原理解释：

头节点创建：首先创建头节点，头节点不存储实际数据，仅作为链表的起始标志

尾指针使用：使用tail_pointer始终指向当前链表的最后一个节点，便于快速添加新节点

插入过程：

创建新节点并设置数据

将新节点的next指向tail_pointer->next（即NULL）

将尾节点的next指向新节点

更新尾指针指向新节点

终止条件：当输入值为9999时停止创建链表

3. 链表遍历与长度计算

int linked_list_random_position_delete_print(Link* head_pointer){
    if(head_pointer == NULL) {
        printf("linked list data is empty!\n");
        return -1;
    }
    int length = 0;
    Link* start_node = head_pointer -> next;
    while(start_node != NULL) {
        printf("%d", start_node -> data);
        length++;
        start_node = start_node -> next;
        if(start_node != NULL) {
            printf(" ");
        }
    }
    printf("\n");
    return length;
}

原理解释：

遍历起点：从头节点的下一个节点开始遍历（头节点不存储数据）

遍历过程：使用while循环依次访问每个节点，直到遇到NULL指针

长度计算：在遍历过程中计数，最终返回链表长度

输出格式：在元素之间添加空格，最后一个元素后不加空格

4. 按位置查找节点

int linked_list_random_position_delete_random_position_find_node(Link* head_pointer, int find_position, int length) {
    if(head_pointer == NULL || length == 0) {
        printf("find failed, because param data is empty!\n");
        return -1;
    }
    if(find_position < 0 || find_position > length) {
        printf("find out of range!\n");
        return -1;
    }
    Link* start_node = head_pointer -> next;
    for(int i = 0; i < find_position - 1; i++) {
        start_node = start_node -> next;
    }
    return start_node -> data;
}

原理解释：

参数验证：检查链表是否为空和查找位置是否越界

查找过程：从头节点后的第一个节点开始，通过循环移动到指定位置

位置计算：由于链表从位置1开始计数，需要移动find_position-1次

返回值：返回找到的节点的数据值

5. 按值查找节点位置

int linked_list_random_position_delete_random_value_find_node(Link* head_pointer, ElementType find_value, int length) {
    if(head_pointer == NULL || length == 0) {
        printf("find node value failed!\n");
        return -1;
    }
    Link* current_node = head_pointer -> next;
    int position = 1;
    while(current_node != NULL) {
        if(current_node -> data == find_value) {
            return position;
        }
        current_node = current_node -> next;
        position++;
    }
    return -1;
}

原理解释：

遍历查找：从头节点后的第一个节点开始遍历整个链表

值比较：将每个节点的数据与目标值进行比较

位置计数：使用position变量记录当前节点的位置

返回值：找到则返回位置，未找到则返回-1

6. 删除指定位置节点

int linked_list_random_position_delete(Link** head_pointer, int position, int* length) {
    if(head_pointer == NULL || *head_pointer == NULL) {
        printf("delete node failed, because linked list node is empty!\n");
        return -1;
    }
    if(position < 1 || position > *length) {
        printf("delete node position out of range!\n");
        return -1;
    }
    Link* head_node = *head_pointer;
    Link* start_node = head_node -> next;
    // 如果删除的结点是第一个元素
    if(position == 1) {
        int data = start_node -> data;
        head_node -> next = start_node -> next;
        free(start_node);
        *length = *length - 1;
        return data;
    }

    // 如果删除的结点是第二个元素
    if(position == 2) {
        int data;
        Link* second_node = NULL;
        second_node = start_node -> next;  // 指向第二个节点
        data = second_node -> data;
        start_node -> next = second_node -> next;  // 将第二个节点的指针域，第三个节点地址给第一个节点的指针域。
        free(second_node);
        *length = *length - 1;
        return data;
    }
    // 【删除中间元素】 找到需要删除的结点的前一个结点
    for(int i = 1; i < position - 1; i++) {
        // 找到前驱节点
        start_node = start_node -> next;
    }
    int data = 0;
    Link* current = start_node -> next;
    data = current -> data;
    start_node -> next = current -> next;
    free(current);
    *length = *length - 1;
    return data;
}

原理解释：

删除第一种情况（位置1）：

直接修改头节点的next指针，跳过第一个节点

释放第一个节点的内存

更新链表长度

删除第二种情况（位置2）：

第一个节点的next指针指向第三个节点

释放第二个节点的内存

更新链表长度

删除中间或末尾节点：

先找到待删除节点的前驱节点

将前驱节点的next指向待删除节点的后继节点

释放待删除节点的内存

更新链表长度

7. 内存释放

int linked_list_random_position_delete_free_memory(Link** head_pointer, int* length) {
    if(head_pointer == NULL || *head_pointer == NULL) {
        printf("free memory of linked list data is empty!\n");
        return -1;
    }
    Link* head_node = *head_pointer;
    Link* temp = NULL;
    while(head_node != NULL) {
        temp = head_node;
        head_node = head_node -> next;
        free(temp);
    }
    *head_pointer = NULL;
    *length = 0;
    printf("free memory success!\n");
    return 1;
}

原理解释：

遍历释放：使用循环依次释放每个节点的内存

临时指针：使用temp指针保存当前要释放的节点地址

指针更新：在释放当前节点前，先将head_node指向下一个节点

重置参数：将头指针设为NULL，长度设为0，防止野指针

完整代码

• 提示：这里的代码函数名可以自己取。这里的函数名前面是区分标识，后面则是实际的函数意义。

// 随机输入一个位置，删除链表对应位置的元素
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct LinkList{
    ElementType data;
    struct LinkList* next;
} Link;

int linked_list_random_position_delete_tail_insert(Link** head_pointer);  // 创建链表
int linked_list_random_position_delete_print(Link* head_pointer);         // 遍历链表
int linked_list_random_position_delete(Link** head_pointer, int delete_position, int* length);
int linked_list_random_position_delete_random_position_find_node(Link* head_pointer, int find_position, int length);  // 位置查找
int linked_list_random_position_delete_random_value_find_node(Link* head_pointer, int find_value, int length);        // 值查找
int linked_list_random_position_delete_free_memory(Link** head_pointer, int* length);  // 释放内存

int main() {
    // 初始化头指针，目的是指向链表头结点
    Link* head_pointer = NULL;
    int linked_list_length = 0;
    linked_list_random_position_delete_tail_insert(&head_pointer);
    linked_list_length = linked_list_random_position_delete_print(head_pointer);

    printf("please input need to find node position: ");
    int find_position;
    scanf("%d", &find_position);
    int find_value = linked_list_random_position_delete_random_position_find_node(head_pointer, find_position, linked_list_length);
    if(find_value == -1) {
        printf("find failed\n");
    } else {
        printf("find_value: %d\n", find_value);
    }

    printf("please input need find value:\n");
    int value = 0;
    scanf("%d", &value);
    int find_result = linked_list_random_position_delete_random_value_find_node(head_pointer, value, linked_list_length);
    if(find_result == -1) {
        printf("find failed\n");
    } else {
        printf("find success: position = %d\n", find_result);
    }

    // 删除结点元素
    printf("please input need delete node the position:\n");
    int delete_position = 0;
    scanf("%d", &delete_position);
    int delete_result = linked_list_random_position_delete(&head_pointer, delete_position, &linked_list_length);
    if(delete_result == -1) {
        printf("delete failed!\n");
    } else {
        printf("delete success: data = %d\n", delete_result);
        linked_list_length = linked_list_random_position_delete_print(head_pointer);
        printf("linked list length = %d\n", linked_list_length);
    }
    linked_list_random_position_delete_free_memory(&head_pointer, &linked_list_length);
    return 0;
}

/**
 * 尾插法创建链表
 * @param head_pointer 头指针
 * @return
 */
int linked_list_random_position_delete_tail_insert(Link** head_pointer) {
    if(head_pointer == NULL) {
        printf("input the data is incorrect!\n");
        return -1;
    }
    // 创建头结点
    Link* head_node = (Link* ) malloc(sizeof(Link));
    if(head_node == NULL) {
        printf("create head_node memory allocation failed!\n");
        return -1;
    }
    // 将头指针指向头结点, 并将头结点的指针域赋值为 NULL（表示最后一个元素标识）
    *head_pointer = head_node;
    head_node -> next = NULL;

    // 尾指针：用于标记最后一个尾结点的
    Link* tail_pointer = head_node;

    // 开始创建有效的节点
    ElementType element;
    scanf("%d", &element);
    while(element != 9999) {
        // 创建新的结点
        Link* new_node = (Link* ) malloc(sizeof(Link));
        if(new_node == NULL) {
            printf("create new_node memory allocation failed!\n");
            return -1;
        }
        new_node -> data = element;
        new_node -> next = tail_pointer -> next;
        tail_pointer -> next = new_node;
        tail_pointer = new_node;
        scanf("%d", &element);
    }
    printf("linked list create success!\n");
    return 1;
}

/**
 * 根据用户输入的结点位置，删除结点
 * @param head_pointer  头指针
 * @param position      需要删除的元素位置
 * @param length        链表的长度
 * @return              返回被删除的结点数据域值
 */
int linked_list_random_position_delete(Link** head_pointer, int position, int* length) {
    if(head_pointer == NULL || *head_pointer == NULL) {
        printf("delete node failed, because linked list node is empty!\n");
        return -1;
    }
    if(position < 1 || position > *length) {
        printf("delete node position out of range!\n");
        return -1;
    }
    Link* head_node = *head_pointer;
    Link* start_node = head_node -> next;
    // 如果删除的结点是第一个元素
    if(position == 1) {
        int data = start_node -> data;
        head_node -> next = start_node -> next;
        free(start_node);
        *length = *length - 1;
        return data;
    }

    // 如果删除的结点是第二个元素
    if(position == 2) {
        int data;
        Link* second_node = NULL;
        second_node = start_node -> next;  // 指向第二个节点
        data = second_node -> data;
        start_node -> next = second_node -> next;  // 将第二个节点的指针域，第三个节点地址给第一个节点的指针域。
        free(second_node);
        *length = *length - 1;
        return data;
    }
    // 【删除中间元素】 找到需要删除的结点的前一个结点
    for(int i = 1; i < position - 1; i++) {
        // 找到前驱节点
        start_node = start_node -> next;
    }
    int data = 0;
    Link* current = start_node -> next;
    data = current -> data;
    start_node -> next = current -> next;
    free(current);
    *length = *length - 1;
    return data;
}


/**
 * 遍历链表 / 获取链表长度
 * @param head_pointer 头结点
 */
int linked_list_random_position_delete_print(Link* head_pointer){
    if(head_pointer == NULL) {
        printf("linked list data is empty!\n");
        return -1;
    }
    int length = 0;
    Link* start_node = head_pointer -> next;
    while(start_node != NULL) {
        printf("%d", start_node -> data);
        length++;
        start_node = start_node -> next;
        if(start_node != NULL) {
            printf(" ");
        }
    }
    printf("\n");
    return length;
}

/**
 * 根据用户输入的结点位置，返回该结点指针域的值。
 * @param head_pointer 头结点地址
 * @param find_position 需要查找结点的位置
 * @param length 链表的长度
 * @return  返回查找到的结点数据域值
 */
int linked_list_random_position_delete_random_position_find_node(Link* head_pointer, int find_position, int length) {
    if(head_pointer == NULL || length == 0) {
        printf("find failed, because param data is empty!\n");
        return -1;
    }
    if(find_position < 0 || find_position > length) {
        printf("find out of range!\n");
        return -1;
    }
    Link* start_node = head_pointer -> next;
    for(int i = 0; i < find_position - 1; i++) {
        start_node = start_node -> next;
    }
    return start_node -> data;
}

/**
 * 根据用户输入的结点数据域值，返回该结点在链表中的位置。
 * @param head_pointer 头结点地址
 * @param find_value 需要查找结点的数据域值
 * @param length 链表的长度
 * @return  返回查找到的结点在链表中的位置
 */
int linked_list_random_position_delete_random_value_find_node(Link* head_pointer, ElementType find_value, int length) {
    if(head_pointer == NULL || length == 0) {
        printf("find node value failed!\n");
        return -1;
    }
    Link* current_node = head_pointer -> next;
    int position = 1;
    while(current_node != NULL) {
        if(current_node -> data == find_value) {
            return position;
        }
        current_node = current_node -> next;
        position++;
    }
    return -1;
}

/**
 * 释放整个链表内存空间
 * @param head_pointer 头指针
 * @return
 */
int linked_list_random_position_delete_free_memory(Link** head_pointer, int* length) {
    if(head_pointer == NULL || *head_pointer == NULL) {
        printf("free memory of linked list data is empty!\n");
        return -1;
    }
    Link* head_node = *head_pointer;
    Link* temp = NULL;
    while(head_node != NULL) {
        temp = head_node;
        head_node = head_node -> next;
        free(temp);
    }
    *head_pointer = NULL;
    *length = 0;
    printf("free memory success!\n");
    return 1;
}

总结

本文详细介绍了单链表的各项基本操作，包括创建、遍历、查找、删除和内存释放。通过分段代码和原理解释，帮助读者深入理解单链表的实现机制。每个函数都考虑了边界情况和错误处理，增强了代码的健壮性。掌握这些基本操作是学习更复杂数据结构的基础。