动态数据的艺术：揭开单链表的面纱

平凡之路.

发布于 2025-06-02 12:22:21

5300

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

一、引言

单链表（Singly Linked List）是数据结构中最基础且广泛应用的链式结构之一。与数组不同，单链表在内存中的元素不需要连续存储，每个元素（节点）通过指针连接到下一个节点。这种非连续存储结构，使得单链表在动态内存管理、插入和删除操作上有着明显的优势。它在处理动态数据或需要频繁插入删除的场景中尤为高效，因此在许多算法和应用中扮演着重要角色。

本文将全面介绍单链表的概念、结构和常见操作，提供完整的代码实现，并详细讲解每个操作的核心思想。通过本文的学习，你将能够深入理解单链表的特点及其在编程中的实际应用。

二、单链表的基本概念与结构

1. 概念

单链表是一种链式存储的数据结构，由一系列节点（Node）组成。每个节点包含两部分：

数据域（Data）：存储实际的数据内容。
指针域（Next）：指向链表中的下一个节点的地址。

链表的特点是节点在内存中不需要连续存储，这与数组不同，数组的元素是连续存储在内存中的。由于这一特点，链表的插入和删除操作不涉及大量的元素移动，因此操作非常灵活、高效，尤其适合动态数据的管理。通过指针的连接，链表能够动态扩展，存储任意数量的节点，而不会像数组一样受到固定容量的限制。

链表结构示意图如下：

2. 基本结构

单链表的基本结构由节点和指针组成。每个节点包含数据部分和指向下一个节点的指针。下面是C语言中单链表节点的定义：

typedef int DataType;
typedef struct ListNode
{
	DataType data;//数据域
	struct ListNode* next;//指针域,指向下一个节点
}LN;

每个节点通过 next 指针连接到下一个节点，最后一个节点的 next 指针为空（即指向 NULL），表示链表的终点。整个链表的入口称为头指针（Head Pointer），它指向第一个节点的位置。如果链表为空，头指针为 NULL。

三、单链表的优缺点

1. 优点

动态内存管理： 单链表在内存中不要求节点的连续存储，可以根据需求动态分配或释放内存，适应动态数据变化。
高效的插入和删除操作： 在链表的任意位置进行插入或删除操作时，只需调整相关节点的指针即可，时间复杂度为 O(1)，比数组的O(n)更加高效。
灵活性强： 单链表不需要在创建时就确定存储空间的大小，适合数据量不确定的场景。

2. 缺点

额外的内存开销： 每个节点需要存储一个指针，增加了内存使用。
访问效率低： 访问链表中的第 n 个元素时，需要从头节点开始依次遍历，时间复杂度为 O(n)，无法像数组那样通过下标快速访问。
不支持反向遍历： 单链表只能从头节点开始向后遍历，无法直接从尾部向前遍历。

四、单链表的常见操作

单链表的常见操作包括节点的插入、删除、查找、遍历和销毁。以下将详细介绍这些操作的实现方法，并提供相应的代码示例。

1. 创建节点

每个节点是链表的基本组成部分。以下代码用于创建一个新节点，并初始化节点中的数据和指针：

// 创建一个新节点
LN* CreateNode(DataType x) {
    // 分配一个新的链表节点内存
    LN* newnode = (LN*)malloc(sizeof(LN));
    if (newnode == NULL) { // 判断内存分配是否成功
        perror("malloc fail"); // 输出错误信息
        exit(-1); // 程序退出，表示分配失败
    }
    newnode->data = x; // 设置节点的数据域
    newnode->next = NULL; // 将节点的 next 指针置为 NULL
    return newnode; // 返回新创建的节点
}

2. 初始化（创建头节点）

链表的头节点作为链表的入口，初始化链表时，通常会先创建一个头节点（头节点的数据部分可以存储不使用的数据或空值）。以下代码用于初始化链表并创建头节点：

// 初始化链表，创建一个头节点
LN* ListInit() {
    LN* headnode = CreateNode(0); // 创建一个头节点，数据域初始化为 0
    return headnode; // 返回头节点
}

