无头单向非循环链表的实现

1.链表的结构

在用代码实现之前，我们要先了解这种链表的逻辑结构和物理结构，

在逻辑上我们能知道这种链表能够通过前一个节点的 next 来存储下一个节点的地址，从而能够找到下一个数据，这就是一种线性结构，我们可以把数据看成是按照一定的顺序存储起来的，虽然他们的空间顺序不一定是他们的逻辑顺序。上面图中的 head 并不是指的链表是有头链表，head不是烧饼位，而是链表头节点，存储第一个数据的空间。我们使用链表时只要知道头节点的位置，就能访问到所有的数据，如果链表为空，则一个节点也没有。

这就是链表的物理结构，通过对节点的 next 中存的地址解引用就能访问到下一个节点，而尾节点的 next 我们设置为空指针。

2.链表的实现

链表的物理结构和逻辑结构我们清楚之后，我们就能找到每个节点的情况，无非就是数据域和指针域，数据域用来存储数据，而指针域用来存储下一个节点的指针，对于每一个节点我们用结构体定义出来就是这样的：

typedef int SLTDataType;

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

而对于后续的链表的操作，我们只需要传头结点的地址就够了，因为链表通过头节点就能访问到所有数据。而链表没有数据时，没有头节点，链表地址就是空指针。所以我们一般首先将plist初始化为NULL，而因为链表没有元素时什么也没有，所以现在要实现的这个单链表是不需要初始化的。

void test1()
{
	SLTNode* plist = NULL;
	//对plist进行操作

}

下面就是要实现的一些接口

头插

对单链表头插数据十分简单。我们首先要创建一个newnode，因为创建节点的功能我们在后面的各种插入数据中都要用到，所以我们直接写一个函数来完成创建节点的功能

//创建新节点
SLTNode* NewSLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

我们在函数中创建一个新节点，将新节点的的数据初始化为插入的数据，next设置为NULL。然后返回新节点地址。

然后头插数据我们具体要怎么做呢？

看图就很简单了，我们只需要 phead 指向新节点，然后原来的链表链接到新节点的next就完成了。

但是头插是要改变 phead 的，也就是整个链表的头节点地址 plist ，所以在头插函数中我们要传plist 的地址，也就是一个二级指针，记住，要修改什么类型的变量就要传那个类型的指针，plist是SLTNode*类型的指针变量，要修改 plist 就要传plist的地址，在函数参数部分就要用SLTNode** 的指针来接收。

//头插数据
void SLTPushFront(SLTNode** pphead, SLTDataType x);

传参的时候，可能链表为空，也就是phead（plist）为NULL，但是 plist 是一个变量，他的地址不可能为空，也就是pphead 不能为NULL，如果为空，就说明传参有问题，我们可以用assert断言一下，后续的很多结构都要对一些不可能为空的指针断言检查。链表为空和链表不为空时的操作其实是一样的逻辑和代码，因为phead为NULL的时候，将 phead 连接到newnode的时候，不会对newnode有什么影响，newnode的next还是NULL，也就是它既是头指针也是尾指针。

//头插数据
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = NewSLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

为了方便测试，我们先写一个打印链表的函数出来。

打印链表

打印函数我们只需要从头结点遍历到NULL就行了。因为打印链表不会出现需要修改头结点的请跨，所以我们传 plist 就够了，同时因为链表可能为空，我们不用对传过来的phead断言。

//打印链表
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)//当cur为空时就结束
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//为了更加直观，在最后面打印一个NULL
	printf("NULL\n");

}

写完打印函数之后先来测试一下头插的函数

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);

头插函数没有问题。

头删

头删函数我们一样看图来分析

我们只需要把phead指向的节点删除，在这之前要修改phead指向第二个元素，要注意先换phead的指向再去free第一个节点，否则就出现野指针的问题了。同时，我们要注意头节点要修改，我们要传二级指针pphead，而且，删除元素的时候链表不能是空链表，所以我们还要对 *pphead也进行断言。

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//先记录要删除的节点
	SLTNode* del = *pphead;
	//调整头结点指针
	*pphead = (*pphead)->next;
	//最后释放原来的头节点
	free(del);
}

然后对函数进行测试，我们一个一个把数据删完

	//头插
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
	
	//头删
	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

测试链表为空再删除一下的情况

assert断言失败报错，说明函数功能是没问题的。因为当链表只有一个节点时，我们先将 phead 的值修改为phead的next，也就是NULL，所以删完之后phead又重新变成了空指针。

尾插

单链表的尾插是一件很麻烦的事情，因为他首先要找到尾节点，而由于他是单向非循环的，所以找尾节点只能遍历。我们用一个 cur 的指针来遍历链表

