数据结构：单链表

文章目录

• 单链表
• • 前言
  • 一、什么是单链表
  • • 1.1概念和结构
    • • 1.1.1 结点
      • 1.1.2 链表的性质
      • 1.1.3 单链表特点
  • 二，链表的使用
  • • 2.1 链表的创建：
    • 2.2 链表的打印
    • 2.3 创建新结点
    • 2.4 创建空链表
    • • 2.4.1 带头结点空链表
      • 2.4.2 不带头结点空链表
    • 2.5 尾插
    • 2.6 头插
    • 2.7 尾删
    • 2.8 头删
    • 2.9 在指定位置之前插入结点
    • 2.10 指定位置之后插入数据
    • 2.11 删除pos结点
    • 2.11 删除pos之后的结点
    • 2.12 查找
    • 2.13 销毁
  • 三，单链表 核心易错点总结

单链表

前言

本篇我们学习单链表的知识

在学习单链表之前我们先看一下在顺序表中遗留的问题：

我们要将头插和头删的时间复杂度降到O(1)，这个时候我们就可以使用单链表

一、什么是单链表

1.1概念和结构

我们先来看数组： 数组的缺点：

• 数组是连续内存：
• 插入 / 删除中间元素：需要大量元素移位，效率低
• 必须提前定长度，容易溢出或浪费空间

单链表解决以上问题：

• 内存不连续，每个元素独立分配空间
• 每个节点存两部分：数据 + 下一个节点地址
• 靠指针串联成一条 “链”，插入、删除极快

下面我们给出单链表的概念：

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

物理结构不一定是线性的 很大概率不是，很小概率是，因为内存的分配是由操作系统完成的，不排除有连续的可能

1.1.1 结点

我们先举一个生活中的例子：

那么在链表中，每节车厢是什么样子的呢?

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”

结点的组成主要有两个部分：

• 当前结点要保存的数据
• 保存下⼀个结点的地址（指针变量）。

图中指针变量plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望plist“指向”第二个结点时，只需要修改plist保存的内容为0x0012FFA0。 链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

1.1.2 链表的性质

1.1.3 单链表特点

二，链表的使用

我们仍旧创建三个文件： test.c 测试文件 SList.h 头文件和函数声明 SList.c 函数实现

2.1 链表的创建：

在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;

//typedef struct SListNode SLTNode;

2.2 链表的打印

遍历链表 在SList.c文件中

/链表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\\n");

在SList.h文件中：

//链表的打印
void SLTPrint(SLTNode* phead);

在test.c文件中

void test01()
{
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));

node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;

node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;

SLTNode* plist = node1;
SLTPrint(plist);
}
int main()
{
test01();
return 0;
}

2.3 创建新结点

新节点的创建是必要的，无论是头插头删还是尾插尾删还是别的用法都需要创建一个新节点

在SList.c文件中：

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

return newnode;
}

2.4 创建空链表

2.4.1 带头结点空链表

核心逻辑：

在SList.c文件中

// 创建/初始化 带头结点的空链表，返回头指针
Node* InitList()
{
// 1. 分配头结点内存
Node* head = (Node*)malloc(sizeof(Node));

// 安全判断：内存分配失败
if (head == NULL)
{
printf("内存分配失败！\\n");
return NULL;
}

// 2. 空链表：头结点后继置空
head->next = NULL;

// 3. 返回头指针
return head;
}

整个链表只有一个头结点，没有任何有效元素，就是空链表。

2.4.2 不带头结点空链表

核心逻辑 不额外创建空头结点，头指针直接指向第一个有效节点。 空链表的定义：头指针 = NULL。 初始化代码 不需要函数，直接赋值即可： 在test.c 中：

int main()
{
// 不带头结点：头指针置NULL，就是空链表
Node* head = NULL;

if (head == NULL)
{
printf("当前是不带头结点的空链表\\n");
}

return 0;
}

缺点：后续增、删、查操作，要额外判断头指针是否为 NULL，代码冗余，所以开发中优先用带头结点。

声明： 下面的我们都用不带头结点的空链表来实现