3. 头插法

在链表的头部插入新节点（即在第一个元素之前插入新节点），时间复杂度为 O(1)：

// 在链表的头部添加节点
void ListPushHead(LN* phead, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* newnode = CreateNode(x); // 创建一个新节点
    newnode->next = phead->next; // 新节点的 next 指向原头节点的下一个节点
    phead->next = newnode; // 头节点的 next 指向新节点
}

4. 尾插法

在链表的尾部插入新节点，时间复杂度为 O(n)：

// 在链表的末尾添加节点
void ListPushBack(LN* phead, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* newnode = CreateNode(x); // 创建一个新节点
    LN* pcur = phead;
    while (pcur->next != NULL) { // 遍历到链表的末尾
        pcur = pcur->next;
    }
    pcur->next = newnode; // 将新节点添加到链表的末尾
}

5. 头删法

删除链表头部的第一个节点，时间复杂度为 O(1)：

// 删除链表的头部节点
void ListDelHead(LN* phead) {
    assert(phead); // 确保链表头节点不为空
    if (phead->next == NULL) { // 判断链表是否为空
        printf("链表为空，无法进行删除操作！\n");
        return;
    }
    LN* temp = phead->next; // 保存头部节点
    phead->next = phead->next->next; // 头节点的 next 指向原头部节点的下一个节点
    free(temp); // 释放原头部节点的内存
}

6. 尾删法

删除链表尾部的最后一个节点，时间复杂度为 O(n)：

// 删除链表的尾部节点
void ListDelBack(LN* phead) {
    assert(phead); // 确保链表头节点不为空
    if (phead->next == NULL) { // 判断链表是否为空
        printf("链表为空，无法进行删除操作！\n");
        return;
    }
    LN* pcur = phead;
    while (pcur->next->next != NULL) { // 找到倒数第二个节点
        pcur = pcur->next;
    }
    free(pcur->next); // 释放最后一个节点的内存
    pcur->next = NULL; // 将倒数第二个节点的 next 置为 NULL
}

7. 查找

在链表中查找值为 x 的节点：

// 查找链表中值为 x 的节点
LN* ListFind(LN* phead, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* pcur = phead->next;
    while (pcur) { // 遍历链表
        if (pcur->data == x) { // 如果找到数据域等于 x 的节点
            return pcur; // 返回该节点
        }
        pcur = pcur->next;
    }
    return NULL; // 没有找到则返回 NULL
}

8. 指定位置前插入

在指定节点 pos 之前插入新节点：

// 在指定节点前插入新节点
void ListInsertFront(LN* phead, LN* pos, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* pcur = phead;
    if (pos == NULL) { // 判断插入位置是否合法
        printf("插入位置非法\n");
        return;
    }
    while (pcur->next != pos) { // 找到 pos 的前一个节点
        pcur = pcur->next;
    }
    LN* newnode = CreateNode(x); // 创建新节点
    newnode->next = pos; // 新节点的 next 指向 pos
    pcur->next = newnode; // 前一个节点的 next 指向新节点
}

9. 指定位置后插入

在指定节点 pos 之后插入新节点：

// 在指定节点后插入新节点
void ListInsertBack(LN* pos, DataType x) {
    if (pos == NULL) { // 判断插入位置是否合法
        printf("插入位置非法\n");
        return;
    }
    LN* newnode = CreateNode(x); // 创建新节点
    newnode->next = pos->next; // 新节点的 next 指向 pos 的下一个节点
    pos->next = newnode; // pos 的 next 指向新节点
}

10. 指定位置删除

删除指定位置 pos 处的节点：

// 删除指定位置的节点
void ListErase(LN* phead, LN* pos) {
    assert(phead); // 确保链表头节点不为空
    if (pos == NULL) { // 判断删除位置是否合法
        printf("删除位置非法\n");
        return;
    }
    if (phead->next == NULL) { // 判断链表是否为空
        printf("链表为空，无法进行删除操作！\n");
        return;
    }
    LN* pcur = phead;
    while (pcur->next != pos) { // 找到 pos 的前一个节点
        pcur = pcur->next;
    }
    pcur->next = pos->next; // 前一个节点的 next 指向 pos 的下一个节点
    free(pos); // 释放 pos 的内存
}

