数据结构-单链表

一.链表的概念和结构

1.1概念

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

1.2结构

这和之前学的顺序表不同，链表在内存中存放不是连续的，但是为了找到这些不连续的元素，所以把链表的每个元素都定义成一个结构体。结构体里有两个成员，一个是需要存的数据，另一个是下一个结构体的地址。
我们把这些一个一个的结构体取了一个名字：节点，最后一个节点因为没有指向的内容，所以把它里面的地址设置为空

二.链表的实现

2.1定义一个链表节点的结构体

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
1
2
3
4
5
6

每个节点都有两个成员，第一个要存放数据，第二个要存放下一个节点的地址。

我们在主函数里创建一个指针：

SListNode* plist = NULL;
1

这个指针plist就是一个指针，这个指针类型是我们刚定义的结构体类型的，刚开始为空。也可以认为这个指针指向了一个我们即将要开辟的链表的起始位置。

2.2动态申请一个节点

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	//开辟一块SListNode结构体大小的空间，返回地址
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("BuySListNode()");
		exit(-1);
	}

	//将这个新开辟的结构体里的data设置成需要输入的内容
	//将结构体里的第二个成员指针设置成空
	newnode->data = x;
	newnode->next = NULL;

	//返回这块空间的起始地址
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里，每个节点的空间都是用malloc函数在堆区开辟出来了。在创建的同时初始化将存的地址置为空。

2.3单链表尾插

我们之前创建了一个指针，这个函数就是把这个指针传进来。下面的图为了好表达尾插函数的作用，我假设我刚才定义的指针已经指向好了一个链表。

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	//创建一个节点
	SListNode* newnode = BuySListNode(x);

	//先判断此时传进来的那个指针是否为空指针
	//是的话说明此时还没有创建链表
	if (*pplist == NULL)
	{
		//将先创建的节点当作新链表的头节点
		*pplist = newnode;
	}
	else
	{
		//此时传进来的地址已经是一个已经建好的节点的起始地址
		//将这个地址赋给tail,用tail向后遍历，我们尽量不去动pplist这个指针
		SListNode* tail = *pplist;

		//寻找链表的尾部
		while (tail->next)
		{
			tail = tail->next;
		}

		//此时tail指向的位置就是最后一个节点的位置
		//将这个节点的第二个成员的地址改成新创建的节点的位置
		tail->next = newnode;
	}
}
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

单链表对尾部的操作是比较麻烦的，因为单链表要从头开始一直向后走，才能找到链表的尾部，然后在尾部插入一个数据。假设我们这个链表有了很多元素，我们要在这些元素的最后面添加一个元素：
我们希望在4这个节点后面插入5。首先要找到4的位置，可以通过一个指针，从头开始向后遍历：
直到tail->next == NULL时停下来，此时tail指向的就是最后一个节点：

接下来我们希望4的节点指向5的节点，只需要让tail->next = newnode(newnode是新开辟的节点的地址)。因为新开辟的节点默认指向空，所以这样就可以了：
但是这里还要注意一个问题，注意看while的循环条件：

while(tail->next)
1

加入我们传进来的是一个空链表，也就是说tail为空，此时在判断时tail->next就是对空指针解引用，这样会出错，所以在while循环之前要对这个特例单独说明。
有人可能已经发现了，我们这个函数传的是一个二级指针，为什么呢？刚才也说了如果传进来一个空链表：pplist是空的时候，我们是把一个新的节点的起始位置传给这个空指针，这个空指针指向的就是这个新增的节点。
但是就因为这一步出现了问题，函数的参数是形参只是实参的一份临时拷贝。这就意味着你函数里改变这个指针的内容，你外面那个实参是完全不受任何影响的，该是空指针就还是空指针，最好的解决办法就是，把需要改变的头指针的地址传进来，在函数里，你直接对地址解引用直接在函数里找到这个头指针，现在你就可以改变它的值了。

