数据结构线性表——单链表-CSDN博客

前言小伙伴们又见面啦这篇文章我们来一起学习线性表的第二模块——单链表。

单链表的学习就要开始上强度啦小伙伴们一定要努力坚持

---

目录

一.什么是单链表

二.单链表与顺序表的区别

三.单链表的实现

1.单链表的定义 

2.单链表的初始化

3.单链表节点的创建

 四.单链表的操作

1.单链表的打印

 2.单链表的尾插

3.单链表的头插

4.单链表的尾删

5.单链表的头删

6.单链表的查找

7.单链表在指定位置前插

8.单链表在指定位置后插

9.单链表在指定位置删除

10.单链表的销毁

五.完整代码展示

1.SLinkList.h

2.SLIinkList.c

test.c

六.总结

---

一.什么是单链表

通过物理模型我们可以这样理解单链表就是每个数据之间都用一个链条来连接而单的含义就是两个数据之间只有一条链子连接。

---

二.单链表与顺序表的区别

我们已经知道顺序表是用一个数组来存储和管理数据因为数组的大小难以改变就算是我们能够通过动态内存管理来实现数组大小的不断扩容但还是可能会出现内存浪费的情况。

而单链表就可以完美的解决这个问题。

单链表可以实现存一个数据就开辟一块空间的完美内存控制。

如下图我们每需要存入一个数据就开辟一个空间而每个空间之间我们用指针来相连前一个空间在存储数据的同时存储下一块空间的地址这样一来我们就可以杜绝空间浪费。而这样一小块一小块的空间我们称之为节点。

带着这个思路我们就开始来真正的实现单链表。

---

三.单链表的实现

1.单链表的定义 

通过上边的思路不难得出我们需要用结构体来管理每块空间

typedef int SLLDataType;
//定义单链表
typedef struct SLinkList
{
	SLLDataType data;//数据
	struct SLinkList* next;//链条
}SLLNode;

因为指针要指向下一个数据空间而空间是结构体类型所以该指针的类型就要是结构体。

而指针的名字规定为next对等“下一个”的意思。

---

2.单链表的初始化

因为单链表创建之后是没有数据的内存为空所以单链表的初始化也就是我们要使用单链表的时候创建一个单链表类型的指针变量

    SLLNode* ssl = NULL;

注意当我们创建完一个指针变量之后如果不对其进行任何赋值操作就要置空否则就会变成野指针。

---

3.单链表节点的创建

初始时刻单链表是没有任何数据的那么想要存入数据就要创建新的节点。

一个节点同时包含该节点的数据和要指向下一个节点地址的指针。

SLLNode* CreatNode(SLLDataType x)
{
	SLLNode* newnode = (SLLNode*)malloc(sizeof(SLLNode));
		if (newnode == NULL)
		{
			perror("CreatNode->malloc");
			exit(-1);
		}
		newnode->data = x;	
		newnode->next = NULL;
		return newnode;
}

开辟节点的空间我们用到malloc函数。

当我们新创建了一个节点之后要将他的指针置空因为我们并不需要在该函数中使用它的指针。

至此单链表的基础外壳就已经全部实现了下面我们就要进行单链表的各种操作。 

---

 四.单链表的操作

1.单链表的打印

基于前边顺序表学习的经验我们实现每一种操作之后都要及时测试是否无误所以我们要先有打印函数那么单链表该如何打印呢

有小伙伴说这简单啊不是每个节点都有指针指向下一个节点的地址吗直接用指针遍历打印不就好了。

但是小伙伴们是否发现虽然我们说每个节点都有一个指针来指向下一个节点但是第一个节点的地址该怎么存放依此疑惑我们引出头结点的定义。

头结点我们用phead表示让头结点去指向我们第一个节点的地址。

事实上头结点还是我们在调用各种单链表操作函数时的形参。

当我们新创建了单链表类型的变量这个变量就是一个头节点要用它去实现各种功能。

了解过头结点之后我们就能够来实现打印函数了 

