单链表任意位置插入删除

「这是我参与2022首次更文挑战的第5天，活动详情查看：2022首次更文挑战」

09.在pos位置前插入

思路：

遍历链表，找到pos位置之前的结点(pre->next == pos)，pos前一个结点的next链接新结点，新结点的next链接pos

注意：假如pos为头结点，不能找到pos位置之前的结点，所以，只有一个节点时，要单独判断！

• 只有一个结点：相当于头插，可以直接调用头插的接口 。新结点的next链接pos，然后头指针指向新结点，新结点成为新的头

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	assert(*pphead);//防止为空链表
	SLTNode* newnode = BuyList(x);
	//找到pos的前一个结点
	//如果pos为第一个结点，第一个结点没有前一个结点，所以会有问题
	//单独判断
	if (*pphead == pos)
	{
        //新结点的next链接头结点
		newnode->next = *pphead;
        //头指针指向新结点，新结点成为新的头
		*pphead = newnode;
	}
	else
	{
		SLTNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		//跳出循环，此时pre就是pos的前一个结点
		//pos前一个结点的next链接新结点，新结点的next链接pos
		pre->next = newnode;
		newnode->next = pos;
	}
}

10.删除pos位置结点

思路：找到pos位置前后的两个位置进行连接

pos后一个位置：pos->next

但是找pos前一个位置，需要遍历链表进行查找

同上面的情况，如果pos为头结点的话，找不到它的前一个位置，所以需要单独处理

• 情况1：只有一个结点
  • 释放掉头结点，然后把头指针置空

• 情况2：多个结点
  • 保存pos位置的下一个结点next，遍历链表找到pos位置的前一个结点prev。释放pos位置的结点，然后前一个结点的next链接后一个结点

//删除pos位置的结点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);//防止链表为空
	//找到pos位置的前一个结点和下一个结点进行链接
	//注意：如果只有一个结点，没有前一个结点，要进行单独判断
	
	//情况1:删除的是第一个结点
	if ((*pphead) == pos)
	{
		*pphead  = pos->next; //第二个结点成为新的头
		free(pos);
	}
	else
	{
		SLTNode* next = pos->next;//保存下一个结点
		//遍历找上一个结点
		SLTNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		free(pos);
		//pos上一个结点链接下一个结点
		pre->next = next;
	}
}

11.删除pos位置后结点

思路：保存pos位置后的结点的下一个结点next

释放掉pos位置后的结点

然后pos结点的next指针链接next结点

**注意：不要直接写成：pos->next->next **，防止pos为尾结点时，pos->next 为空指针，然后再pos->next->next 相当于堆空指针解引用

所以：如果pos为尾结点时，不删除 (进行断言或者判断)

void SListEraseAfter(SLTNode* pos)
{
	//删除pos位置后一个结点，要防止pos是尾结点(即pos->next == NULL
	assert(pos->next);
	//保存pos位置后的结点的下一个结点
	SLTNode* next = pos->next->next; //上述代码就起作用了，如果pos->next为空
	//pos->next ->next 就是相当于对空指针解引用


	free(pos->next);
	//pos的next链接pos位置后的结点的下一个结点
	pos ->next = next;
}

12.销毁单链表

由于每个结点都是动态开辟的，所以需要逐个释放。由于释放了就找不到下一个结点。所以先保存下一个结点。然后再释放。以此迭代，直到链表为空

void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	//每个结点都是动态开辟的，所以要一个一个的释放
	//释放前要保存下一个结点，不然找不到了
	SLTNode* cur = *pphead; 
	while (cur)
	{
		SLTNode* next = cur->next;//保存下一个结点
		free(cur);
		cur = next;//把下一个结点赋给cur
	}
	*pphead = NULL;//最后把头指针置空
}