【数据结构】单向链表实现 超详细

目录

前言：（受篇幅限制，为了划清知识模块，进行分章节讲解）

若想了解清楚 链表的概念和分类 ：

可以点击跳转 这一章节—-> :【数据结构】链表的概念 及 分类 （使用比喻解释概念）

一. 单链表的实现

1.准备工作及其注意事项

1.1 先创建三个文件

 解释这三个文件的作用
 1、头文件SList.h  是来声明接口函数，定义链表，将几个公共用到的库函数集合起来
 2、源文件SList.c  是用来具体实现接口
 3、源文件test.c  用于接口的测试工作 ，即具体的使用场景

1.2 注意事项：帮助高效记忆和理解

1. 但凡是删除，必须 断言 链表不能为 空，避免传过来的是NULL指针 assert(*pphead);
2. 传递二级指针，要断言 不能为 NULL ，指针不能为空：assert(pphead);
3. 指定位置 pos 时，要确保pos存在：assert(pos);
4. (pphead)->next;  解引用前一定要加 括号，* 号 优先级 < 箭头操作符
5. 链表的所有插入接口：链表为空： 没有节点 就直接插入
6.要找 前一个节点 prev 或 后一个节点 next 时， 一定要确保 其本身存在！！！！
7.当指定位置 pos 刚好是 头节点时 就没有 prev 了

2.链表的基本功能接口

2.0 创建一个 链表

// 创建链表节点结构体
// 和顺序表创建原理相同，可以看我的 【顺序表】章节
typedef  int  SLDataType;
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLTNode;

2.1 链表的打印

// 打印函数
//注意这里的 phead 仅表示单向链表传递过来的 第一个节点地址，不是 双向链表的带头节点 
void SLTPrint(SLTNode* phead)
{
	SLTNode* ptemp = phead;
	while (ptemp) // ptemp != NULL 说明为是有效的节点，则循环打印
	{
		printf("%d -> ", ptemp->data);
		ptemp = ptemp->next; // 更新 ptemp ：保存下个节点的地址：遍历节点的关键
	}
	printf("NULL\n");
}

 3.链表的创建新节点接口

// 创建新节点函数：所有的插入接口，都需要 创建新节点
SLTNode* STLCreatNode(SLDataType x)
{
	// 先创建 一个 新节点
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

4.链表的节点插入功能接口

4.1 尾插接口

链表的尾插法
几种情况
1、链表非空：先找到尾节点，然后直接将尾节点 的 next 指向 新节点，(形成链接), 新节点 则 指向 NULL 变成 新的尾节点
2、链表为空：将头指针phead更新 成 新插入节点的地址，然后新节点 next 指向 NULL

// 注意：plist 头指针是 时刻更新为了指向头节点，当创建新的头节点后，要更新 plist ，而若要真正改变 plist 的值，需要传地址
// 传递过来的 头指针 &plist 是 一级指针 plist 的地址，要用 二级指针 pphead 来接收 ； 而 *pphead == plist 
// void SLTPushBack(SLTNode* phead, SLDataType x) // 错误写法：传值

void SLTPushBack(SLTNode** pphead, SLDataType x)
{
	assert(pphead); // 传递过来的 一级指针的地址 二级指针 不能为 NULL
	// 先创建 一个 新节点
	SLTNode* newNode = STLCreatNode(x);

	// 1、链表为空
	if (*pphead == NULL)
	{
		*pphead = newNode;
		return;
	}

	// 2、链表非空
	SLTNode* ptail = *pphead; // 因为要找 尾节点：干脆命名为 tail
	//本质是：找到尾节点的地址，而不是 尾节点的 next
	while (ptail->next) 
	{
		ptail = ptail->next;
	}
	ptail->next = newNode;
}

4.2 头插接口  

void SLTPushFront(SLTNode** pphead, SLDataType x)
{
	assert(pphead); // 传递过来的 一级指针的地址 二级指针 不能为 NULL
	// 先创建 一个 新节点
	SLTNode* newNode = STLCreatNode(x);

	newNode->next = *pphead; // 先将原本的 头指针放在 新节点的next
	*pphead = newNode; // 更新 头指针
}

  4.3 指定位置 pos 之前 插入接口

// 在指定位置节点pos 之前插入数据 
// 思路：找三个节点 ：prev     newNode      next 
//                  前      本身新节点     后         为了找到 地址 才能将三者链接起来
// 注意：要找 前一个节点 prev 时， 一定要确保 其本身存在！！！ 
// 当 pos 刚好是 头节点时 就没有 prev 了，特殊情况, 否则会因为找不到prev而 程序奔溃
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	assert(pphead); // 指针不能为空
	assert(pos); // pos 不能为空
	assert(*pphead); // 链表不能为空: pos 是链表中 的一个有效节点，pos 不为空，链表也不能为 空

	// 创建新节点
	SLTNode* newNode = STLCreatNode(x);
	if (*pphead == pos)
	{
		// 当 pos 刚好是 头节点时 就用 头插法：调用之前写的函数接口
		SLTPushFront(pphead, x);
		return;
	}
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	// 三者关联起来:  prev -> newNode -> pos
	newNode->next = pos;
	prev->next = newNode;
}

 4.4 指定位置pos 之后 插入接口（推荐）

