【数据结构】单链表

一、什么是链表

在线性表结构中，可以分为顺序存储结构与链式存储结构，顺序存储结构就好比数组，在一块连续的空间中存放对应的数据。

二、链表种类

链表也有多种的类型：单向链表，双向链表，带头（哨兵位）链表，不带头（哨兵位）链表，循环链表和不循环链表；同时这几种属性可以相互搭配：

共有8种；

三、单向不带头不循环链表的实现

（一）链表的初始化

因为链表所储存的数据还不确定，所以可以先使用typedef将链表所储存的数据类型进行重命名，当需要重新更改数据类型时只需要更改被重命名的类型即可。

typedef int SLTDataType;
typedef struct SListNode//声明一个结构体 
{
	SLTDataType date;//用来存放数据
	struct SListNode* next;//用来记录下一个内存的地址或是空指针
}SLTNode;//使用typydef将结构体重命名为STLTNode

在实现链表之前应先声明一个相对应的结构体类型，使得每次malloc节点时的类型都能为该结构体类型。

（二）链表的打印

void SLTPrint(SLTNode* phead)//链表的遍历
{
	SLTNode* cur = phead;
	while (cur != NULL) {
		printf("%d->",cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
	//本质上也可以移动phead，形参的改变不影响实参
}

该处在函数内创建了一个cur指针用来进行链表的遍历，本质上此处也可直接使用phead指针，函数内的phead指针为形参，形参的改变不会影响到实参；

（三）新节点的开辟

当需要插入数据的时候即需要向内存开辟空间，在此存在多个插入接口（头插、尾插、中间插入），故可以将开辟空间封装为一个函数；

SLTNode* BuyLTNode()
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		perror("SLPushFront::malloc");
		return NULL;
	}
	newnode->next = NULL;//保险起见应先提前将新节点的next置空
	return newnode;
}

（四）链表的尾插

单链表的尾插，即将尾节点的next指向新节点，同时新节点的next指向NULL；

void SLPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* newnode = BuyLTNode();
	newnode->date = x;

	if (*pphead==NULL) {
		*pphead = newnode;
	}
	else {
		SLTNode* tmp = *pphead;
		while (tmp->next!=NULL) {
			tmp = tmp->next;
		}
		tmp->next = newnode;
	}

}

（五）链表的尾删

链表的尾删即为，遍历到尾节点的前一个节点，并将尾节点释放，同时将尾节点的前一个节点的next处置为空；

该处需要注意的是典型的边界性问题：

• 尾删时链表不能为空；
• 尾删时若是链表只存在一个节点，则可能出现非法解引用访问；
  

void SLPopBack(SLTNode** pphead)//尾删 
{
	assert(*pphead);//空链表

	SLTNode* tmp = *pphead;
	if (tmp->next == NULL) {
		free(tmp);
		*pphead = NULL;
	}
	else
	{
		while (tmp->next->next != NULL) {
			tmp = tmp->next;
		}
		free(tmp->next);
		tmp->next = NULL;
	}
}

（六）链表的头插

void SLPushFront(SLTNode**phead,SLTDataType x) //头插
{
	SLTNode* newnode = BuyLTNode();

	newnode->date = x;
	newnode->next = NULL;//初始化置空

	newnode->next = *phead;
	*phead = newnode;
}

（七）链表的头删

链表的头删与头插也有异曲同工之处，都需要使用二级指针来更新头指针head的指向；

void SLPopFront(SLTNode** pphead)//头删
{
	assert(*pphead);

	/*if ((*pphead)->next == NULL) {
		SLTNode* tmp = *pphead;
		free(tmp);
		*pphead = NULL;
	}
	//注释掉的步骤为冗余的步骤；
	else {*/
	
		SLTNode* tmp = (*pphead)->next;
		free(*pphead);
		*pphead = tmp;
		
	//}
	
}

（八）链表的查找

SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* tmp = phead;
	while (tmp->next != NULL) {
		if (tmp->date == x) {
			return tmp;
		}
		tmp = tmp->next;

	}
	return NULL;
}

（九）链表中间插入（pos之后）

该处的pos即为所给位置的节点，一般在单链表中的中间插入都为pos之后，单链表与双链表不同，单链表只能依靠结构中的next访问下一个节点，而不能通过该节点访问该节点的前一个节点。

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode*newnode = BuyLTNode();
	newnode->date = x;
	SLTNode* tmp = pos->next;
	pos->next = newnode;
	newnode->next = tmp;		
}

（十）链表的中间删除（pos之后）

单链表的中间删除与中间插入相同，因为单链表不像双链表一样可以访问到pos之前的节点，故一般只能删除pos之后的节点；

void SListEraseAfter(SLTNode* pos) 
{
	assert(pos&&pos->next);
	SLTNode* tmp = pos->next->next;
	free(pos->next);
	pos->next = tmp;
}

（十一）链表的修改

链表的修改只需要将所给指针pos节点内的val改为需要修改的值即可，但也需要对pos指针进行assert断言，防止对非法指针的解引用访问；

void SLModify(SLTNode* phead, SLTDataType x) {
	assert(phead);
	phead->date = x;
}

（十二）链表的销毁

只要是涉及到内存申请的问题，在申请并用完过后应及时进行释放，一般情况下程序结束时会自动将程序内所申请的空间还给操作系统，但若是程序未结束，所申请的内存即不将还给操作系统，可能会发生内存泄漏等问题；
链表的销毁只需将链表中的各个节点进行释放并将头指针head置为空防止出现野指针问题即可；

void SListDestroy(SLTNode** plist)
{

	assert(*plist);
	SLTNode* tmp;
	SLTNode* pos = *plist;
	while (pos != NULL) {
		tmp = pos->next;
		free(pos);
		pos = tmp;
	}
	*plist = NULL;
}

利用两个指针对链表进行遍历，使用指针pos指向头head，另一个指针tmp指向pos所指向的next，并对链表进行遍历，tmp指针用来记录即将被销毁的节点的下一个节点，pos指针用来释放内存；

总结

1. 操作链表的几个函数内都要注意对所给参数进行断言，防止对非法指针的解引用访问；
2. 单向不带头不循环链表虽然是链表中结构最简单的链表，但相比于其他链表中操作也是最繁琐的，为了防止出现边界问题，总要对链表进行判空；