敞开掘金成长之旅！这是我参加「掘金日新计划 2 月更文挑战」的第 1 天，点击检查活动概况

前语

回顾之前的顺序表，咱们发现就算是动态扩容，咱们也都是成倍的括，也或许存在空间糟蹋，并且顺序表的头插头删还十分麻烦，需求移动数据。而链表的存在就处理了头插头删以及空间糟蹋这一问题，说到链表，咱们脑海中就会浮现出一个链条把东西都链接起来。

链表

链表是一种物理存储结构上非接连、非顺序的存储结构，数据元素的逻辑顺序是经过链表中的指针链接次第完成的。这儿所谓的逻辑结构，其实就是为了便利了解，然后加上箭头用来表明关系的，但实际上并不存在箭头。

咱们发现，链式结构其实就是在该节点寄存下一个节点的地址，然后经过地址便能够访问到该节点的下一个节点。而上图中的箭头，仅仅为了便利了解，一个一个连接起来，但实际上是并不存在的。(逻辑结构)

因而，链式结构在逻辑上是接连的（如上图经过箭头链接起来），但在物理地址上却不必定接连。由于每一个节点都是在堆上拓荒空间，拓荒空间的地址有或许接连，又或许不接连。

链表种类

链表主要分为以下几类：单向与双向、带头与不带头、循环与非循环，而经过这三类的组合，又分为八种方式的链表：带头单向循环链表、带头单向不循环……

而咱们本次章节研讨的就是不带头单向非循环链表。把这一个连接后，后边的其它种类的链表就很好了解与完成了

接口完成

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//数据
	struct SListNode* next;//指向下一个结构体的指针
}SListNode;

动态请求节点

动态请求节点其实就是在堆上malloc出一块空间，并把数据data寄存在该节点中。由于后边的刺进操作都需求进行拓荒新空间，所以这儿单独给写了出来，后边用到的时分直接调用即可

//动态请求节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode*newnode=(SListNode*)malloc(sizeof(SListNode));//malloc空间
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;//将数据放在该节点的data
	newnode->next = NULL;//next置为空（防止野指针）
	return newnode;//回来新节点
}

尾插与尾删

尾插仍是需求进行画图，这样才干更好的了解

但是这儿假设传来的是个空指针，即假设是一个空的链表，那尾插时这个新节点就作为头节点来运用。（特殊情况）

//尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	//动态请求一个新节点
	SListNode* newnode = BuySListNode(x);
	//空表
	if (*pplist == NULL)
	{
		//这儿改动List，传址调用、形参是实参的临时复制，形参的修正不会影响实参，所以传List的地址，即用二级指针变量来接纳一级指针的地址，这时解引用后就会影响到List
		*pplist = newnode;
	}
	else
	{	//找尾巴
		SListNode* ptail = *pplist;
		//这儿修正的是结构体成员变量，所以不用二级指针
		while (ptail->next != NULL)
		{
			ptail = ptail->next;
		}
		//将节点接在尾巴上
		ptail->next = newnode;
	}
}

这儿需求留意的是，我是在外面定义的是一个结构体指针，要对此进行修正，有必要传址调用，由于传值调用形参的改动不会影响实参。而进行修正后（空表情况下进行尾插），后边的再次尾插其实改动的就不是该变量了，而是该变量的结构体成员next，以及next节点指向的data

尾删画图处理一切。

这儿需求留意的就是，假设只要一个节点的情况下，该节点的next就是空指针，然后再next就形成了空指针的解引用操作（NULL->next）这是错误的，所以咱们要考虑到只剩一个节点的特殊情况，另外，还要留意空表状况是不可删去的。

//尾删
void SListPopBack(SListNode** pplist)
{
	//空表不可进行删去，所以加个断言
	assert(*pplist);
	//只要一个数据时直接把该节点开释，然后置空即可
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* ptail = *pplist;//本意即SListNode*ptail=list
		//找到最终一个的前一个
		while (ptail->next->next!=NULL)
		{
			ptail = ptail->next;
		}
		//开释最终一个节点
		free(ptail->next);
		//并把指向最终一个节点的next置空（不置空就是野指针了，由于虽然开释了那块空间，但是它的前一个节点的next依然指向它）
		ptail->next = NULL;
	}
}

打印

这儿咱们写一个打印的接口，便利咱们调查。也很简单，遍历整个链表即可。

//单链表打印
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	//留意这儿是cur！=NULL，由于假设是cur->next ！=NULL的话，最终一个节点的数据不会被打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
}

这儿咱们来测验一下前面的尾插与尾删操作。