// 在指定位置节点pos 之后插入数据: 注意一下错误写法： 和正确写法刚好相反
// 特点：有了 pos 就不需要 头节点了！！
void SLTInsertAfter(SLTNode*pos, SLDataType x)
{
	assert(pos); // pos 不能为空
	// 创建新节点
	SLTNode* newNode = STLCreatNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

5.链表表的删除功能接口

5.1 尾删接口

// 链表的尾删法
// 思路：删除尾节点 以及  前一个节点 pre 的next 要置为 NULL
// 要注意 只有一个节点时，没有前置节点 pre！！！！
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead); // 一级指针为plist 指向头节点，传递过来的 一级指针的地址二级指针不能为 NULL
	assert(*pphead); // 一级指针为plist 指向头节点, *pphead == plist 这个指针也不能为 NULL 不能为空链表

	// 链表非空
	// 链表只有一个节点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	// 链表有多个节点
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL; // 时刻更新保存 
	while(ptail->next)
	{ 
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

5.2头删接口

// 链表的头删法
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead); // 指针不能为空
	assert(*pphead); // 链表不能为空
	// 让第二个节点成为新的头节点
	// 将 旧的节点释放掉: 注意 要先将 第二个节点的地址  (*pphead) -> next  临时储存起来！！
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

5.3 删除 指定位置 pos 节点 接口

// 删除pos 节点
// 删除 pos 节点后，还要 将 prev 和 next （pos的前后两个节点） 链接上！！： 比较麻烦
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead); // 指针不能为空
	assert(pos); // pos 不能为空
	assert(*pphead); // 链表不能为空: pos 是链表中 的一个有效节点，pos 不为空，链表也不能为 空

	//先 让 prev 链接上 next，后 free 释放掉 pos
	// 遇到 需要找 prev 的，一定要 检查是否存在 prev
	if (*pphead == pos)//检查是否存在 prev
	{
		free(pos);
		*pphead = NULL;
		return;
	}
	SLTNode* prev = *pphead;
	while (prev->next != pos) // 找 前面节点 prev
	{
		prev = prev->next;
	}
	prev->next = pos->next; // 先赋值后 再free释放
	free(pos);
	pos = NULL;
}

 5.4 删除  指定位置 pos ==之后== 的一个 节点 接口

// 删除pos 之后的节点
// 直接 删除 pos 之后的 节点 pos->next  
// 先让 pos 和 pos -> next -> next 链接起来，后 删除 节点 pos -> next 
// 注意：像这类找 上一个节点 prev 或 找下一个节点 next ：都需要 检查 是否存在 该节点
void SLTEraseBeind(SLTNode* pos)
{
	assert(pos); // pos 不能为空
	assert(pos->next); // 这个节点必须存在，否则该函数无意义！ 链表至少要有两个节点
	 // 三者的关联关系：pos    pos->next    pos->next->next
	 // 注意：下面 先 pos->next = pos->next->next， 后 free(pos->next) 是不对的  
     // pos->next 已经更新，不是你所认为的原来的那个 中间节点了，因此要先 临时保存起来！！！
	SLTNode* temp = pos->next;
	pos->next = pos->next->next;
	free(temp);
	temp = NULL;
}

 6.链表的  查找  接口