2.5 尾插

需要循环遍历找到末尾，O (n) 在SList.c文件中：

//尾插：不带头结点链表尾插，pphead是头指针的地址（二级指针）
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
// 1.断言：防止传入pphead为NULL（实参没传地址）
assert(pphead);

// 2.新建一个待插入节点，next默认NULL
SLTNode* newnode = SLTbuyNode(x);

// 情况1：链表为空 *pphead == NULL（头指针是空，没有任何节点）
if (*pphead == NULL)
{
// 空链表：头指针直接指向新节点，新节点就是第一个节点
*pphead = newnode;
}
else
{
// 情况2：链表不为空，找到尾节点
SLTNode* ptail = *pphead; // ptail从头节点开始
// ptail->next != NULL就往后走，走到最后一个节点
while (ptail->next)
{
ptail = ptail->next;
}
// 尾节点next指向新节点，完成尾插
ptail->next = newnode;
}
}

为什么参数是 SLTNode** pphead（二级指针）？ 链表不带头：

• 空链表时 *pphead = NULL，要修改头指针本身的值
• C 语言函数想要修改外面变量，必须传变量地址
• pphead：接收外面头指针SLTNode* head的&head

SList.h文件中：

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

在test.c文件中：

void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
}
int main()
{
test02();
return 0;
}

要点：

SList.h文件中：

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

test.c文件中：

void test()
{
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SLTPushFront(NULL, 4);
}
int main()
{
test();
return 0;
}

2.6 头插

不用找尾，永远两步，O (1) 最快 在SList.c文件中：

//头插：在链表最前面插入x
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead); // 保护：不能传NULL进去，比如SLTPushFront(NULL,5)报错
SLTNode* newnode = SLTbuyNode(x); // 新建节点，newnode->next默认=NULL

// 第一步：新节点连上原来链表首节点
newnode->next = *pphead;

// 第二步：头指针更新为新节点（新节点变成第一个节点）
*pphead = newnode;
}

两行核心顺序不能颠倒！

newnode->next = *pphead;
*pphead = newnode;

• 先让新节点指向原来第一个节点
• 再改头指针指向新节点
• 否则会丢失后面的结点，找不到

如果写反:

• *pphead = newnode; head直接变成新节点，原链表地址直接丢失
• newnode->next = *pphead; 新节点自己指向自己，死循环

为什么是二级指针 **pphead？ 头插一定会修改外面 head 变量的值（头指针指向变了），C 函数修改外部变量需要传地址： 在test.c文件中：

void test2
{
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
}
int main()
{
test2();
return 0;
}

2.7 尾删

时间复杂度为O(n) 在SList.c文件中

void SLTPopBack(SLTNode** pphead)
{
// 断言：1.pphead不能是空 2.链表不能为空(*pphead!=NULL)，空链表不能删
assert(pphead && *pphead);

// 情况1：链表只有1个节点：(*pphead)->next==NULL
if ((*pphead)->next == NULL)
{
free(*pphead); // 释放唯一节点
*pphead = NULL; // 外头指针置空，链表变空
}
else
{
// 情况2：节点≥2个，需要找【倒数第二个节点prev】和最后一个ptail
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;

// 循环走到尾节点，prev跟着ptail同步后移，保存前驱
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}

prev->next = NULL; // 倒数第二个节点断掉和尾节点的链接
free(ptail); // 释放原尾节点内存
ptail = NULL;
}
}

关键细节：

2.8 头删

时间复杂度O(1) 在SList.c文件中：

void SLTPopFront(SLTNode** pphead)
{
//断言：pphead不能为NULL + 链表非空(*pphead≠NULL)，空链表不能头删
assert(pphead && *pphead);

//1.先用next保存原首节点的下一个节点地址
SLTNode* next = (*pphead)->next;
//2.释放原来第一个节点
free(*pphead);
//3.头指针指向原来第二个节点，成为新首节点
*pphead = next;
}

核心要点：

测试： 在test.c 文件中：

void test()
{
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
}
int main()
{
void test();
return 0;
}

