【数据结构】单链表定义的介绍及增删查改的实现

目录

前言

结点的初始化

增删

打印

查找

在指定位置后的插入

 删除指定位置下一个结点的数据

销毁

 与顺序表的对比

总结

源码

---

前言

相信很多人都像我一样，在正式学习链表之前就已经听过它的大名，但是就是不知道它究竟是干什么、怎么用的，在遇到这类题目时也只能跳过。这次就讲讲链表这个数据结构，让大家有更深入的了解。

链表与顺序表都是一种线性表，使数据的存放跟读取更加方便快捷，我们都知道一组数据是连续存放在顺序表里的，而链表不同，它的数据是零散存放的，每个数据称为一个结点，上一个结点指向下一个结点，如此便链接成了链表。

 即 使用一个结构体来表示一个结点，里面包含要存储的数据以及下一个结点的地址，同时用 typedef 对数据类型进行转换，方便以后更改。这就是单链表。

链表的根据一些结构的变化，其功能会变得更加完善，分作单项还是双向，带头和不带头，循环或非循环，总的合并起来就变成带头双向循环链表。

结点的初始化

一个单链表是由多个结点构成，而各个结点分开储存，在单链表的初始化时我们应该用动态内存为一个结点开辟一段空间，而单链表的结尾的标识为 NULL（空指针）。所以在开辟新节点的时候需要给结点赋值，并且把指向下结点的指针制空，这样最后一个结点就自动指向空指针了。

既然已经有结点了，那我们就可以开始搭建链表了。

增删

尾插

尾插其实对于单链表来说是相当痛苦的一件事，与顺序表不同单链表无法直接对尾部进行访问，于是每次插入都要先遍历一遍链表，再进行插入。

由于链表为空的情况下也是可以进行插入的，因此这个插入的函数并不需要对传入进来的地址进行断言。我们首先要先使用刚刚实现的函数创建一个新的结点，之后对链表是否为空进行判定。若为空则新的结点就变成第一个结点，若非空则把新节点链接到上一个的尾结点之后。由于单链表只能向后访问，所以循环在为空的上一位就应该停止了。

尾删

既然有尾插那自然也有尾删。

尾删与尾插稍稍有些许不同，它找的不是尾结点，而是尾结点的上一结点，为什么呢？让我们仔细想想：删除一个结点需要几个步骤？

结点作为一个动态内存，我们不使用了之后就应该将其 free ，避免导致内存泄漏。与此同时上一个结点是不是还保留着指向这块空间的指针？在我们已经将该空间释放的情况下，这个指针就变成野指针了，在以后的使用中若对其解引用，则会使程序出现错误。

同时在整个函数的开头，我们还要再进行对传入指针的断言。你想：要是一个链表已经没有内容了，你还要进行删除操作，从本质上那不就错了吗？所以传入这个函数的参数不可以有空指针。

头插

头插可谓是单链表的强项了，我们知道在顺序表中进行头插是十分麻烦的，还要将后面的数据往后挪动，但在单链表这个结构中头插只需将一个新建的结点指向原本的头结点，之后把原来的头结点转换到新的这个结点来就可以了。

值得注意的是，这里传的值都是二级指针，我们都知道在函数调用的时候形参是实参的一份临时拷贝，形参的改变并不会影响实参，只有使用指向实参的地址才能在调用外部函数的时候才能对实参直接进行更改。在头插的这个这个函数里面我们需要对头结点进行更改，而头结点的数据类型是结构体指针，既然如此在这里我们便无法使用结构体指针去改变一个结构体指针，所以需要传指向这个结构体指针的指针，即二级指针。

不使用二级指针也不是不行，只不过要设置一个返回值，返回更改后的头结点，并在主函数接收，这样程序就相对变得比较麻烦。

头删

有了上面几个函数的经验，头删这个操作也不会难到哪里去，首先先断言避免空指针进行下一步操作，之后先存下下一个结点的地址，之后释放头结点、调整头结点的位置，就完成头删操作了。

 做个小提示：每次写完一个函数时都应该使用看看，避免全写完函数太多找不到出错的位置在哪。

打印

这个方面只能说是各取所需，需要打印出什么格式就打印什么格式，我就实现最普通的一种就好了。

断言避免对空指针解引用，打印一个之后迭代继续，直到链表结束（即NULL)。

查找

 对于查找，无论是顺序表还是链表都摆脱不了需要遍历一遍的事实，毕竟你不遍历怎么查找数据呢。这个过程也很直接，先断言 毕竟一个空指针有什么好查找的。直到找到目标数据后返回该结点的地址。

在指定位置后的插入

实现这个函数前需要传入一个指向链表中某个数据的地址，而后我们找到这个地址，并创建一个新结点，让 pos 这个结点指向新节点，而新节点指向原来 pos 的下一个结点，这样便完成了一个新结点的插入。

 删除指定位置下一个结点的数据

首先对pos断言避免是空指针，之后判断pos的下一位是不是空指针，如果是空指针也没什么好删的，就不做处理了。若不是空指针，则记录要删除的结点，并让pos与下下个结点进行链接，最后再释放目标结点。（若先释放结点再链接则会出现越界访问，因此值得留意）

销毁

当我们不再使用这个链表，从内存角度考虑同时也是对应动态内存有申请就有释放的规则，所以对单链表的销毁是十分重要的。

首先还是要先断言避免删到空指针，采用的是存储下一个地址然后把上一个删掉的方法。记得要先存储再释放不然就找不到下一个结点了。

 与顺序表的对比