// 链表的查找
SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{
	// 遍历链表
	assert(pphead); // 指针不能为空
	SLTNode* ptemp = *pphead;
	while (ptemp)
	{
		if (ptemp->data == x) return ptemp; // 找到了就返回节点
		ptemp = ptemp->next;
	}
	// 没找到
	return NULL;
}

7.链表的  销毁  接口

// 销毁链表
// 一旦涉及到 动态内存申请，不要忘记销毁
void SListDestory(SLTNode** pphead)
{
	assert(pphead); // 指针不能为空
	assert(*pphead); // 链表不能为空，空的没必要销毁了
	// 顺序表是一段连续的空间，可以执行一次free全部销毁，而链表节点是独立的，需要遍历节点一个一个销毁
	 // 不能直接 一个一个 free 下去，需要 保存 next 节点，才能找到下个节点！！！！
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	// 当所有节点销毁后，需要 将头指针 销毁
	*pphead = NULL;
}

二、总代码

SList.h

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

// 零、创建链表节点
typedef int SLDataType;
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLTNode;

// 一、打印函数: 这里用传址
void SLTPrint(SLTNode* ps);

// 二、尾插法
void SLTPushBack(SLTNode** pphead, SLDataType x);

// 三、头插法
void SLTPushFront(SLTNode** pphead, SLDataType x);

// 四、尾删法
void SLTPopBack(SLTNode** pphead);

// 五、头删法
void SLTPopFront(SLTNode** pphead);

// 六、链表的查找
SLTNode* SLTFind(SLTNode** pphead, SLDataType x);

// 七、指定位置 pos 之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);

// 八、指定位置 pos 之后 插入
void SLTInsertAfter(SLTNode* pos, SLDataType x);

// 九、删除 指定 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos);

// 十、删除指定 pos 之后 的节点
void SLTEraseAfter(SLTNode* pos);

// 十一、销毁链表
void SLTDestory(SLTNode** pphead);

SList.c

#include"SList.h"

// 一、打印函数: 这里用传址
void SLTPrint(SLTNode* phead)
{
	SLTNode* ptemp = phead;
	while (ptemp) //  ptemp != NULL 表示为有效节点 
	{
		printf("%d -> ", ptemp->data);
		ptemp = ptemp->next;
	}
	printf("NULL\n");
}

// 创建节点函数
SLTNode* SLTCreatNode(SLDataType x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
// 二、尾插法
void SLTPushBack(SLTNode** pphead, SLDataType x)
{
	assert(pphead);
	// 创建新节点
	SLTNode* newNode = SLTCreatNode(x);
	// 链表为空： 没有节点 就直接插入
	if (*pphead == NULL)
	{
		*pphead = newNode;
		return;
	}
	// 链表非空：找尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	ptail->next = newNode;
}

// 三、头插法
void SLTPushFront(SLTNode** pphead, SLDataType x)
{
	assert(pphead);
	// 创建新节点
	SLTNode* newNode = SLTCreatNode(x);
	// 先 链接 第一个节点，  没有第一个节点就是 NULL，也可以直接给 newNode->next，后更新 *pphead
	newNode->next = *pphead;
	*pphead = newNode;
}

// 四、尾删法
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	// 先找尾节点 和 前置节点 prev，后删除+链接
	// 当只有一个 节点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	// 当有 两个 节点 及以上
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

// 五、头删法
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	// 让 *pphead 指向第二个节点，free 掉第一个
	SLTNode* next = (*pphead)->next; // 一定要加 括号，* 号 优先级 < 箭头操作符 
	free(*pphead);
	*pphead = next;
}

// 六、链表的查找
SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{
	assert(pphead);
	// 遍历
	SLTNode* ptemp = *pphead;
	while (ptemp)
	{
		if (ptemp->data == x) return ptemp;
		ptemp = ptemp->next;
	}
	return NULL;
}

