数据结构入门：单链表详解

才是是多年

689人浏览 · 2026-05-21 22:14:38

才是是多年 · 2026-05-21 22:14:38 发布

3.1 关键概念辨别：头指针、头结点、首元结点

3.2 具体实现

3.2.1 创建新节点 SLTBuyNode

3.2.2 链表打印 SLTPrint

3.2.3 尾插 SLTPushBack

3.2.4 头插 SLTPushFront

3.2.5 尾删 SLTPopBack

3.2.6 头删 SLTPopFront

3.2.7 查找 SLTFind

3.2.8 在指定位置之前插入数据 SLTInsert

3.2.9 在指定位置之后插入数据 SLTInsertAfter

3.2.10 删除pos节点 SLTErase

3.2.11 删除pos之后的节点 SLTEraseAfter

4. 单链表优缺点总结

4.1 优点

4.2 缺点

1. 单链表概念与结构

1.1 核心定义

单链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序通过链表中的指针链接次序实现。

单链表不会提前开辟一整块连续空间，而是需要时才单独申请节点，再用指针串联起来。

1.2 通俗类比：火车车厢模型

单链表可以理解为一列火车：

每一节车厢 = 链表的一个节点
车厢里的货物 = 节点存储的数据
车厢里放的下一节车厢钥匙 = 节点里的next 指针
增删节点就像加减车厢，不影响其他车厢独立存在

1.3 节点组成

单链表的每个节点由两部分构成：

数据域：存储当前节点要保存的数据
指针域：存储下一个节点的地址，用来找到下一个节

1.4 结构特性

逻辑结构连续，物理空间不一定连续
节点空间一般从堆区动态申请
堆区空间按系统策略分配，节点可能连续也可能不连续
尾节点的指针固定指向 NULL，表示链表结束

1.5 节点结构体定义

//定义节点结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

2. 单链表头文件 SList.h

#pragma once

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

//定义节点结构
//数据 + 指向下一个节点的指针

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


//创建节点
SLTNode* SLTBuyNode(SLTDataType x);
//打印
void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SListDesTroy(SLTNode** pphead);

3. 单链表功能实现 SList.c

3.1 关键概念辨别：头指针、头结点、首元结点

在写单链表代码前，必须先分清这三个极易混淆的概念，这是理解链表传参、增删逻辑的基础：

头指针（phead /plist）
- 本质：一个指针变量，永远指向链表的起始位置
- 作用：用来找到整条链表，是链表的入口
- 特点：一定存在，即使链表为空，头指针也存在（值为 NULL）
- 本文代码中：SLTNode* phead 就是头指针
首元结点
- 本质：链表中第一个存储真实数据的节点
- 特点：链表为空时，首元结点不存在
- 注意：本文实现的无头单链表中，头指针直接指向首元结点
头结点（哨兵位结点）
- 本质：在首元结点之前额外设置的虚拟节点
- 特点：不存储有效数据，仅用来简化插入、删除操作
- 本文实现：不带头结点，是最经典的 “无头单向非循环链表”

3.2 具体实现

3.2.1 创建新节点 SLTBuyNode

//创建新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

1. perror 的作用

perror 是 C 标准库提供的错误打印函数

功能：自动打印系统级错误信息 + 自定义提示
头文件：#include <stdio.h>
用法：perror("你想加的提示信息");

在链表中的意义

当 malloc 申请节点空间失败时，perror 会输出：

malloc fail: 无法分配内存

清晰告诉我们哪里出错
自动带上系统给出的错误原因
比 printf 更专业、更方便查错

2. exit 的作用

exit 是 C 标准库提供的程序退出函数

功能：立即终止整个程序，并返回状态码
头文件：#include <stdlib.h>
用法：
- exit(0); 正常退出
- exit(非0); 异常退出（常用 exit(1)）

在链表中的意义

malloc 失败意味着无法创建节点，链表无法继续运行，继续执行只会崩溃。exit(1) 直接终止程序，避免后续代码出现空指针、野指针等严重错误。

3.2.2 链表打印 SLTPrint

//打印
void SLTPrint(SLTNode* phead)
{
    //assert(phead); - 不需要断言 - 如果为空指针的话就是空链表
    SLTNode* pcur = phead;
    while (pcur != NULL)
    {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

//assert(phead); - 不需要断言 - 如果为空指针的话就是空链表，直接打印NULL

3.2.3 尾插 SLTPushBack

1.一般情况：找到尾节点 (ptail)---->插入newnode（ptail->next = newnode）。

2.特殊情况：尾节点可能是空指针（即链表为空链表，phead == ptail == NULL），就不能对 ptail 解引用。

那么插入newnode，就是直接修改phead。

但是在函数里不能直接修改phead（函数的形参只是实参的一份临时拷贝，尾插函数只是将形参的phead的值改成了newnode并没有将真正的头指针改变，同时函数结束时这个phead局部变量会被销毁）。

因此要对phead修改就需要它的指针（即二级指针pphead）。

注意：这可能修改头指针的插入 / 删除操作都要用二级指针。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//*pphead 就是指向第一个节点的指针
	SLTNode* newnode = SLTBuyNode(x);

	//分情况：空链表和非空链表
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾节点
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}