单链表（无头单项非循环）

前言

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。链表的形式有很多，本篇文章主要介绍的是单链表且无头结点。在严版数据结构（C语言 第2版）中，单链表采用的是有头节点，这两种形式，各有利弊。含头节点的单链表在学习时，可能会容易些，但是在实践中或者在力扣中做题时，很少会有带头节点。但是有时候做题，使用带头节点的单链表会简单许多，不常见。

概述

一个结点有两个部分组成，数据域（val），指针域（next）。

链表的实现

初始化

在无头单项非循环链表中，需要声明一个数据域和指针域，指针域指向的是下一个节点的地址，数据域是当前节点的数据。这里需要注意的是，在声明指针域是，因为是结构体指针类型，所以一定要写全了。

typedef int SLNDataType;

//初始化
typedef struct SListNode
{
	SLNDataType val;    //指针域
	struct SListNode* next; //指针域
}SLNode;
1
2
3
4
5
6
7
8

遍历单链表

遍历单链表，就是从单链表的第一个节点一直访问到单链表的最后一个节点。
形参接收到的是单链表的第一节点，然后需要用指针去维护节点。通过改变指针的指向，从而实现访问不同的节点。
当cue不为空指针时，继续访问下一个节点，操作为：cur=cur->next
当cur为空时，已经访问结束，无需继续遍历。
需要注意的是，这里的判断条件是cur为不为空，而不是cur->next为不为空，如果去判断cur->next，那么当cur->next==NULL时，访问的是最后一个节点为空，此时还没有遍历结束。

void SLTprintf(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

创建新节点

用malloc函数，在堆上申请一片空间来存储数据，当newcode为空时，表示开辟失败。

//创建新节点
SLNode* CreateNode(SLNDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

尾插

尾插又称后插法，顾名思义，是将新节点逐个插入链表的尾部来创建链表。每次申请一个新节点，读入相应的数据元素值，同时需要一个尾指针指针链表的尾节点（tail）。
需要注意的是，当链表为空时，直接将新创建的节点当作第一个节点。尾插是封装在函数里实现的，对于函数来说，形参的改变不会改变形参，因此需要传递地址，即址传递，因此需要一个二级指针接收。
pphead是头指针（plist）的地址，*pphead是对它进行解引用。

void SLTPushBack(SLNode** pphead, SLNDataType x)
{
	SLNode* newnode = CreateNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

空链表和链表不存在的区别：

• 空链表： 头指针为空，也就是plist==NULL表示是一个空链表
  在遍历、尾插、头插时允许空链表存在，在头删、尾删中不允许出现
• 链表不存在： ppead==NULL，表示链表不存在，这种情况不允许存在的，因此，每次都需检查一下链表存不存在。

头插

头插法即前插法，逐个将新节点插入到链表的头部来创建，每次申请一个新节点，读入相应的数据元素值。传递的也是二级指针，将新节点的头节点给newnode->next，将newhead变成头节点。

//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	SLNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6
7

尾删

尾删是将最后一个节点给释放掉，同时还需要保存倒数第二个节点，将它的指针域存放的地址改成NULL。需要两个指针，一个找尾，一个找倒数第二个节点，同时遍历。
空链表不能删，链表中只有一个节点的链表删除后会变成一个空链表，改变头指针需要存放地址，形参也是一个二级指针。

void SLTPopBack(SLNode** pphead)
{
	assert(*pphead);
	assert(pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

头删

头删需要改变的是头指针的地址，因此传的也是地址。tous需要考虑链表是否为空，如果是空链表就不能操作了，因此需要先断言。在删除头节点的时候，需要先保存一下头节点，否则释放了头节点，就找不到原来的头节点了。

//头删
void SLTPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
}
1
2
3
4
5
6
7
8
9
10

单链表的查找

单链表的查找实际上就是遍历单链表，遍历过程中，找到你所需要的数值，如果是的，就返回当前节点，不是就继续往下遍历，直到链表为空。如果遍历完了还没有找到，那就说明你想查找的数值不在链表里面，返回空指针。

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	SLNode* ptr = phead;
	while (ptr)
	{
		if (ptr->val == x)
		{
			return ptr;
		}
		else
		{
			ptr = ptr->next;
		}
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在pos位置之前插入一个节点

遍历链表，找到pos之前的节点，然后按照尾插的方式插入即可。但是需要判断一种情况，如果pos就是第一个节点，那么在pos位置之前插入，那就相当于是头插了。有限制条件，pos一定是链表中的一个有效节点。

//在pos位置之前插入
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//pos如果为头节点，就是头插
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
    //pos不是头节点
	else
	{
		SLNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		SLNode* newnode = CreateNode(x);
		pre->next = newnode;
		newnode->next = pos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

在pos位置删除节点

pos需要是链表中存在的节点，链表不能为空。pos可能是头节点，因此需要二级指针，这种情况就相当于头删。删除pos节点时，需要一个指针保存pos前一个节点，让pos前一个结点的指针域直接指向pos下一个节点即可，释放pos，让pos=NULL。

//在pos位置删除节点
void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre=pre->next;
		}
		pre->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在pos位置后插入节点

需要保证pos是链表的一个有效节点，然后让新节点的指针域指向pos的下一个节点，然后让pos的指针域指向新节点。

//pos位置之后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);
	SLNode* newnode = CreateNode(x);

	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8
9

删除pos后一个节点

删除pos后一个节点，pos已经是一个节点，因此，链表不可能为空。
需要注意的是，这里不能直接是pos的指针域指向pos后的第二个节点，因为每一个节点都是通过malloc在堆上申请的，不使用的时候要主动的去释放掉，也就是free掉，把这块空间归还给操作系统，否则会导致内存泄漏。需要借助一个节点，保存待删节点，然后去释放借助的这一个节点并置为空指针即可。

//删除pos后一个节点
void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLNode* tmp = pos->next;
	pos->next = pos->next->next;

	free(tmp);
	tmp = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

销毁

void SLTDestroy(SLNode** pphead){
	assert(pphead);

	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

结尾

单链表相对于顺序表会难很多，也会有很多的坑点，我们要去判断链表是否为空？（在遍历、尾插、头插时允许空链表存在），头节点是否存在？什么时候传二级指针？