C语言：手撕单链表

1.链表的概念

概念

链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。

链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只 需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。

⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状 态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？ 最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。

在链表⾥，每节“⻋厢”是什么样的呢？

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点” 节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。 图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA5。

为什么还需要指针变量来保存下⼀个节点的位置？ 链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针 变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。 结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码： 假设当前保存的节点为整型：

struct SListNode

{
 int data; //节点数据 
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数 据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。 当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个 节点的钥匙）就可以了。 给定的链表结构中，如何实现节点从头到尾的打印？

补充说明

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续 2、节点⼀般是从堆上申请的3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

2.手撕单链表

2.1说明

定义三个文件：

SingleLinkedList.h       SingleLinkedList.c       test.c

头文件用于包含要用到的库文件和定义链表节点的结构，及各类接口的声明

SingleLinkedList.c用于实现各类接口

test.c用于接口的测试

2.2尾插

头文件声明：
void SLLPushBack(SLLNode**pphead,SLLDataType x);

实现：
void SLLPushBack(SLLNode** pphead, SLLDataType x)
{
	assert(pphead);
	SLLNode* newnode = BuynewNode(x);
	if (*pphead == NULL)
	{

		*pphead = newnode;
	}
	else
	{
		SLLNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
	
}

首先我们添加断言，不能传空指针过来解引用，在尾插前我们先获取一个新节点见标题2.4

这里有两种情况，当链表为空时，我们直接让头结点*pphead指向新节点，

链表不空时，先定义一个尾巴节点，先让它指向头结点，开始遍历，链表，直到ptail找到最后一个链表节点停下来，然后将尾节点的next指针指向刚刚我们获得的新节点newnode。

2.3打印链表

那么在text.c中定义一个链表结构，然后尾插四个值打印出来看看：

首先，先看代码

头文件声明：
void SLLPrint(SLLNode* phead);

实现：
void SLLPrint(SLLNode* phead)
{
	SLLNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->x);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

test.c测试：
#include"SingleLinkedList.h"
void test01()
{
	//定义一个单链表
	SLLNode* s1=NULL;
	//尾插测试
	SLLPushBack(&s1, 1);
	SLLPushBack(&s1, 2);
	SLLPushBack(&s1, 3);
	SLLPushBack(&s1, 4);
	//打印链表
	SLLPrint(s1);
}
int main()
{
	test01();
	return 0;
}

运行结果：

2.4获取一个新节点

头文件声明：
SLLNode* BuynewNode(SLLDataType x);

实现：
SLLNode* BuynewNode( SLLDataType x)
{
	SLLNode* newnode = (SLLNode*)malloc(sizeof(SLLNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		return;
	}
	newnode->x = x;
	newnode->next = NULL;
	return newnode;
}

使用malloc函数申请一个链表节点大小的空间，给newnode，如果申请空间失败，我们直接退出，申请成功，那么将数据赋值给我们的newnode->x,并将next指针指向NULL。

2.5头插

头文件声明：
void SLLPushFront(SLLNode** pphead, SLLDataType x);

实现：
void SLLPushFront(SLLNode** pphead, SLLDataType x)
{
	assert(pphead);
	SLLNode* newnode = BuynewNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

如同尾插那样，先添加断言，防止传过来空指针解引用崩溃，

先获取一个新节点，然后将新节点的next指针指向我们的头结点，再将头结点指向新头插过来的newnode节点即可完成头插

不论链表有无数据都可以完成头插。

//头插测试
SLLPushFront(&s1, 5);
SLLPushFront(&s1, 6);
SLLPushFront(&s1, 7);
SLLPushFront(&s1, 8);

我们运行一下：

2.6尾删

头文件声明：
void SLLPopBack(SLLNode** pphead);

实现：
void SLLPopBack(SLLNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLLNode* prev = *pphead;
		SLLNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
	
}

先添加断言，不能传空指针过来，其次，链表必须至少有一个节点，没节点不能进行尾删

两种情况：

第一种，当链表只存在一个节点，直接进行头结点释放空间，将头结点*pphead指向NULL；

第二种，当链表存在多个节点，我们先定义一个前驱指针prev，和找尾指针ptail，都先指向*pphead头指针，然后进行循环找链表的尾巴，再每次指向新尾巴的前一步，我们让前驱指针prev先指向ptail，这样循环完毕，我们可以得到倒数第一个节点（即尾节点）和倒数第二个节点，然后将倒数第二个节点的next指针指向NULL，将ptail空间释放，ptail指向NULL，完成尾删

看下列图示：

//定义一个单链表
SLLNode* s1=NULL;
//尾插测试
SLLPushBack(&s1, 1);
SLLPushBack(&s1, 2);
SLLPushBack(&s1, 3);
SLLPushBack(&s1, 4);

//头插测试
SLLPushFront(&s1, 5);
SLLPushFront(&s1, 6);
SLLPushFront(&s1, 7);
SLLPushFront(&s1, 8);

//尾删测试
SLLPopBack(&s1);
SLLPopBack(&s1);
SLLPopBack(&s1);
SLLPopBack(&s1);

运行一下：

2.7头删

头文件声明：
void SLLPopFront(SLLNode** pphead);

实现：
void SLLPopFront(SLLNode** pphead)
{
	assert(pphead && *pphead);
	SLLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

先添加断言，不能传空指针过来，其次，链表必须至少有一个节点，没节点不能进行头删

先将头结点的下一个节点用保存起来，这里我们定义一个next指针指向*pphead的下一个节点

然后释放头结点，将头结点*pphead指向next，让next成为新的头节点，从而完成头删。

	//定义一个单链表
	SLLNode* s1=NULL;
	//尾插测试
	SLLPushBack(&s1, 1);
	SLLPushBack(&s1, 2);
	SLLPushBack(&s1, 3);
	SLLPushBack(&s1, 4);

	//头插测试
	SLLPushFront(&s1, 5);
	SLLPushFront(&s1, 6);
	SLLPushFront(&s1, 7);
	SLLPushFront(&s1, 8);


	//头删测试
	SLLPopFront(&s1);
	SLLPopFront(&s1);
	SLLPopFront(&s1);
	SLLPopFront(&s1);

运行一下：

2.8查找

头文件声明：
SLLNode* SLLFind(SLLNode* phead, SLLDataType x);

实现：
SLLNode* SLLFind(SLLNode* phead, SLLDataType x)
{
	assert(phead);
	SLLNode* pcur = phead;
	while (pcur)
	{
		if (pcur->x == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

链表不能为空，由于我们只是找值，不改值，所以，传一级指针，如果要找的数据x链表中存在就返回该数据所在节点，否则就返回NULL

//查找测试
SLLNode*find=SLLFind(s1, 3);
if (find != NULL)
{
	printf("找到了!\n");
}
else
{
	printf("找不到!\n");
}

运行一下：

2.9在指定位置之前插入数据

头文件声明：
void SLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x);

void SLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x)
{
	assert(pphead&&*pphead);
	assert(pos);
	SLLNode* newnode = BuynewNode(x);
	if (*pphead==pos)
	{
		SLLPushFront(pphead, x);
	}
	else
	{
		SLLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
	
}

先添加断言，不能传空指针过来解引用，链表不能为空，否则指定位置就没有意义，其次，指定位置pos不能为空

先获取一个新节点，这里有两种情况，

第一种：当头结点与pos位置相同时，那么pos位置之前插入数据，就是头插，我们直接调用刚刚写的头插接口即可

第二种：当链表有多个节点时，我们先找到pos位置的前一个节点，那么这里定义一个前驱指针prev先指向头节点*pphead，然后开始遍历直到在pos位置的前一个节点停下来，然后让新节点的next指针指向pos，再将prev的next指针指向新节点，完成插入，图示如下：

第一种：

第二种：

	//查找测试
	SLLNode*find=SLLFind(s1, 3);
//在指定位置之前插入数据测试
SLLInsert(&s1, find, 55);

运行一下：

2.10在指定位置之后插入数据

头文件声明：
void SLLInsertAfter( SLLNode* pos, SLLDataType x);

实现：
void SLLInsertAfter(SLLNode* pos, SLLDataType x)
{
	assert(pos);
	SLLNode* newnode = BuynewNode(x);
	SLLNode* next = pos->next;

	newnode->next = next;
	pos->next = newnode;
}

由于是在pos位置后面插入数据，所以只需要一个pos位置的节点指针就可以，不需要传头节点

断言pos指针不可为空，先获取一个新节点，然后先找到pos的下一位置，我们定义一个指针next存放pos的下一位置，让newnode新节点的next指针指向next，然后吧pos的next指针指向newnode新节点，图示如下：

//查找测试
SLLNode*find=SLLFind(s1, 3);
//在指定位置之后插入数据
SLLInsertAfter(find, 68 );
	

运行一下：

2.11删除指定位置之后的数据

头文件声明：
void SLLEraseAfter(SLLNode* pos);

实现：
void SLLEraseAfter(SLLNode* pos)
{
	assert(pos&&pos->next);
	SLLNode* del = pos->next;
	pos->next=del->next;
	free(del);
	del = NULL;
}

断言pos位置，不可为空指针，且pos后面得有数据才能进行删除

先将pos下一位置存起来，这里我们定义一个del指针指向pos->next

然后将pos的next指针指向del的下一节点即指向del->next

然后释放del(pos后面的节点)

将del置为NULL

图示如下：

//查找测试
SLLNode*find=SLLFind(s1, 3);	
//删除指定位置之后的数据
	SLLEraseAfter(find);

运行一下：

2.12删除指定位置的数据

头文件声明：
void SLLErase(SLLNode**pphead,SLLNode* pos);

实现：
void SLLErase(SLLNode** pphead, SLLNode* pos)
{
	assert(pphead&&*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLLPopFront(pphead);
	}
	else
	{
		SLLNode* del = pos;
		SLLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = del->next;
		free(pos);
		pos = NULL;
	}
	
}

断言不可传入空指针，链表不可为空，pos指针也不能为空

这里有两种情况：

第一种：当头结点和pos位置相同时：我们直接调用先前写的头删的接口

第二种：当链表有多个节点时，定义一个del指针指向pos位置

定义一个前驱指针prev先指向头结点，然后开始遍历prev指针，直到找到pos的前一个位置停下来，此时将prev的next指针指向del的下一节点，即指向del->nex,然后释放pos指向的空间，pos置为NULL；

图示如下：

第一种：

第二种：

//查找测试
SLLNode*find=SLLFind(s1, 3);
	//删除指定位置的数据
	SLLErase(&s1,find);

运行一下：

2.13销毁链表

头文件声明：
void SLLDestroy(SLLNode**pphead);

实现：
void SLLDestroy(SLLNode** pphead)
{
	assert(pphead && *pphead);
	while (*pphead)
	{
		SLLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;	
	}

}

链表的销毁：需要我们一个一个节点的释放，当所有节点都释放完毕，从而达到链表的销毁的目的，一开始我们先断言，不可传入空指针进行解引用，且链表非空的情况下

开始遍历头结点，在循环体内定义一个next指针，每次都保存头节点的下一节点，这样在释放完头结点，让头结找到链表的下一节点，直到next和*pphead都走到NULL为止

图示如下：

销毁前：

		//定义一个单链表
	SLLNode* s1=NULL;
	//尾插测试
	SLLPushBack(&s1, 1);
	SLLPushBack(&s1, 2);
	SLLPushBack(&s1, 3);
	SLLPushBack(&s1, 4);
//打印链表
	SLLPrint(s1);

	//销毁链表
	SLLDestroy(&s1);
	打印链表
	SLLPrint(s1);

销毁后：

2.14完整源码

SingleLinkedList.h文件：
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLLDataType;
typedef struct _SingleLinkedListNode
{
	SLLDataType x;
	struct _SingleLinkedListNode* next;
}SLLNode;
//获取一个新节点
SLLNode* BuynewNode(SLLDataType x);
//尾插
void SLLPushBack(SLLNode**pphead,SLLDataType x);
//头插
void SLLPushFront(SLLNode** pphead, SLLDataType x);
//尾删
void SLLPopBack(SLLNode** pphead);
//头删
void SLLPopFront(SLLNode** pphead);
//查找
SLLNode* SLLFind(SLLNode* phead, SLLDataType x);
//在指定位置之前插入数据
void SLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x);
//在指定位置之后插入数据
void SLLInsertAfter( SLLNode* pos, SLLDataType x);
//删除指定位置之后的数据
void SLLEraseAfter(SLLNode* pos);
//删除指定位置的数据
void SLLErase(SLLNode**pphead,SLLNode* pos);
//打印链表
void SLLPrint(SLLNode* phead);
//销毁链表
void SLLDestroy(SLLNode**pphead);

SingleLinkedList.c文件：
#include"SingleLinkedList.h"
//打印链表
void SLLPrint(SLLNode* phead)
{
	SLLNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->x);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//获取一个新节点
SLLNode* BuynewNode( SLLDataType x)
{
	SLLNode* newnode = (SLLNode*)malloc(sizeof(SLLNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		return;
	}
	newnode->x = x;
	newnode->next = NULL;
	return newnode;
}
//尾插
void SLLPushBack(SLLNode** pphead, SLLDataType x)
{
	assert(pphead);
	SLLNode* newnode = BuynewNode(x);
	if (*pphead == NULL)
	{

		*pphead = newnode;
	}
	else
	{
		SLLNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
	
}
//头插
void SLLPushFront(SLLNode** pphead, SLLDataType x)
{
	assert(pphead);
	SLLNode* newnode = BuynewNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾删
void SLLPopBack(SLLNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLLNode* prev = *pphead;
		SLLNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
	
}
//头删
void SLLPopFront(SLLNode** pphead)
{
	assert(pphead && *pphead);
	SLLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
//查找
SLLNode* SLLFind(SLLNode* phead, SLLDataType x)
{
	assert(phead);
	SLLNode* pcur = phead;
	while (pcur)
	{
		if (pcur->x == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在指定位置之前插入数据
void SLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x)
{
	assert(pphead&&*pphead);
	assert(pos);
	SLLNode* newnode = BuynewNode(x);
	if (*pphead==pos)
	{
		SLLPushFront(pphead, x);
	}
	else
	{
		SLLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
	
}
//在指定位置之后插入数据
void SLLInsertAfter(SLLNode* pos, SLLDataType x)
{
	assert(pos);
	SLLNode* newnode = BuynewNode(x);
	SLLNode* next = pos->next;

	newnode->next = next;
	pos->next = newnode;
}
//删除指定位置之后的数据
void SLLEraseAfter(SLLNode* pos)
{
	assert(pos&&pos->next);
	SLLNode* del = pos->next;
	pos->next=del->next;
	free(del);
	del = NULL;
}
//删除指定位置的数据
void SLLErase(SLLNode** pphead, SLLNode* pos)
{
	assert(pphead&&*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLLPopFront(pphead);
	}
	else
	{
		SLLNode* del = pos;
		SLLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = del->next;
		free(pos);
		pos = NULL;
	}
	
}
//销毁链表
void SLLDestroy(SLLNode** pphead)
{
	assert(pphead && *pphead);
	while (*pphead)
	{
		SLLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;	
	}

}

test.c文件：
#include"SingleLinkedList.h"
void test01()
{
	//定义一个单链表
	SLLNode* s1=NULL;
	//尾插测试
	SLLPushBack(&s1, 1);
	SLLPushBack(&s1, 2);
	SLLPushBack(&s1, 3);
	SLLPushBack(&s1, 4);

	//头插测试
	/*SLLPushFront(&s1, 5);
	SLLPushFront(&s1, 6);
	SLLPushFront(&s1, 7);
	SLLPushFront(&s1, 8);*/

	//尾删测试
	/*SLLPopBack(&s1);
	SLLPopBack(&s1);
	SLLPopBack(&s1);
	SLLPopBack(&s1);*/

	//头删测试
	/*SLLPopFront(&s1);
	SLLPopFront(&s1);
	SLLPopFront(&s1);
	SLLPopFront(&s1);*/
	//查找测试
//	SLLNode*find=SLLFind(s1, 3);
	/*if (find != NULL)
	{
		printf("找到了!\n");
	}
	else
	{
		printf("找不到!\n");
	}*/
	
	//在指定位置之前插入数据测试
//	SLLInsert(&s1, find, 55);

	在指定位置之后插入数据
	//SLLInsertAfter(find, 68 );
	
	//删除指定位置之后的数据
	//SLLEraseAfter(find);
	 
	//删除指定位置的数据
	//SLLErase(&s1,find);
	//打印链表
	SLLPrint(s1);

	销毁链表
	//SLLDestroy(&s1);
	打印链表
	//SLLPrint(s1);
}
int main()
{
	test01();
	return 0;
}

3.链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2x2x2）链表结构：

链表说明

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表

1.⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。

2.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带 来很多优势，实现反⽽简单了