这里可能有人不知道什么叫做缓存利用率，简单解释一下，CPU在访问一块内存数据的时候会先去缓存之中寻找是否有目标数据，若没有就会先将其加载到缓存之中再进行访问，而为了运行的效率，会将目标数据周围一部分数据一并加载到缓存之中，但数据表的各个结点不是存储在一起的便无法享受到这种便利，相反顺序表就完美地契合了这个访问方式，因此其缓存利用率较高。

经过对比，可以看出顺序表优点的部分恰好就是链表的缺点，正是因为物理层面上没有存在一起，所以链表无法通过下标实现随机访问，也正是如此在插入数据时只需要简单地调换指针就可以实现。所以二者并没有孰强孰弱的概念，而是相辅相成的关系。只有更适合使用的场景。

总结

单链表跟顺序表一样都是一种数据结构，得利于其结构的不同，使其在头删和头插的实现中占据了得天独厚的优势，但与之而来的也有无法做到随机访问的缺点。因此要转变思路不能继续像思考顺序表的方式，去思考单链表，学会通过问题的转换来发挥其优势。

好了今天单链表定义的介绍及增删查改的实现，到这里就到一段落了，把源码放在下面，希望能帮到有需要的人。这篇博客完善了单链表一些不完善的地方【数据结构】带头双向循环链表的实现（C语言）。

源码

SListNode.h

#include "SListNode.h"
 
SListNode* BuySListNode(SLTDateType x)//创建新节点
{
	SListNode* p1 = (SListNode*)malloc(sizeof(SListNode)); //开辟空间
	if (p1 == NULL)   //判断是否为空
	{
		perror(malloc);
		exit(-1);
	}
	p1->data = x;    //赋值
	p1->next = NULL; //指向下一结点制空
	return p1;  //返回开辟新节点的地址
}
 
void SListPrint(SListNode* plist) //打印单链表
{
	while(plist)        //链表指向空指针时结束打印
	{
		printf("%d ", plist->data);
		plist = plist->next;           //迭代
	}
}
 
void SListPushBack(SListNode** pplist, SLTDateType x) //单链表尾插
{
	SListNode* newnode = BuySListNode(x);  //创建新结点
	if (*pplist == NULL)        //原链表为空
	{
		*pplist = newnode;      
	}
	else
	{
		SListNode* cur = *pplist;
		while (cur->next)      //找尾结点
		{
			cur = cur->next;
		}
		cur->next = newnode;   //链接
	}
}
 
 
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);      //断言空指针
	if ((*pplist)->next == NULL)   //考虑链表只有一个结点的情况
	{                              //防止对空指针解引用
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next->next)   //找尾结点的上一位
		{
			tail = tail->next;
		}
		free(tail->next);       //释放空间
		tail->next = NULL;     //尾指针下一指针制空
	}
}
 
void SListPushFront(SListNode** pplist, SLTDateType x)//单链表的头插
{
	SListNode* newnode = BuySListNode(x);   //创建新结点
	if (*pplist == NULL)         //判断为空的情况
	{
		*pplist = newnode;
	}
	else
	{ 
		newnode->next = *pplist;   //指向原来的头结点
		*pplist = newnode;       //更改新头结点
	}
}
 
 
void SListPopFront(SListNode** pplist)//单链表头删
{
	assert(*pplist);               //断言
	SListNode* next = (*pplist)->next;  //存储第二个结点
	free(*pplist);                 //释放空间
	*pplist = next;                //更改头结点
}
 
SListNode* SListFind(SListNode* plist, SLTDateType x)//单链表查找
{
	assert(plist);                //断言
	SListNode* cur = plist;       //设置变量遍历
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;           //返回地址
		}
		cur = cur->next;          //迭代
	}
	printf("找不到\n");
	return NULL;
}
 
void SListInsertAfter(SListNode* pos, SLTDateType x)//单链表在pos位置的后面插入
{
	assert(pos);                //断言
	SListNode* newnode = BuySListNode(x);       //创建新结点
	SListNode* nextnode = pos->next;            //找到下一结点
	pos->next = newnode;                        //链接
	newnode->next = nextnode;
}
 
void SListEraseAfter(SListNode* pos)//删除pos后的数据
{
	assert(pos);                    //断言
	if (pos->next != NULL)          //判断下一个结点不为空
	{
		SListNode* next = pos->next;  //指向下个结点
		pos->next = next->next;       //pos位置指向下下个结点
		free(next);                   //释放目标结点
	}
	else                              //不做处理
	{
		return;
	}
}
 
void SListDestroy(SListNode** plist)//销毁单链表
{
	assert(plist);                  //断言
	SListNode* cur = plist;         
	while (cur)
	{
		SListNode* next = cur->next;  //存储下一个结点
		free(cur);                    //释放上一个结点
		cur = next;                   //迭代
	}
	*plist = NULL;
}

 SListNode.c

#pragma once
 
#include
#include
#include
 
typedef  int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
 
SListNode* BuySListNode(SLTDateType x);
void SListPrint(SListNode* plist);
void SListPushBack(SListNode** pplist, SLTDateType x);
void SListPopBack(SListNode** pplist);
void SListPushFront(SListNode** pplist, SLTDateType x);
void SListPopFront(SListNode** pplist);
SListNode* SListFind(SListNode* plist, SLTDateType x);
void SListInsertAfter(SListNode* pos, SLTDateType x);
void SListEraseAfter(SListNode* pos);
void SListDestroy(SListNode** plist);