// 七、指定位置 pos 之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	// 涉及到三个节点： prev    newNode   pos
	// 创建新节点
	SLTNode* newNode = SLTCreatNode(x);
	if (*pphead == pos)// 无 prev 的情况
	{
		SLTPushFront(pphead, x);
		return;
	}
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newNode->next = pos;
	prev->next = newNode;
}

// 八、指定位置 pos 之后 插入（推荐！）
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{
	assert(pos);
	// 创建新节点
	SLTNode* newNode = SLTCreatNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

// 九、删除 指定 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	// 关系三个节点：prev    pos    next
	// 先找 prev
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

// 十、删除指定 pos 之后 的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next); // 注意  pos->next 这个必须存在
	// 关系三个节点： pos      pos->next     pos->next->next
	// 另一种可能：     pos      pos->next     NULL
	if (pos->next->next == NULL)
	{
		free(pos->next);
		pos->next = NULL;
		return;
	}
	// 直接销毁  pos->next  会找不到 pos->next->next，先保存
	SLTNode* ptemp = pos->next->next;
	free(pos->next);
	pos->next = NULL;
	pos->next = ptemp;
}

// 十一、销毁链表
void SLTDestory(SLTNode** pphead)
{
	assert(pphead);
	// 遍历销毁
	if (*pphead == NULL)return;
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	// 别忘了将 头指针销毁！！！
	*pphead = NULL;
}

test.c

#include"SList.h"

void SLTest1()
{
	// 零、创建 链表
	SLTNode* plist = NULL;

	// 二、尾插法
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4); // 1 -> 2 -> 3 -> 4 -> NULL
	printf("测试尾插：");
	SLTPrint(plist);

	// 三、头插法
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6); // 6 -> 5 -> 1 -> 2 -> 3 -> 4 -> NULL
	printf("测试头插：");
	SLTPrint(plist);

	// 四、尾删法
	SLTPopBack(&plist);
	SLTPopBack(&plist); // 6 -> 5 -> 1 -> 2 -> NULL
	printf("测试尾删：");
	SLTPrint(plist);

	// 五、头删法
	SLTPopFront(&plist);
	SLTPopFront(&plist); // 1 -> 2 -> NULL
	printf("测试头删：");
	SLTPrint(plist);

	// 六、链表的查找
	SLTNode* FindRet = SLTFind(&plist, 2);
	printf("测试查找：");
	if (FindRet) printf("找到了\n");
	else printf("没找到\n");

	// 七、指定位置 pos 之前插入
	SLTNode* FindRet1 = SLTFind(&plist, 2);
	SLTNode* FindRet2 = SLTFind(&plist, 1);
	SLTInsert(&plist, FindRet1, 200);
	SLTInsert(&plist, FindRet2, 100);// 100 -> 1 -> 200 -> 2 -> NULL
	printf("测试指定位置之前插入：");
	SLTPrint(plist);

	// 八、指定位置 pos 之后 插入（推荐！）
	SLTNode* FindRet3 = SLTFind(&plist, 2);
	SLTInsertAfter(FindRet3, 200); // 100 -> 1 -> 200 -> 2 -> 200 -> NULL
	printf("测试指定位置之后插入：");
	SLTPrint(plist);

	// 九、删除 指定 pos 节点
	SLTNode* FindRet4 = SLTFind(&plist, 1);
	SLTErase(&plist, FindRet4);// 100 -> 200 -> 2 -> 200 -> NULL
	printf("测试删除指定节点：");  
	SLTPrint(plist);

	// 十、删除指定 pos 之后 的节点
	SLTNode* FindRet5 = SLTFind(&plist, 200); // 注意如果 通过 Find 函数 找 节点，节点中有重复数据，返回 第一个遇到的
	SLTEraseAfter(FindRet5);// 100 -> 200 -> 200 -> NULL
	printf("测试删除指定节点："); 
	SLTPrint(plist);

	//
}
int main()
{
	SLTest1();
	return 0;
}

完。

若上述文章有什么错误，欢迎各位大佬及时指出，我们共同进步！