2.4单链表尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	//首先如果这个链表什么都没有就禁止删除
	assert(*pplist);
	SListNode* tail = *pplist;

	//找尾部，将倒数第二个节点成员的地址改为空，然后释放最后一个节点的空间
	//但是如果节点只有一个，就会造成空指针访问的错误
	if (tail->next == NULL)
	{
	//如果只剩一个节点，要删除它直接将这块空间free掉即可
	//因为tail是一个局部变量，它出了这个函数就会自动销毁，不用担心它会变成野指针。
		free(tail);
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		//此时tail指向的是倒数第二个节点
		//将倒数第一个节点空间释放
		free(tail->next);

		//此时tail指向的节点相当于最后一个节点
		tail->next = NULL;
	}
}
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

单链表的尾删也是一个很麻烦的东西，首先我们要考虑特殊情况：

加入链表为空的话，我们还要不要删？应该不能了吧，本来就是空的还要删什么？所以我们在函数开始之前先进行一个断言：

assert(*pplist);
1

如果链表还剩一个节点的时候，此时指针指向的是这个节点的位置，如果我们把它删了，我们现在这个指针指向的应该是空了吧。这就说明，在这种情况下，我们也要改变传进来的头指针的内容，这意味着尾插函数传进来的参数还是一个二级指针即指针的地址。

特殊情况考虑完了，现在看普通情况，它是怎么删除的，假设我们传进来的这个指针已经指向了一个有节点的链表，定义一个指针tail来代表这个头指针向后遍历：

现在能不能和尾插一样一样先找到4这个节点，然后再把它删除掉？不可以，因为我们将4这个节点释放掉的话，3这个节点指向什么呢？它本来只向的是4这个节点，但是4这个节点没了，节点3里的指针变量不就变成了野指针了吗，所以我们在释放4这个节点空间的同时要知道3这个节点的地址。

现在我们就不是在tail->next == NULL的时候停下来而是在tail->next->next的时候停下来，此时tail指向的就是倒数第二个节点：
接下来的步骤比较容易了，首先free(tail->next)就是把4这个节点的空间释放掉，然后将3这个节点指向的位置置成空：

这样我们就把4这个节点删掉了。

2.5单链表的打印

// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;

	//一直向后遍历，知道当cur此时指向的节点的第二个成员为空，说明此节点是最后一个节点
	while (cur)
	{
		//打印此时cur指向的节点的第一个成员的数据
		printf("%d ", cur->data);
		
		//将cur移动到下一个节点的位置上
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

单链表的打印比较简单，将cur指针从链表头部开始向后遍历，每次遍历时将cur指向的这个节点的数据打印出来。

2.6单链表的头插

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
	//这里要注意*pplist如果要解引用一定要加上括号
	//(*pplist)->data
}
1
2
3
4
5
6
7
8
9

相比顺序表而言，链表最容易的就是头插头删了。
在头部差一个节点两步就可以了。首先将新节点指向原来的头节点：
然后新节点的地址作为头节点，因为我们还是要改变头节点的内容，所以这个函数也要传指针的地址。

2.7单链表的头删

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* next = *pplist;
	next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}
1
2
3
4
5
6
7
8
9

刚开始先考虑一下特殊情况，如果传进来的是一个空指针，这肯定是不能进行删除这个操作的，所以先进行断言。
现在希望将newnode这个节点删除掉，现在不能直接将这个节点free掉，因为直接释放之后你就找不到后面那些节点的位置了，所以要先把第二个节点的地址保存下来：

	SListNode* next = *pplist;
	next = (*pplist)->next;
1
2

保存完之后就可以把第一个节点释放掉了，最后头指针也要移动到next的位置。这里和头插一样都要改变头指针的位置，所以要传二级指针。

2.8单链表查找

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;

	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

查找和打印两个函数是一个性质都是读链表，不会对链表里的内容做改变，所以这两个函数传的都是一级指针。

函数查找比较简单，定义一个指针遍历这个链表如果某个节点里的值和需要查找的值相同，则返回该节点的地址。

2.9在pos位之后插入x

// 单链表在pos位置之后插入x
//pos的位置是在查找的时候得出来的
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	//因为下面有个代码是pos->next,所以pos必须不为空指针，否则会出错
	assert(pos);

	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8
9
10
11

