前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >动态数据的艺术:揭开单链表的面纱

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

作者头像
平凡之路.
发布2025-06-02 12:22:21
发布2025-06-02 12:22:21
5200
代码可运行
举报
文章被收录于专栏:学习学习
运行总次数:0
代码可运行

一、引言

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

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

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

1. 概念

单链表是一种链式存储的数据结构,由一系列节点(Node)组成。每个节点包含两部分:

  • 数据域(Data):存储实际的数据内容。
  • 指针域(Next):指向链表中的下一个节点的地址。

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

链表结构示意图如下:

img
img

2. 基本结构

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

代码语言:javascript
代码运行次数:0
运行
复制
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. 创建节点

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

代码语言:javascript
代码运行次数:0
运行
复制
// 创建一个新节点
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. 初始化(创建头节点)

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

代码语言:javascript
代码运行次数:0
运行
复制
// 初始化链表,创建一个头节点
LN* ListInit() {
    LN* headnode = CreateNode(0); // 创建一个头节点,数据域初始化为 0
    return headnode; // 返回头节点
}

3. 头插法

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

代码语言:javascript
代码运行次数:0
运行
复制
// 在链表的头部添加节点
void ListPushHead(LN* phead, DataType x) {
    assert(phead); // 确保链表头节点不为空
    LN* newnode = CreateNode(x); // 创建一个新节点
    newnode->next = phead->next; // 新节点的 next 指向原头节点的下一个节点
    phead->next = newnode; // 头节点的 next 指向新节点
}

4. 尾插法

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

代码语言:javascript
代码运行次数:0
运行
复制
// 在链表的末尾添加节点
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):

代码语言:javascript
代码运行次数:0
运行
复制
// 删除链表的头部节点
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):

代码语言:javascript
代码运行次数:0
运行
复制
// 删除链表的尾部节点
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 的节点:

代码语言:javascript
代码运行次数:0
运行
复制
// 查找链表中值为 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 之前插入新节点:

代码语言:javascript
代码运行次数:0
运行
复制
// 在指定节点前插入新节点
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 之后插入新节点:

代码语言:javascript
代码运行次数:0
运行
复制
// 在指定节点后插入新节点
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 处的节点:

代码语言:javascript
代码运行次数:0
运行
复制
// 删除指定位置的节点
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. 打印链表

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

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

12. 销毁链表

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

代码语言:javascript
代码运行次数:0
运行
复制
// 销毁链表,释放所有节点的内存
void ListDestroy(LN** pphead) {
    LN* pcur = *pphead;
    LN* temp = NULL;
    while (pcur) { // 遍历链表并释放每个节点
        temp = pcur->next;
        free(pcur);
        pcur = temp;
    }
    *pphead = NULL; // 将头指针置为 NULL
}

五、完整代码

完整代码包括以下三部分:List.hList.ctest.c,分别是链表的定义、链表操作函数的实现以及测试用例。

List.h
代码语言:javascript
代码运行次数:0
运行
复制
#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
代码语言:javascript
代码运行次数:0
运行
复制
#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
代码语言:javascript
代码运行次数:0
运行
复制
#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;
}

六、总结

单链表是一种简单而强大的数据结构,适用于动态数据存储和管理。通过本文,我们介绍了单链表的基本概念、常见操作及其实现。掌握单链表的操作可以帮助我们更好地解决实际编程问题,特别是在需要频繁插入和删除操作的场景中。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-10-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、引言
  • 二、单链表的基本概念与结构
    • 1. 概念
    • 2. 基本结构
  • 三、单链表的优缺点
    • 1. 优点
    • 2. 缺点
  • 四、单链表的常见操作
    • 1. 创建节点
    • 2. 初始化(创建头节点)
    • 3. 头插法
    • 4. 尾插法
    • 5. 头删法
    • 6. 尾删法
    • 7. 查找
    • 8. 指定位置前插入
    • 9. 指定位置后插入
    • 10. 指定位置删除
    • 11. 打印链表
    • 12. 销毁链表
  • 五、完整代码
    • List.h
    • List.c
    • test.c
  • 六、总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档