11. 打印链表

遍历并打印链表中的所有元素：

// 打印链表中的所有节点
void ListPrint(LN* phead) {
    assert(phead); // 确保链表头节点不为空
    LN* pcur = phead->next;
    while (pcur) { // 遍历链表中的每个节点
        printf("%d->", pcur->data); // 打印当前节点的数据
        pcur = pcur->next;
    }
    printf("NULL\n"); // 链表结束时打印 NULL
}

12. 销毁链表

释放链表中所有节点的内存，防止内存泄漏：

// 销毁链表，释放所有节点的内存
void ListDestroy(LN** pphead) {
    LN* pcur = *pphead;
    LN* temp = NULL;
    while (pcur) { // 遍历链表并释放每个节点
        temp = pcur->next;
        free(pcur);
        pcur = temp;
    }
    *pphead = NULL; // 将头指针置为 NULL
}

五、完整代码

完整代码包括以下三部分：List.h、List.c 和 test.c，分别是链表的定义、链表操作函数的实现以及测试用例。

`List.h`

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct ListNode
{
	DataType data;//数据域
	struct ListNode* next;//指针域,指向下一个节点
}LN;
//创建节点
LN* CreateNode(DataType x);
// 初始化链表（创建头节点）
LN* ListInit();
//尾插
void ListPushBack(LN* phead, DataType x);
//头插
void ListPushHead(LN* phead, DataType x);
//尾删
void ListDelBack(LN* phead);
//头删
void ListDelHead(LN* phead);
//打印链表
void ListPrint(LN *phead);
//查找
LN* ListFind(LN* phead, DataType x);
//指定位置前插入
void ListInsertFront(LN* phead, LN*pos,DataType x);
//指定位置后插入
void ListInsertBack(LN* pos, DataType x);
//指定位置节点删除
void ListErase(LN*phead,LN*pos);
//销毁
void ListDestroy(LN**pphead);

`List.c`

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
// 创建一个新节点
LN* CreateNode(DataType x) {
    // 分配一个新的链表节点内存
    LN* newnode = (LN*)malloc(sizeof(LN));
    if (newnode == NULL) { // 判断内存分配是否成功
        perror("malloc fail"); // 输出错误信息
        exit(-1); // 程序退出，表示分配失败
    }
    newnode->data = x; // 设置节点的数据域
    newnode->next = NULL; // 将节点的 next 指针置为 NULL
    return newnode; // 返回新创建的节点
}

// 初始化链表，创建一个头节点
LN* ListInit() {
    LN* headnode = CreateNode(0); // 创建一个头节点，数据域初始化为 0
    return headnode; // 返回头节点
}

// 在链表的末尾添加节点
void ListPushBack(LN* phead, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* newnode = CreateNode(x); // 创建一个新节点
    LN* pcur = phead;
    while (pcur->next != NULL) { // 遍历到链表的末尾
        pcur = pcur->next;
    }
    pcur->next = newnode; // 将新节点添加到链表的末尾
}

// 在链表的头部添加节点
void ListPushHead(LN* phead, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* newnode = CreateNode(x); // 创建一个新节点
    newnode->next = phead->next; // 新节点的 next 指向原头节点的下一个节点
    phead->next = newnode; // 头节点的 next 指向新节点
}

// 删除链表的尾部节点
void ListDelBack(LN* phead) {
    assert(phead); // 确保链表头节点不为空
    if (phead->next == NULL) { // 判断链表是否为空
        printf("链表为空，无法进行删除操作！\n");
        return;
    }
    LN* pcur = phead;
    while (pcur->next->next != NULL) { // 找到倒数第二个节点
        pcur = pcur->next;
    }
    free(pcur->next); // 释放最后一个节点的内存
    pcur->next = NULL; // 将倒数第二个节点的 next 置为 NULL
}