这个函数是要结合函数的查找一起来使用的。首先是要在pos位之后插入：
这里也不需要遍历，因为传进来的指针指向的本来就是需要插入的那个位置的地址。

加下来就好操作了：

注意先后顺序，先让新节点指向4这个节点，然后让3这个节点指向这个新节点。如果步骤搞反了的话，3在指向新节点之后就找不到4这个节点了。

2.10在pos位之前插入x

// 单链表在pos位置之前插入x
void SListInsertBefore(SListNode** phead, SListNode* pos, SLTDateType x)
//这里可能会出现头插的情况，既然是头插，必然会改变链表的起始位置，所以这里用到了二级指针
{
	SListNode* cur = *phead;
	SListNode* newnode = BuySListNode(x);

	if (pos == *phead)
	//说明是头插
	{
		SListPushFront(phead, x);
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}

		//此时找到的是pos之前的节点位置
		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
23
24

在pos位之前插入比在之后插入要麻烦的多。因为我们只知道pos位的地址，不知道pos位之前的地址。所以我们要从头开始遍历，又因为要从头开始遍历，所以我们需要传进去头指针，但为什么是二级指针，想必看到这里你们应该多少猜到一些了。如果pos指向的节点就是头节点的时候，此时在pos位之前插入就相当于头插了。

当pos是其他位置的时候，我们就要开始遍历链表了，知道找到pos之前的那个位置也就是cur->next == pos的时候。
找到之后的操作也是比较容易的：
先将新节点指向pos指向的节点，然后将cur指向的节点指向新节点。

2.11在pos位之后删除

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);

	if (pos->next == NULL)
	{
		return;
	}

	SListNode* cur = pos->next;
	pos->next = pos->next->next;
	free(cur);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在删除之前先考虑几种特殊情况：
如果链表为空，此时我们不在删除，所以要提前断言
如果pos为指向的最后一个元素，在链表末尾删除也是不可取的上面用的是if语句，用assert断言也是可以的。

普通状况时删除就比较简单了：

现在是希望将节点3后面的节点4删除，但是我们不能直接删除掉4，因为如果删了，5这个节点我们就找不到了，我们可以先把需要删除的节点的位置保存下来，然后将3这个节点直接指向5这个节点，做完这一步再将4这个节点释放掉。

2.12删除pos位

// 单链表删除pos的值
void SListEraseBefore(SListNode** pphead, SListNode* pos)
{
	assert(pos);

	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}

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

删除pos位的节点比删除pos位之后的节点麻烦许多。
首先要assert断言防止链表为空，然后要考虑pos位是头的情况，这时候就相当于头删了，所以这个函数也要传一个二级指针。

如果pos不是头的时候，如果要删除pos位的节点，首先要找的pos位之前的那一个节点，这钟情况我们只能从头开始遍历了：
找到之后就容易了，但现在我们不用把需要删除的那个节点的地址保存下来，因为这个地址就是pos，我们本来就知道。
随后将cur指向的节点指向pos的下一个节点就行：

cur->next = pos->next;
1

连接完之后就可以释放pos指向的那个节点了。

2.13单链表的销毁

// 单链表的销毁
void SListDestroy(SListNode** plist)
{
	SListNode* cur = *plist;
	while (cur)
	{
		cur = (*plist)->next;
		free(*plist);
		*plist = cur;
	}
}
1
2
3
4
5
6
7
8
9
10
11

在最开始的时候，我就讲过，链表里的这些节点都是在堆区开辟的空间，就是说你用malloc函数开辟，你必须在用完之后手动释放，系统不会帮你的。

这里我们将链表用指针cur从头开始遍历：
先将cur指向节点的下一个节点的位置保存下来。

保存完之后再将cur指向的节点释放掉。

释放完再将cur指向刚才保存的节点。

next继续指向cur指向节点的下一个节点。

像这样一直走，边走边释放，直到cur为空就结束了。

三.其它的一些链表

链表的增删查改到这里基本就讲完了，但是链表不止单链表这一种。

单向/双向，带头/不带头，循环/不循环
这几种经过排列组合可以组成8种类型的链表。但是有些链表不常用，我之后会讲双向带头循环链表，这可是一个buff拉满的链表。