单链表的实现（Single Linked List）---直接拿下！

单链表的实现（Single Linked List）—直接拿下！

一、单链表的模型

链表也是一种线性表，和我们之前讲过的顺序表属于一个大类。
这是之前有关顺序表的介绍，如果大家有兴趣的话可以点击下面链接。
顺序表的实现
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
存储结构（实际存在的）非线性的，逻辑结构（人们想象出来的）是线性的。


注意：pList只是一个指针，它本身不是一个结点。最后一个包含数值4的结点指向的下一个结点的指针就是NULL。
而且这些结点都是从堆上申请而来的，从堆上申请空间，是按照一定策略分配的，两次申请的空间可能连续也可能不连续。

typedef int SLDataType;
typedef struct SLNode
{
	SLDataType val;
	struct SLNode* next;
}SL;
1
2
3
4
5
6

二、代码实现，接口函数实现

①初始化

void SLIni(SL** phead)
{
	assert(phead);
	*phead = NULL;
}
1
2
3
4
5

②打印链表

void SLPrint(SL* phead)
{
	SL* cur = phead;//我们要养成一个良好的习惯，这样多创建一个变量。
	while (cur)//注意此处打印，不需要assert断言，
	//因为空链表也需要打印出一个NULL
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

相信大家已经发现了我的备注，空链表是什么鬼？不急，大家先来看一下尾插的实现后，我就给大家详细解释一下。

③创建一个结点

SL* SLCreateNode(x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

④尾插

void SLPushBack(SL** phead, SLDataType x)
{
	assert(phead);
	SL* newnode = SLCreateNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		SL* tail = *phead;
		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

相信大家经过尾插后，一下子就看懂了，空链表就是首结点的指针直接指向NULL，而这样的链表在尾插时，我只需要把首结点的指针指向新创建的结点就啦。

⑤尾删

大家先来思考两个问题
1.空结点还能删吗？当然是不能呀，家都没了，就别拆了。
2.一个结点的链表删了之后是不是就只剩一个NULL了？对，所以头结点指针需要改变了，指向NULL。

void SLPopBack(SL** phead)
{
	assert(phead);
	assert(*phead);//避免空节点
	SL* tail = *phead;
	SL* cur = tail;
	if (cur->next == NULL)//只有一个结点的链表
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		while (tail->next)
		{
			cur = tail;
			tail = tail->next;
		}
		free(tail);
		cur->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

相信大家已经看出来了，单链表有几个特殊的情况，也就是空链表和只有一个结点的链表，所以无论大家以后在写代码或者OJ题的过程中，切记要考虑三个情矿，空链表，一个结点和正常多个结点的链表 。

⑥头插

void SLPushFront(SL** phead, SLDataType x)
{
	assert(phead);
	SL* newnode = SLCreateNode(x);
	newnode->next = *phead;
	*phead = newnode;
}
1
2
3
4
5
6
7

⑦头删

void SLPopFront(SL** phead)
{
	assert(phead);
	assert(*phead);
	SL* next = (*phead)->next;
	free(*phead);
	*phead = next;
}
1
2
3
4
5
6
7
8

单链表进行头插、头删真的很方便。

⑧查找结点

SL* SLFind(SL* phead, SLDataType x)
{
	while (phead)
	{
		if (phead->val == x)
		{
			return phead;
		}
		phead = phead->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

⑨在pos位置的结点处插入一个新节点（不删除pos结点，在pos结点前插入）

void SLInsert(SL** phead, SLDataType x, SL* pos)//在pos位置之前插入
{
	//一定要保证pos是链表里的一个有效结点。
	assert(pos);
	assert(phead);
	assert(*phead);
	if (*phead == pos)//头插需要单独拎出来，要不然这种情况就会被漏掉。
	{
		SLPushFront(phead, x);
	}
	else
	{
		SL* cur = *phead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SL* newnode = SLCreateNode(x);
		cur->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

⑩删除pos位置的结点。

void SLErase(SL** phead, SL* pos)
{
	assert(phead);
	assert(*phead);
	assert(pos);
	if (*phead == pos)//头删需要单独拎出来，要不然这种情况会被漏掉。
	{
		SLPopFront(phead);
	}
	else
	{
		SL* cur = *phead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->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

⑪在pos位后面插入

void SLInsertAfter(SLDataType x, SL* pos)
{
	assert(pos);//这么一步，已经把空链表刨除在外了，
	//因为严格限制pos必须是链表里的一个有效结点。
	SL* newnode = SLCreateNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8

这种情况就不需要传头结点指针了，因为在保证pos是链表里的一个有效结点后，不像在pos位置前插入，需要遍历链表，找到pos位前一位的结点，这种情况直接在pos位后面插入就好了。这个是因为受限于单链表的性质，单向走，无法回溯。

⑫删除pos位后面的结点

void SLEraseAfter(SL* pos)
{
	assert(pos);
	assert(pos->next);
	SL* tmp = pos->next;
	pos->next = tmp->next;
	free(tmp);
	tmp = NULL;
}
1
2
3
4
5
6
7
8
9

⑬销毁链表

void SLDestroy(SL** phead)
{
	assert(phead);
	SL* cur = *phead;
	while (cur)
	{
		SL* next = cur->next;
		free(cur);
		cur = next;
	}
	*phead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

⑭测试用例

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

void test1()
{
	SL P;
	SL* p1 = &P;
	SL** phead = &p1;
	SLIni(phead);
	SLPushBack(phead, 1);
	SLPushBack(phead, 2);
	SLPushBack(phead, 3);
	SLPushBack(phead, 4);
	SLPushBack(phead, 5);
	SLPrint(p1);
	SLPopBack(phead);
	SLPopBack(phead);
	SLPopBack(phead);
	SLPopBack(phead);
	SLPopBack(phead);
	SLPrint(p1);
}

void test2()
{
	SL P;
	SL* p1 = &P;
	SL** phead = &p1;
	SLIni(phead);
	SLPushFront(phead, 1);
	SLPushFront(phead, 2);
	SLPushFront(phead, 3);
	SLPushFront(phead, 4);
	SLPushFront(phead, 5);
	SLPrint(p1);
	SLPopFront(phead);
	SLPopFront(phead);
	SLPopFront(phead);
	SLPopFront(phead);
	SLPopFront(phead);
	SLPrint(p1);
}

void test3()
{
	SL P;
	SL* p1 = &P;
	SL** phead = &p1;
	SLIni(phead);
	SLPushBack(phead, 1);
	SLPushBack(phead, 2);
	SLPushBack(phead, 3);
	SLPushBack(phead, 4);
	SLPushBack(phead, 5);
	SL* ret = SLFind(p1, 3);
	SL* ret1 = SLFind(p1, 1);
	printf("%d\n", ret->val);
	//SLErase(phead, ret);
	SLErase(phead, ret1);
	SLInsert(phead, 100, ret);
	SLPrint(p1);
}

int main()
{
	//test1();
	//test2();
	test3();
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

三、总结

最重要的一点，一定要考虑单链表空链表、一个结点(也包括需要单独考虑尾结点（NULL前的结点）和单独考虑头结点）和正常的情况。初次之外，还有很重要的一点，一定不要对空指针解引用。
单链表在实现头插和头删真的很方便，但是大家相信大家也会发现，实现尾插和尾删，找尾的过程时间复杂度是O(n)。
所以，这就引出我们的神中神链表，双向带头循环链表。
l带头双向循环链表