2.9 在指定位置之前插入结点

时间复杂度：O(n)

//在指定pos节点之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && pos); // pphead不能空、pos不能空

// 情况1：pos就是第一个节点 → 等价头插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* newnode = SLTbuyNode(x);
// 从表头开始遍历，找到pos的前驱prev
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
// 两步链接：prev -> newnode -> pos
prev->next = newnode;
newnode->next = pos;
}
}

关键细节：

2.10 指定位置之后插入数据

时间内复杂度O(1)

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos); // pos不能是空指针
SLTNode* newnode = SLTbuyNode(x); // 创建新节点

// 1.新节点先接上pos原来的下一个
newnode->next = pos->next;
// 2.pos再指向新节点
pos->next = newnode;
}

核心优势

• 参数只用一级指针 pos，不用二级指针pphead
• O (1) 常数时间，不需要遍历找前驱（对比前面SLTInsert(pos前插)要循环找前驱 O (n)）

2.11 删除pos结点

时间复杂度O(n)

//删除pos指向的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos); // pphead不能空，pos不能是空指针

//情况1：要删的是第一个节点 → 直接复用头删
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
//情况2：pos在中间/尾部，先找pos的前驱prev
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//前驱跳过pos，直接连pos的下一个
prev->next = pos->next;
free(pos); //释放被删节点内存
pos = NULL;
}
}

关键点

• 单链表不能向前回溯，删中间节点必须从头遍历找前驱，O (n)
• 先改指针prev->next = pos->next，再 free，防止断链丢数据
• 传参必须&plist，二级指针用来处理删头节点时修改头指针

删除 pos 后一个结点（EraseAfter，O (1) 不用找前驱）

2.11 删除pos之后的结点

时间复杂度O(1)

void SLTEraseAfter(SLTNode* pos)
{
//断言：pos不能为空，且pos后面必须有节点才能删
assert(pos && pos->next);

//1.del保存待删节点（pos的下一个）
SLTNode* del = pos->next;
//2.pos直接跨过待删节点，连接del的后继
pos->next = del->next;
//3.释放被删节点，防止内存泄漏
free(del);
del = NULL;
}

优点 & 对比

• 只用一级指针、不用传二级指针
• O (1)，不用遍历找前驱，效率极高
• 只能删pos 下一个，不能删 pos 自身（删自身要用SLTErase）

2.12 查找

// 根据数据x查找节点，找到返回节点地址，找不到返回NULL
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead; // 遍历指针从头节点开始
while (pcur) // pcur != NULL就继续遍历
{
if (pcur->data == x) // 当前节点数据匹配
{
return pcur; // 直接返回该节点指针
}
pcur = pcur->next; // 不匹配，走到下一个节点
}
return NULL; // 循环走完没找到，返回空
}

关键细节

2.13 销毁

void SListDestroy(SLTNode** pphead)
{
SLTNode* pcur = *pphead; // pcur指向第一个有效节点
while (pcur) // pcur != NULL 还有节点就循环释放
{
SLTNode* next = pcur->next; // 先保存下一个节点地址（关键！）
free(pcur); // 释放当前节点
pcur = next; // pcur跳到刚才存的下一个节点
}
*pphead = NULL; // 外头指针置空，防止野指针
}

核心逻辑（为什么先存 next）

不能直接 free (pcur) 再 pcur=pcur->next

• free (pcur) 后这块内存已经还给系统，pcur->next是野指针，取值崩溃
• 所以必须提前用next保存后继

参数为什么是二级指针 **pphead：

函数最后要修改外部SLTNode* head的值为NULL；

所以在test.c中：

SListDestroy(&plist);

易错点

三，单链表 核心易错点总结

• 头节点不能丢：全程用临时指针遍历，不要直接移动 head
• 头插顺序：先接后继，再改前驱，否则断链
• 动态内存：malloc 对应 free，否则内存泄漏
• 空指针判断：每次使用指针前先判 NULL，防止程序崩溃
• 单链表单向性：无法逆向遍历，查找效率低

这时我们来回答开头的问题：