而cur什么时候停下来呢，尾节点有一个特点，就是他的next为NULL，所以我们的遍历的结束条件就是cur->next!=NULL。但是光这样还不行，尾插的对象可能是一个空链表，也就是cur为NULL，这时候对cur解引用就会出错。所以尾插也要检查链表是否为空，如果为空，也要修改头结点的指针，所以尾插传的也是 pphead （&plist）。而当链表为空时我们可以复用头插的函数来插入数据。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	if (*pphead == NULL)//如果为空链表
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = NewSLTNode(x);
		SLTNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		//找到尾节点将newnode连接到尾节点的next
		cur->next = newnode;
	}
}

然后对尾插进行测试


void test2()
{
	SLTNode* plist = NULL;
	//对plist进行操作
	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
}

尾删

尾删的第一步和尾插一样都是找尾节点，但是又有一点不一样，就是尾删需要用一个指针prev来保存尾节点的前一个节点，因为我们不仅要释放掉最后一个节点，还要对倒数第二个节点的next置为NULL。当然尾删的前提是链表不为空，可以用assert断言，同时，因为删除数据可能会把链表删为空，也就是可能会改变phead，所以也要传二级指针。这里我们要思考一下要不要将只有一个节点的请跨单独拿出来讨论。

当只有一个节点时，cur->next为NULL，所以不会进入循环中，这时候我们就不需要定义一个prev指针了，而是直接释放掉phead，然后要通过二级指针把plist置为NULL。

有了思路代码就很好写了

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* cur = *pphead;
	if (cur->next == NULL)//只有一个节点的情况
	{
		free(cur);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev=NULL;
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;
		}//循环退出时prev为倒数第二个节点
		prev->next = NULL;
		free(cur);
	}
}

首先我们来测试正常情况下的尾删


void test2()
{
	SLTNode* plist = NULL;
	//对plist进行操作
	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

}

当链表为空时再次尾删

数据查找

查找函数也没什么可取巧的，我们就是要遍历链表，一一比对数据，如果链表中能找到该数据，则返回节点的指针，如果找不到就返回空指针。

//查找数据，返回节点地址
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur)//遍历查找
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	//遍历完找不到就返回NULL
	return NULL;
}

而查找函数返回了节点的指针之后，我们就不用再额外写一个修改函数了，因为我们可以直接对pos的data进行操作。

测试一下查找和修改

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
	
	SLTNode* pos = SLTFind(plist, 1);
	if (pos != NULL)
	{
		pos->data = 30;
		SLTPrint(plist);
	}
	else
	{
		printf("找不到\n");
	}

指定位置插入

链表指定位置插入的逻辑是在该位置之前插入，这时候我们就需要遍历查找pos的前一个位置。在这个函数中我们不再讨论 pos 是否为链表中的节点位置，只讨论Find函数的返回值中NULL和节点指针两个方面，如果pos传的是NULL，就报错，这就要求使用者在函数传参使得要注意一点了。同时，因为传的pos有可能是头结点的地址，如果是头节点的地址，我们就用头插的做法来写。

//指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	SLTNode* newnode = NewSLTNode(x);
	if (pos == *pphead)//头结点的情况
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)//我们不讨论pos是非节点指针
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

测试插入，首先测试尾节点

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
	
	SLTNode* pos = SLTFind(plist, 1);
	SLTInsert(&plist, pos, 30);
	SLTPrint(plist);

再测试头节点

指定位置之前插入数据的效率有点低，要遍历一遍，但是我们发现它在指定位置之后插入就很方便，于是我们再来实现一个指定位置之后插入的函数

//指定位置之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	SLTNode* newnode = NewSLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

测试首尾节点

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
	
	SLTNode* pos = SLTFind(plist, 4);
	SLTInsertAfter(&plist, pos, 30);
	SLTPrint(plist);
	pos = SLTFind(plist, 1);
	SLTInsertAfter(&plist, pos, 10);
	SLTPrint(plist);

指定位置删除

指定位置删除的逻辑与指定位置插入差不多，也是要先找到pos的前一个结点，然后将pos的前一个结点的next修改为pos的next。由于pos也与可能是头节点，所以有可能会修改头节点，要传二级指针。

//指定位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)//头删
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
			free(pos);
	}
}

测试头尾的删除

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
	
	//SLTNode* pos = SLTFind(plist, 4);
	//SLTInsertAfter(&plist, pos, 30);
	//SLTPrint(plist);
	//pos = SLTFind(plist, 1);
	//SLTInsertAfter(&plist, pos, 10);
	//SLTPrint(plist);
	//

	SLTNode* pos = SLTFind(plist, 4);
	SLTErase(&plist, pos);
	SLTPrint(plist);
	pos = SLTFind(plist, 1);
	SLTErase(&plist, pos);
	SLTPrint(plist);