// 删除链表的头部节点
void ListDelHead(LN* phead) {
    assert(phead); // 确保链表头节点不为空
    if (phead->next == NULL) { // 判断链表是否为空
        printf("链表为空，无法进行删除操作！\n");
        return;
    }
    LN* temp = phead->next; // 保存头部节点
    phead->next = phead->next->next; // 头节点的 next 指向原头部节点的下一个节点
    free(temp); // 释放原头部节点的内存
}

// 打印链表中的所有节点
void ListPrint(LN* phead) {
    assert(phead); // 确保链表头节点不为空
    LN* pcur = phead->next;
    while (pcur) { // 遍历链表中的每个节点
        printf("%d->", pcur->data); // 打印当前节点的数据
        pcur = pcur->next;
    }
    printf("NULL\n"); // 链表结束时打印 NULL
}

// 查找链表中值为 x 的节点
LN* ListFind(LN* phead, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* pcur = phead->next;
    while (pcur) { // 遍历链表
        if (pcur->data == x) { // 如果找到数据域等于 x 的节点
            return pcur; // 返回该节点
        }
        pcur = pcur->next;
    }
    return NULL; // 没有找到则返回 NULL
}

// 在指定节点前插入新节点
void ListInsertFront(LN* phead, LN* pos, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* pcur = phead;
    if (pos == NULL) { // 判断插入位置是否合法
        printf("插入位置非法\n");
        return;
    }
    while (pcur->next != pos) { // 找到 pos 的前一个节点
        pcur = pcur->next;
    }
    LN* newnode = CreateNode(x); // 创建新节点
    newnode->next = pos; // 新节点的 next 指向 pos
    pcur->next = newnode; // 前一个节点的 next 指向新节点
}

// 在指定节点后插入新节点
void ListInsertBack(LN* pos, DataType x) {
    if (pos == NULL) { // 判断插入位置是否合法
        printf("插入位置非法\n");
        return;
    }
    LN* newnode = CreateNode(x); // 创建新节点
    newnode->next = pos->next; // 新节点的 next 指向 pos 的下一个节点
    pos->next = newnode; // pos 的 next 指向新节点
}

// 删除指定位置的节点
void ListErase(LN* phead, LN* pos) {
    assert(phead); // 确保链表头节点不为空
    if (pos == NULL) { // 判断删除位置是否合法
        printf("删除位置非法\n");
        return;
    }
    if (phead->next == NULL) { // 判断链表是否为空
        printf("链表为空，无法进行删除操作！\n");
        return;
    }
    LN* pcur = phead;
    while (pcur->next != pos) { // 找到 pos 的前一个节点
        pcur = pcur->next;
    }
    pcur->next = pos->next; // 前一个节点的 next 指向 pos 的下一个节点
    free(pos); // 释放 pos 的内存
}

// 销毁链表，释放所有节点的内存
void ListDestroy(LN** pphead) {
    LN* pcur = *pphead;
    LN* temp = NULL;
    while (pcur) { // 遍历链表并释放每个节点
        temp = pcur->next;
        free(pcur);
        pcur = temp;
    }
    *pphead = NULL; // 将头指针置为 NULL
}

`test.c`

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test1()
{
	LN* phead = ListInit();//创建头节点，头指针指向头节点 
	ListPushHead(phead, 1);
	ListPushHead(phead, 2);
	ListPushHead(phead, 3);
	//ListDelBack(phead);
	//ListDelHead(phead);
	//测试查找
	LN * find = ListFind(phead,2);
	/*if (find == NULL)
	{
		printf("没有找到!\n");
	}
	else
	{
		printf("找到了!\n");
	}*/
	//ListInsertFront(phead, find, 99);
	//ListInsertBack(find,88);
	//ListErase(phead, find);
	ListPrint(phead);
	//ListDestroy(&phead);
}
int main()
{
	test1();
	return 0;
}