void SLListPrint(SLLNode* phead)
{
	SLLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

 为了防止phead发生改变我们用cur来作为临时变量进行操作。

那么该如何理解while循环的判断条件(cur != NULL)呢

SLLNode* ssl = NULL;

这是我们的头结点也是实参把它传给函数并用phead接收再赋值给cur。

如果cur一开始就为空那么就证明当前单链表没有节点无需打印如果不为空就证明单链表有节点开始循环打印每打印一次就让cur指向下一个节点直到cur再次为空时说明没有下一个节点了循环便退出。

---

 2.单链表的尾插

先来分析一下单链表该如何尾插呢

如果单链表本来有数据那么只需要找到它的最后一个节点让它的指针指向新节点的地址。

但如果本来就没有数据那么尾插不就等于创建一个新节点。

//尾插
void SLListPushBack(SLLNode** phead, SLLDataType x)
{
   	assert(phead);
	SLLNode* newnode = CreatNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
        //找尾
		SLLNode* tail = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

首先进行一个assert(phead)的断言因为如果phead为空的话就说明单链表不存在。

尾插要创建一个新的节点所以我们先调用CreatNode函数并创建newnode节点变量来接收。

接着进行头结点的判断如果为空说明当前没有数据直接让头结点指向新的节点。

如果不为空就从头开始往后找到最后一个节点然后让最后一个节点的指针指向新的节点。

要注意这里while循环的判断条件 如果tail是最后一个节点了那么它的指针就为空因为它没有节点可以指向所以要置空防止变成野指针也就是tail->next == NULL随后就让该指针指向新节点即可。

下面请注意最重要的一点

不知道小伙伴们有没有注意到形式参数phead是一个二级指针类型呀

好奇怪为什么是二级指针呢

这就又要扯到形参是实参的一份临时拷贝这个知识点上了。

注意我们的实参ssl是一个一级结构体指针类型那么想要改变它所关联的结构体的内部数据就需要传它的地址。

而接收一个指针的地址就需要二级指针了。

 这里经常有小伙伴会认为只要我是指针我就能改变值这是一个很大的误区。

下面我们就来进行测试

void test()
{
	SLLNode* ssl = NULL;
	SLListPushBack(&ssl, 1);
	SLListPushBack(&ssl, 2);
	SLListPushBack(&ssl, 3);
	SLListPushBack(&ssl, 4);
	SLListPrint(ssl);
}

注意我们调用函数时传的都是实参ssl的地址而打印并不会改变什么所以不需要传地址。

结果如下

---

3.单链表的头插

头插相对于尾插就简单多了我们只需要创建一个新节点让它的指针指向第一个节点的地址再让头结点指向新节点的地址。

//头插
void SLListPushFront(SLLNode** phead,SLLDataType x)
{
    assert(phead);
	SLLNode* newnode = CreatNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

首先进行一个assert(phead)的断言因为如果phead为空的话就说明单链表不存在。

第一个节点的地址存在*phead里边所以直接将*phead赋值给新节点的指针然后再让*phead指向新节点。

这段代码同样也满足原单链表没有节点的情况这样*phead就为空赋值之后同样满足最后一个节点指向NULL。

测试如下

void test()
{
	SLLNode* ssl = NULL;
	SLListPushBack(&ssl, 1);
	SLListPushBack(&ssl, 2);
	SLListPushBack(&ssl, 3);
	SLListPrint(ssl);
	printf("\n");
	SLListPushFront(&ssl, 5);
	SLListPushFront(&ssl, 6);
	SLListPrint(ssl);
}

结果如下

---

4.单链表的尾删

想要尾删那就和尾插一样要先找到尾节点然后将指向尾结点的前一个节点的指针置空因为是用malloc开辟的空间所以需要再将尾节点free掉就可以完成尾删的操作了。

但是尾删还需要关注没有节点只有一个节点和有多个节点这三种情况。

那有小伙伴就会问为什么一个节点和多个节点不能用同一个代码呢

我们来分析一下如果只有一个节点我们是要直接对*phead进行free的这就需要二级指针

但是如果有多个节点我们就可以用一个临时变量指针来free空间不需要二级指针。

• 没有节点好说那就是*phead为空。
• 当只有一个节点时我们只需要将*phead给free了再将*phead置空即可。
• 当有多个节点时我们就要找尾了这时候又有一个问题找到尾之后该如何找到尾的前一个节点呢
• 有一个便捷的方法既然tail->next是下一个节点那么tail->next->next就是下下个节点当tail->next->next为尾节点时此时的tail->next就为尾结点的前一个节点啦。

实现如下 

//尾删
void SLListPopBack(SLLNode** phead)
{
	//空
	assert(*phead);
	//一个节点
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else//多个节点
	{
		//找尾
		SLLNode* tail = *phead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

判断单链表是否为空我们直接用assert函数强制断言防止过渡尾删出现错误。

测试如下

void test()
{
	SLLNode* ssl = NULL;
	SLListPushBack(&ssl, 1);
	SLListPushBack(&ssl, 2);
	SLListPushBack(&ssl, 3);
	SLListPushFront(&ssl, 5);
	SLListPrint(ssl);
	printf("\n");
	SLListPopBack(&ssl);
	SLListPopBack(&ssl);
	SLListPopBack(&ssl);
	SLListPrint(ssl);
}

结果如下

---

5.单链表的头删

头删需要和尾删一样考虑没有节点只有一个节点和多个节点这三种情况吗

我们来分析一下没有节点肯定是要用assert函数来断言的紧接着删除第一个节点那就是要让头结点指向第一个节点的next如果只有一个节点那么就是让*phead指向NULL而此时第一个节点的next不就为NULL吗

所以一个节点和多个节点就不用分开考虑了。

//头删
void SLListPopFront(SLLNode** phead)
{
	//空
	assert(*phead);
	//非空
	SLLNode* tail = *phead;
	*phead = (*phead)->next;
	free(tail);
	tail = NULL;
}

用临时变量tail来记录第一个节点接着让*phead指向下一个节点最后通过tail来释放第一个节点。

测试如下

void test()
{
	SLLNode* ssl = NULL;
	SLListPushBack(&ssl, 1);
	SLListPushBack(&ssl, 2);
	SLListPushBack(&ssl, 3);
	SLListPushBack(&ssl, 4);
	SLListPrint(ssl);
	printf("\n");
	SLListPopFront(&ssl);
	SLListPopFront(&ssl);
	SLListPopFront(&ssl);
	SLListPrint(ssl);
}

结果如下

---

6.单链表的查找

我们规定单链表的查找为通过输入数据来查找找到则返回该数据的地址找不到则返回NULL。

其实和打印也是一个差不多的类型我们就直接来实现

//查找
SLLNode* SLListFind(SLLNode* phead, SLLDataType x)
{
	SLLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

---

7.单链表在指定位置前插

单链表不像顺序表一样因为是数组所以可以直接在某个位置进行插入。而单链表的指定位置插入则可以分为前插和后插。

首先要知道想在单链表中插入数据就必须有指针所以我们要先找到指定位置的地址说到找地址就要用到单链表的查找功能了所以单链表在指定位置的插入就必须和查找挂钩使用。

//pos前插
void SLListInsertFront(SLLNode** phead, SLLNode* pos, SLLDataType x)
{
	assert(phead && *phead && pos);
	if (*phead == pos)
	{
		//头插
		SLListPushFront(phead, x);
	}
    else
    {
	    SLLNode* val = *phead;
	    while (val->next != pos)
	    {
		    val = val->next;
	    }
	    SLLNode* newnode = CreatNode(x);
	    val->next = newnode;
	    newnode->next = pos;
    }
}

注意pos位置前插入数据我们就不是仅仅要断言phead了同时还要断言*phead和pos。

• 如果*phead为空说明链表为空空链表哪有什么指定位置的概念
• 如果pos为空就说明你给了一个空位置空位置怎么插入

值得注意的是前插要判断pos是否为第一个节点如果是第一个节点就直接调用头插函数。

那有小伙伴们可能会问为什么pos是第一个节点就要特殊处理呢

我们来看while的循环条件如果pos是第一个节点那么val就是pos这样val->next永远都不可能是pos最后为空对空指针解引用操作程序就崩了。

如果是前插就必须先找到pos位置前的节点让它去指向新的节点newnode再让新节点指向pos位置的地址。

测试如下

void test()
{
	SLLNode* ssl = NULL;
	SLListPushBack(&ssl, 1);
	SLListPushBack(&ssl, 2);
	SLListPushBack(&ssl, 3);
	SLListPushBack(&ssl, 4);
	SLListPrint(ssl);
	printf("\n");
	SLLNode* pos = SLListFind(ssl, 3);
	SLListInsertFront(&ssl, pos, 5);
	SLListPrint(ssl);
}

比如我们要在数据3所处的位置的前边插入就先用查找操作找出3节点的地址并赋值给pos接着进行前插结果如下

---

8.单链表在指定位置后插

指定位置后插入数据就比前插简单多了因为我们并不用去找pos位置前的节点只需要让pos节点的指针指向新节点再让新节点去指向pos节点的后一个节点即可。

//pos后插
void SLListInsertBack(SLLNode* pos, SLLDataType x)
{
	assert(pos);
	SLLNode* newnode = CreatNode(x);
	SLLNode* tmp = pos->next;
	newnode->next = tmp;
	pos->next = newnode;
}

同样先断言一下pos定义tmp去接收pos节点的下一个节点的地址让newnode指向tmp再让pos去指向newnode。

测试如下

void test()
{
	SLLNode* ssl = NULL;
	SLListPushBack(&ssl, 1);
	SLListPushBack(&ssl, 2);
	SLListPushBack(&ssl, 3);
	SLListPushBack(&ssl, 4);
	SLListPrint(ssl);
	printf("\n");
	SLLNode* pos = SLListFind(ssl, 3);
	SLListInsertBack(pos, 5);
	SLListPrint(ssl);
}

依然是在数据3的后边插入结果如下

---

9.单链表在指定位置删除

单链表在指定位置的删除也比较简单找到pos节点的前一个让它直接指向pos节点的后一个再将pos节点释放即可。

那么指定位置的删除是否要考虑节点数问题呢

首先没有节点或是表不存在肯定是不可取的所以要先断言。

其次考虑单节点和多节点如果只有一个节点那么pos位置前就是头节点pheadpos节点后就是NULL让头节点直接指向NULL同样合情合理所以单节点和多节点可以一起处理。

此外指定位置的删除也需要判断pos是否为第一个节点。

//pos删
void SLListErase(SLLNode** phead, SLLNode* pos)
{
	assert(phead && *phead && pos);
	if (*phead == pos)
	{
        //头删
		SLListPopFront(phead);
	}
    else
    {
	    SLLNode* val = *phead;
	    while (val->next != pos)
	    {
		    val = val->next;
	    }
	    val->next = val->next->next;
	    free(pos);
	    pos = NULL;
    }
}

测试如下

void test()
{
	SLLNode* ssl = NULL;
	SLListPushBack(&ssl, 1);
	SLListPushBack(&ssl, 2);
	SLListPushBack(&ssl, 3);
	SLListPushBack(&ssl, 4);
	SLListPrint(ssl);
	printf("\n");
	SLLNode* pos = SLListFind(ssl, 3);
	SLListErase(&ssl, pos);
	SLListPrint(ssl);
}

删除数据3所在位置的节点结果如下

---

10.单链表的销毁

单链表的所有空间也是使用malloc函数开辟的所以使用之后要及时销毁。

那么只需要从头到尾将单链表遍历一遍一个一个free即可

//销毁
void SLListDestroy(SLLNode** phead)
{
	while (*phead)
	{
		SLLNode* tmp = *phead;
		*phead = (*phead)->next;
		free(tmp);
	}
}

---

五.完整代码展示

1.SLinkList.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLLDataType;

//定义单链表
typedef struct SLinkList
{
	SLLDataType data;
	struct SLinkList* next;
}SLLNode;

//打印
void SLListPrint(SLLNode* phead);
//尾插
void SLListPushBack(SLLNode** phead, SLLDataType x);
//尾删
void SLListPopBack(SLLNode** phead);
//头插
void SLListPushFront(SLLNode** phead, SLLDataType x);
//头删
void SLListPopFront(SLLNode** phead);
//查找
SLLNode* SLListFind(SLLNode* phead, SLLDataType x);
//pos前插
void SLListInsertFront(SLLNode** phead, SLLNode* pos, SLLDataType x);
//pos后插
void SLListInsertBack(SLLNode* pos, SLLDataType x);
//任意删
void SLListErase(SLLNode** phead, SLLNode* pos);

---

2.SLIinkList.c

#include "SLinkList.h"
//打印
void SLListPrint(SLLNode* phead)
{
	SLLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("NULL");
}
//创建新节点
SLLNode* CreatNode(SLLDataType x)
{
	SLLNode* newnode = (SLLNode*)malloc(sizeof(SLLNode));
	if (newnode == NULL)
	{
		perror("CreatNode->malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//尾插
void SLListPushBack(SLLNode** phead, SLLDataType x)
{
	assert(phead);
	SLLNode* newnode = CreatNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		//找尾
		SLLNode* tail = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
//头插
void SLListPushFront(SLLNode** phead, SLLDataType x)
{
	assert(phead);
	SLLNode* newnode = CreatNode(x);
	newnode->next = *phead;
	*phead = newnode;
}
//尾删
void SLListPopBack(SLLNode** phead)
{
	assert(phead);
	//空
	assert(*phead);
	//一个节点
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else//多个节点
	{
		//找尾
		SLLNode* tail = *phead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
//头删
void SLListPopFront(SLLNode** phead)
{
	assert(phead);
	//空
	assert(*phead);
	//非空
	SLLNode* tail = *phead;
	*phead = (*phead)->next;
	free(tail);
	tail = NULL;
}
//查找
SLLNode* SLListFind(SLLNode* phead, SLLDataType x)
{
	SLLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
//pos前插
void SLListInsertFront(SLLNode** phead, SLLNode* pos, SLLDataType x)
{
	assert(phead && *phead && pos);
	SLLNode* val = *phead;
	while (val->next != pos)
	{
		val = val->next;
	}
	SLLNode* newnode = CreatNode(x);
	val->next = newnode;
	newnode->next = pos;
}
//pos后插
void SLListInsertBack(SLLNode* pos, SLLDataType x)
{
	assert(pos);
	SLLNode* newnode = CreatNode(x);
	SLLNode* tmp = pos->next;
	newnode->next = tmp;
	pos->next = newnode;
}
//pos删
void SLListErase(SLLNode** phead, SLLNode* pos)
{
	assert(phead && *phead && pos);
	SLLNode* val = *phead;
	while (val->next != pos)
	{
		val = val->next;
	}
	val->next = val->next->next;
	free(pos);
	pos = NULL;
}
//销毁
void SLListDestroy(SLLNode** phead)
{
	while (*phead)
	{
		SLLNode* tmp = *phead;
		*phead = (*phead)->next;
		free(tmp);
	}
}

---

test.c

#include "SLinkList.h"
void test()
{
	SLLNode* ssl = NULL;
	SLListPushBack(&ssl, 1);
	SLListPushBack(&ssl, 2);
	SLListPushBack(&ssl, 3);
	SLListPushBack(&ssl, 4);
	SLListPrint(ssl);
	printf("\n");
	SLLNode* pos = SLListFind(ssl, 3);
	SLListErase(&ssl, pos);
	SLListPrint(ssl);
}
int main()
{
	test();
	return 0;
}

测试代码仅为例子小伙伴们可以根据自己的需求自由更改。

---

六.总结

单链表基本知识的分享到这里就结束啦博主到最后才发现这篇博客的字数竟然破万了

其实大部分都是代码所占哈哈哈。

最后小伙伴们不要忘记一键三连哦

我们下期再见啦