【手撕数据结构】拿捏单链表

单链表介绍

单链表也叫做无头单向非循环链表，链表也是一种线性结构。他在逻辑结构上一定连续，但是在物理结构上不一定连续(随机开辟空间),链表由一个或多个节点足够，每个节点由两部分组成，一个是存储的数据，一个是指向下一个节点的指针。

链表的初始化

typedef int SLTDataType;	//方便以后修改存储数据类型typedef struct SListNode
{SLTDataType val;struct SListNode* next;
}SLTNode;

打印链表

void SLTPrint(SLTNode* phead)
{assert(phead);SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->val);pcur = pcur->next;}printf("NULL");
}

这里就直接依次打印元素即可,我们习惯不动头结点，所以创建一个变量存储头结点来遍历

增加节点

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc failed");exit(1);}else{newnode->val = x;newnode->next = NULL;}return newnode;
}

因为我们每次插入不管是头插还是尾插，都要创建一个新的节点，我们不妨封装一个函数专用

尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//链表和顺序表不一样不是每次2倍申请空间，而是来一个数据申请一个空间SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* pcur = *pphead;/*while (pcur){pcur = pcur->next;}pcur = newnode;*/	//这种写法虽然找到了插入节点的位置，但是无法修改上一个节点的next指针while (pcur->next){pcur = pcur->next;	//这里就找到了插入节点的位置}pcur->next = newnode;//并且修改了上一个节点的指针}
}片

这里要做的就是两点，找到旧的尾节点，将旧的尾节点指针指向新的尾节点，然后将新的尾节点插入;

注：新结点创建的时候指针域就已经置空，所以尾插时不需要再将新结点的指针域置空。还有就是如果只有一个节点，那么就可以直接插入

头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);/*if (*pphead == NULL){*pphead = newnode;}else{SLTNode* pcur = *pphead;*pphead = newnode;(*pphead)->next = pcur;}*///优化版本newnode->next = *pphead;	//这里就巧妙用了SLTBuyNode函数创建节点时候将next指针设置为NULL特性,//反正newonde是在一个固定的位置插入，不用像尾插一样遍历，而插入节点我们现在只需要改变next指针//在改变原来的头结点之前把新头结点的next指向旧头结点，再更新头结点*pphead = newnode;

这里可以看优化版本，可以不处理链表为空的情况，因为我们总是在头结点的位置插入，只需要把新头节点的指针指向旧头结点，然后取代旧头结点

再给定位置之后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);SLTNode* Next = pos->next;if (Next){pos->next = newnode;newnode->next = Next;}else{pos->next = newnode;}//优化版本//assert(pos);//SLTNode* newnode = SLTBuyNode(x);//newnode->next = pos->next;//pos->next = newnode;		//这种也可以同时处理一个节点和多个节点情况
}

这里也建议使用优化版本，不用看考虑只有一个节点的情况，插入就是把新节点的指针指向原来插入位置之后的节点，然后把指定位置的nxet指针指向2新节点。

在给定位置之前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);/*SLTNode* ret = SLTFind(pos,pos->val);assert(ret != NULL);*/assert(pos);	//外面用查找函数返回值即可SLTNode* newnode = SLTBuyNode(x);SLTNode* pcur = *pphead;if (pcur->next == NULL){SLTPushFront(pphead,x);}else{while (pcur->next != pos){pcur = pcur->next;}pcur->next = newnode;newnode->next = pos;}}

这里要注意的是，在给定位置之前插入数据，我们就要先找到给定位置之前的那个节点，将那个节点的next指针指向插入的节点，再将插入的节点next指针指向给定位置的节点即可。但是如果链表只有一个元素，那么我们永远找不到给定位置之前的节点，pcur->next!=pos恒成立，所以单独处理，一个节点之前插入，相当于头插，只需要调用头插函数即可

删除节点

尾删

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);	//*pphead链表不能为空SLTNode* pcur = *pphead;if ((*pphead)->next == NULL)	//如果只有一个节点，则无需考虑next指针{free(*pphead);*pphead = NULL;}else{/*while (pcur->next){pcur = pcur->next;}free(pcur);pcur == NULL;*///上面不能写的原因是,虽然找到了尾节点并释放，但是前一个节点的next指针依然指向尾节点//导致下一次删除尾节点时，对一块释放的空间访问，这里把pucr尾节点设置NULL不代表上一个节点的值为NULL，他的值依然是这块被释放的空间while (pcur->next->next)//找到尾节点之前的节点{pcur = pcur->next;}SLTNode* del = pcur->next;		//因为循环只能找到尾节点之前的节点,释放尾节点之前，把尾节点存起来free(del);del = NULL;pcur->next = NULL;}
}

这里要注意，我们先找到尾节点并释放那块内存空间，但是上一个节点的next指针也要记得设置NULL,不然他依然指向这块被释放的空间.

头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}

头删与尾删的区别是不需要考虑被删除节点的next指针，因为单链表是向后遍历的，头删的next指针并不会影响新的链表的遍历,所以我们只需找到旧头节点的下一个节点作为新的头节点，把原来的头节点释放即可

删除给定位置的节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);	//*pphead不为空链表assert(pos);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else if (*pphead == pos){*pphead = (*pphead)->next;free(pos);pos = NULL;}else{SLTNode* Next = pos->next;SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}free(pos);pos = NULL;pcur->next = Next;}//优化版本//if (pos == *pphead)//{//	SLTPopFront(pphead);	//头删既可以解决只有一个节点，又可以解决指定节点与头结点相同//}//else//{//	SLTNode* prev = *pphead;//	while (prev->next != pos)	//这里不能处理头节点与指点节点相同情况//	{//		prev = prev->next;//	}//	prev pos pos->next//	prev->next = pos->next;//	free(pos);//	pos = NULL;//}}

要删除给定位置的节点之前要先判断这个节点是否在链表中存在(SLTFind)方法 提供pos参数,这里通常只需要找到给定位置之前的节点，然后将其的next指针指向给定位置之后的节点即可.但是有两种情况需要单独处理，第一种情况就是链表只有一个节点时，只需要直接头删即可，第二种情况就是链表有多个节点，我们要删除头结点，这样的我们永远找不到给定位置之前的节点,pcur->next != pos恒成立,这种情况也可以通过头删函数解决

删除给定位置之后的节点

void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);//pos->next = pos->next->next;		//free(pos->next);//pos->next = NULL;SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

注意:不能像注释那样写的原因：

查找节点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->val == x){return pcur;}pcur = pcur->next;}return NULL;
}

只需要从头节点开始遍历查找即可，如果找到了就返回该节点，如果到NULL,返回null;