【数据结构】单向链表实现超详细-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】单向链表实现超详细。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一. 单链表的实现

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

1.1 先创建三个文件

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

2.链表的基本功能接口

2.0 创建一个链表

2.1 链表的打印

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

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

4.1 尾插接口

4.2 头插接口

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

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

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

5.1 尾删接口

5.2头删接口

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

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

6.链表的查找接口

7.链表的销毁接口

二、总代码

SList.h

SList.c

test.c

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

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

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

一. 单链表的实现

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

1.1 先创建三个文件

【数据结构】单向链表实现超详细,数据结构,链表,c语言,visualstudio

解释这三个文件的作用
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

【数据结构】单向链表实现超详细,数据结构,链表,c语言,visualstudio

// 注意：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 头插接口

【数据结构】单向链表实现超详细,数据结构,链表,c语言,visualstudio

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

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

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

【数据结构】单向链表实现超详细,数据结构,链表,c语言,visualstudio

// 在指定位置节点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 之后插入接口（推荐）

【数据结构】单向链表实现超详细,数据结构,链表,c语言,visualstudio

// 在指定位置节点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 尾删接口

【数据结构】单向链表实现超详细,数据结构,链表,c语言,visualstudio

// 链表的尾删法
// 思路：删除尾节点 以及  前一个节点 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头删接口

【数据结构】单向链表实现超详细,数据结构,链表,c语言,visualstudio

// 链表的头删法
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 ==之后== 的一个节点接口

【数据结构】单向链表实现超详细,数据结构,链表,c语言,visualstudio

// 删除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;
}

完。

若上述文章有什么错误，欢迎各位大佬及时指出，我们共同进步！文章来源地址https://www.toymoban.com/news/detail-825908.html

到了这里，关于【数据结构】单向链表实现超详细的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

一. 单链表的实现

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

1.1 先创建三个文件

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

2.链表的基本功能接口

2.0 创建一个链表

2.1 链表的打印

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

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

4.1 尾插接口

4.2 头插接口

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

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

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

5.1 尾删接口

5.2头删接口

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

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

6.链表的查找接口

7.链表的销毁接口

二、总代码

SList.h

SList.c

test.c

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

一. 单链表的实现

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

1.1 先创建三个文件

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

2.链表的基本功能接口

2.0 创建一个 链表

2.1 链表的打印

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

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

4.1 尾插接口

4.2 头插接口

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

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

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

5.1 尾删接口

5.2头删接口

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

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

6.链表的 查找 接口

7.链表的 销毁 接口

二、总代码

SList.h

SList.c

test.c

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

2.0 创建一个链表

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

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

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

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

6.链表的查找接口

7.链表的销毁接口