void SListTest2()
{
	SListNode* list = NULL;
	//传址调用，解引用后形参的修正会影响实参
	SListPushBack(&list, 0);
	//SListPrint(list);//0->NULL
	SListPushBack(&list, 1);
	SListPushBack(&list, 2);
	SListPushBack(&list, 3);
	SListPushBack(&list, 4);
	//打印
	//SListPrint(list);//0->1->2->3->4->NULL
	//尾删
	SListPopBack(&list);
	//SListPrint(list);//0->1->2->3->NULL
	SListPopBack(&list);
	SListPopBack(&list);
	SListPopBack(&list);
	SListPopBack(&list);
	SListPrint(list);//NULL
	//空表进行删去
	SListPopBack(&list);//报错 error
}

经过测验咱们发现一切都在掌控之中，并没有什么问题。接下来完成头插与头删。

头插与头删

头插

单链表的头插最为简单，时刻复杂度达到了O（1）,仍是经过画图然后更好的了解。这儿只需求将新节点的next指向目前的头指针，然后头指针再更新为新节点即可。

//头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
    //留意这儿形参是二级指针，由于这儿改动的是list，并不是改动list指向的结构体成员，所以传地址，而一级指针的地址，就要用二级指针pplist接纳
	SListNode* newnode = BuySListNode(x);
		newnode->next =*pplist;
		*pplist = newnode;
}

咱们假定是个空链表，咱们发现头插也是适用的。因而就以上代码就够了。头删

这儿咱们需求留意的就是，空表不可进行删去，然后其他的画个图就一目了然，需求留意的是，这儿依然是改动的list，所以仍是用二级指针。

//头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	//先保存
	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}

测验

//头插头删
void SListTest3()
{
	//头插
	SListNode* list = NULL;
	SListPushFront(&list,1);
	//SListPrint(list);//1->NULL
	SListPushFront(&list, 2);
	SListPushFront(&list, 3);
	SListPushFront(&list, 4);
	//SListPrint(list);//4->3->2->1->NULL
	//头删
	SListPopFront(&list);
	//SListPrint(list);//3->2->1->NULL
	SListPopFront(&list);
	SListPopFront(&list);
	SListPopFront(&list);
	SListPrint(list);//NULL
	//SListPopFront(&list);//error(空表不可删去)
}

这儿咱们经过测验，进行调查发现没有什么问题，接下来是单链表的查找。

查找

查找操作也很简单，无非就是遍历整个链表，然后找到data时回来该节点指针即可，找不到就回来空指针。其实也能够这样来完成：

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	//while (cur)
	//{
	//	if (cur->data == x)
	//	{
	//		return cur;
	//	}
	//	cur = cur->next;
	//}
	//return NULL;
	//简化版本
	while (cur && cur->data != x)
	{
		cur = cur->next;
	}
	//完毕循环的条件，要么就是cur== NULL，说明找不到，或者就是cur->data==x,找到了，这儿直接回来cur就行。
	return cur;
}

恣意方位刺进与删去

pos方位进行刺进 思路都在图纸当中，画图会愈加简单了解！

//在pos方位刺进
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	if (*pplist == pos)
	{
		//头插
		SListPushFront(pplist, x);
	}
	else
	{
		SListNode* cur = *pplist;
		//找到pos节点之前的一个
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		//将新节点刺进在此
		SListNode* newnode = BuySListNode(x);
		//找到了pos方位之前的了
		cur->next = newnode;
		newnode->next = pos;
	}
}

pos方位进行删去

//删去pos方位
void SListErase(SListNode** pplist, SListNode* pos)
{
	assert(pos);
	//假设pos指向list
	if (pos == *pplist)
	{
		SListPopFront(pplist);
	}
	else
	{
		SListNode* cur = *pplist;
		//找到pos方位之前的
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

销毁

最终就是单链表的销毁，由于咱们知道，malloc、realloc、calloc这几个函数都是与free成对呈现的。不然会造成内存走漏。这儿咱们也是需求进行遍历每一个节点，然后进行删去，不过需求留意的是在删去该节点之前。要先记住下一个节点。

//单链表销毁
void SListDestroy(SListNode** pplist)
{
	SListNode* cur = *pplist;
	while(cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;//必定要置空，不然后边打印就是野指针的访问
}

总结

在这儿，必定要多画图，根据图形来理清思路，然后再进行写代码，一起必定要考虑考虑特殊情况，比方空表状况下能不能删去，比方free的时分会不会存在野指针，并且还主张大家边写边调试，不要一口气从尾插写完，要逐渐进行，慢便是快！

end 日子本来烦闷，但跑起来就会有风！❤

【线性表】—不带头单向非循环链表的增删查改

前语

接口完成

动态请求节点

尾插与尾删

打印

头插与头删

查找

恣意方位刺进与删去

销毁

总结

作者信息

推广

【线性表】—不带头单向非循环链表的增删查改

前语

接口完成

动态请求节点

尾插与尾删

打印

头插与头删

查找

恣意方位刺进与删去

销毁

总结

相关文章

[LeetCode] 1405. 最长快乐字符串

Key-Value Observing(KVO) 基本使用与实现原理

关于Android相册实现的一些经验

Java实现调用外部程序

作者信息

推广