1.?? ?无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.?? ?带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。?

单链表的实现

单链表的定义

//定义单链表
typedef int SLTDataType;//方便修改存储数据类型

typedef struct SlistNode//节点
{
	SLTDataType data;//数据域
	struct SlistNode* next;//指针域
}SLTNode;//结构名改短一点

单链表的空间开辟


//单链表的空间开辟
SLTNode* BuySLTNode(SLTDataType el)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//开辟新节点,判断是否错误
	if (newnode == NULL)
	{
		perror("错误原因");
		exit(-1);
	}
	//给新节点的数据域和指针域分别赋值
	newnode->data = el;
	newnode->next = NULL;
	return newnode;
}

单链表的尾插

?????

//单链表的尾插
void SListPushBack(SLTNode** pphead, SLTDataType el)
{
	//0节点
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = BuySLTNode(el);
	}
	else
	{
		//找到尾结点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//到尾了,开辟空间
		SLTNode* newnode = BuySLTNode(el);
		//连接
		tail->next = newnode;

	}

}

尾插思路:

1.找到尾结点

2.到尾了,开辟空间

3.连接新开辟的空间

单链表的头插


//单链表的头插
void SListPushFront(SLTNode** pphead, SLTDataType el)
{
	assert(pphead);//0节点
	//创建新节点
	SLTNode* newnode = BuySLTNode(el);
	//新节点连接原来的头结点
	newnode->next = *pphead;
	//*pphead指向新节点
	*pphead = newnode;
}

头插思路:

1.创建新节点

2.新节点连接原来的头结点

3.*pphead指向新节点

单链表的打印

//单链表的数据打印--for遍历
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

打印思路:用for语句打印输出

单链表的尾删

//单链表的尾删
void SListPopBack(SLTNode** pphead)
{
    assert(pphead);//0节点
	// 温柔的一点
	/*if (*pphead == NULL)
	{
	return;
	}*/

	// 粗暴一点
	assert(*pphead);//1节点
	//两种情况:
	//1个节点
	//2个节点以上
	if ((*pphead)->next == NULL)//只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多节点时 找倒数第二个节点
	SLTNode* cur = *pphead;
	while (cur->next->next != NULL)
	{
		cur = cur->next;
	}
	//free去掉最后一个节点
	free(cur->next);
    //置NULL
	cur->next = NULL;

}

尾删思路:

2种情况

一个节点时,释放且置空

多节点时:

1.找倒数第二个节点

2.free最后一个节点

3.置空

单链表头删

//单链表的头删
void SListPopFront(SLTNode** pphead)
{	
	assert(*pphead);//0节点
    assert(*pphead);//1节点
	SLTNode* next = (*pphead)->next;//记住第二个节点地址
	free(*pphead);//释放第一个节点
	*pphead = next;//连接第二个节点
}

头删思路:

1.记住第二个节点地址

2.释放第一个节点

3.链接第二个节点

单链表的值查找:


//单链表的值查找操作
SLTNode* SListFind(SLTNode* phead, SLTDataType el)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == el)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}

	return NULL;
}

值查找思路:调试几遍

单链表的在pos位置删除

//单链表在pos位置删除
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);//0节点情况
	assert(pos);//防止向空链表删除

//1个节点直接头删
	if (*pphead == pos)
	{
		/*pphead=pos->next;
		free(pos);*/
		SlistPopFront(pphead);
	}
//多个节点时
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)//找到pos前位置
		{
			prev = prev->next;
		}
		prev->next = pos->next;//链接目标节点前后
		free(pos);//销毁目标节点
	}
}

pos位置删除思路:

1个节点:直接头删

多个节点:

1.找到pos位置

2.链接目标节点前后位置

3.销毁目标节点

单链表pos位置删除图片

单链表在pos位置插入

//单链表在pos位置前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//防止空节点情况
	assert(pos);//防止向空链表插入

	SLTNode* newnode = BuylistNode(x);
	//一个节点,头插
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	
	}
    //多个节点
	else
	{
		//找到pos的前一个位置
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
        //链接
		posPrev->next = newnode;
		newnode->next = pos;
	}
}