目录

首先讲解一下什么是链表

数组与链表的区别

定义链表

链表的扩容

链表的尾插

链表的头插

链表的尾删

 链表的头删

链表的查找

 链表的任意位置插入（在pos位置之前插入）

链表的任意位置删除（删除pos位置的值）

链表的任意位置插入（在pos位置之后插入）

链表的任意位置删除（删除pos位置之后的值）

首先讲解一下什么是链表

这里大家可以看一下这张图，这便是链表的大致结构

这张图描述了链表的内部结构

 从上图可知，可以定义一个结构，一部分存放数据，一部分指下一个节点的指针，这就构成了单链表

当然如果增加指向上一节点的指针，就变成双链表

当然这里我主要为大家讲解一下单链表，双链表其实同理

数组与链表的区别

数组：空间连续，大小固定，要么不够用，要么浪费

链表：空间不连续，大小可根据动态变化

定义链表

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTlist;

 这里使用了（typedef int SLTDataType;）这是为了到时链表里存的不是int类型，方便修改

链表的扩容

SLTlist* buySLTlist(SLTDataType x)
{
	SLTlist* newnode = (SLTlist*)malloc(sizeof(SLTlist));
	assert(newnode);
	newnode->data = x;
	return newnode;
}

这里为什么要把这的函数放在最前面，因为扩容会在后面被其他函数调用，所以把它放在最前面。

链表的尾插

void SListPushBack(SLTlist** pphead, SLTDataType x)
{
	SLTlist* newnode = (SLTlist*)malloc(sizeof(SLTlist));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTlist* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
	return;

 当然看代码有点难理解，下面我用图画演示一遍

假如要在这后面加入一个node4节点，可按如下操作

链表的头插

void SListpushfrond(SLTlist** pphead, SLTDataType x)
{
	SLTlist* newnode=buySLTlist(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头插就非常简单，当然我也会用图给大家演示一下

现在我们要将node4插在头上，可以如下操作（就是只用将node4指向头指针，然后将头指针更新为node4，就可以了）

 下面进入链表的删除

链表的尾删

void SListPopBack(SLTlist** pphead)
{
	SLTlist* cur = *pphead;
	if (cur==NULL)
	{
		printf("链表为空n");
		return;
	}
	if (cur->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	while (cur->next->next!= NULL)
	{
		cur = cur->next;
	}
	free(cur->next);
	cur->next = NULL;	
}

图片演示

 这个其实就是先要找到尾节点的前一个，然后让尾节点的前一个指向空

 链表的头删

void SListpushfrond(SLTlist** pphead)
{
	SLTlist* cur = *pphead;
	if (cur== NULL)
	{
		printf("链表为空n");
		return;
	}
	*pphead = (*pphead)->next;
	free(cur);
	return;
}

 头删其实更简单，只需要将头指针更新为原头指针指向的下一个，就是说把头指针更新为node2

链表的查找

SLTlist* SListfind(SLTlist* phead, SLTDataType x)
{
	SLTlist* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return 0;
}

 链表的任意位置插入（在pos位置之前插入）

void SListInset(SLTlist** pphead, SLTlist* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);
	if (pos == *pphead)
	{
		SListpushfrond(&(*pphead),x);
		return;
	}
	SLTlist* newnode = buySLTlist(x);
	SLTlist* cur = *pphead;
	while (cur->next != pos)
	{
		cur = cur->next;
	}
	cur->next = newnode;
	newnode->next = pos;
	return;
}

图片演示

 这个的思路其实是，首先找到pos的前一个结点，然后使其指向node2，并使node2指向pos

链表的任意位置删除（删除pos位置的值）

void SListErase(SLTlist** pphead, SLTlist* pos)
{
	if (pos == *pphead)
	{
		SListpushfrond(&(*pphead));
		return;
	}
	SLTlist* cur = *pphead;
	while (cur->next != pos)
	{
		cur = cur->next;
	}
	SLTlist* tail = cur->next;
	cur->next = cur->next->next;
	free(tail);
	return;
}

 图片演示

思路是使pos的前一个节点 指向pos的后一个节点

链表的任意位置插入（在pos位置之后插入）

void SListInsetAfter(SLTlist** pphead, SLTlist* pos, SLTDataType x)
{
	assert(pos);
	SLTlist* newnode = buySLTlist(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

这个其实和上面的那个相似，并且更加简单

链表的任意位置删除（删除pos位置之后的值）

void SListEraseAfter(SLTlist** pphead, SLTlist* pos)
{
	assert(pphead);
	assert(pos->next);
	SLTlist* cur = pos->next;
	pos->next = pos->next->next;
	free(cur);
	return;
}

到这里单链表的基本功能基本实现，如有不当，欢迎大家提出！！！