【数据结构】链表（及其单链表实现）

文章目录

• 一、链表概念
• 二、链表的分类
• 三、单链表的实现（无头单向不循环）
• • • 1.SLT.c
    • • • 1.1创建新的结点
        • 1.2插入n个连续的数
        • 1.3数据打印
        • 1.4单链表尾插
        • 1.5单链表尾删
        • 1.6单链表头插
        • 1.7单链表头删
        • 1.8查找数据
        • 1.9在指定位置后面插入
        • 1.10指定位置删除
        • 1.11销毁数据
    • 2.SLT.h
    • 3.test.c
• 四、顺序表和链表的优缺点

一、链表概念

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

1️⃣从上图可以看出逻辑上是连续的，而物理上就并不一定是连续的了
2️⃣现实中结点都是从堆上申请的，（有的书上结点也可能为节点意思是相同的，在这里也顺便介绍一下什么是前驱结点，后驱结点。例如：1、2、3、n、n+1中n+1是n的后驱结点，而n是n+1的前驱结点）
3️⃣因为是在堆上申请的空间，所以可能会出现二次申请空间可能，所以也就导致在物理上不是连续的。

二、链表的分类

链表一共分为三种结构，带不带头，单向双向，循不循环。
由这三种结构可以组合八种，所以链表的分类为八种。

​🐬​：在下面就不全部介绍了，拿出两个经典也是最常用的来介绍一下无头单向非循环链表 带头双向循环链表，在下面的图看上去带头双向循环链表可能看起来比较复杂，但是在我们实现的过程中会发现便不难，对比无头单向非循环，还是前者写起来比较舒服。
1️⃣ 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2️⃣ 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

三、单链表的实现（无头单向不循环）

这里把单链表分为三个大部分分别是
1️⃣test.c：头文件用来测试单链表的功能。
2️⃣SLT.c ：主要是用来单链表功能的实现
3️⃣SLT.h：用来放一些头文件，函数声明，结构体的创建。

1.SLT.c

1.1创建新的结点

创建新的节点，使用动态开辟空间，并对结点内的值进行初始化。

SLTNode* BuySLTNode(SLTDataType x)
{//创建新结点
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)//判断是否空间开辟成功
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;//进行初始化
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

1.2插入n个连续的数

该函数的目的是插入n个连续的数，并不需要一个一个的插入，提供了便捷。在这里每插入一个数就开辟一个空间，这样并不会造成空间浪费，在这里并不能直接尾插，因为这并不是带头的链表，所以需要判断一下。

SLTNode* CreateSList(int n)//插入n个连续的数
{
	SLTNode* phead = NULL;
	SLTNode* ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (phead == NULL)
		{
			//SLTNode* newnode = BuySLTNode(i);
			phead = ptail = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

说一个我自己犯得错误，在创建新的结点的时候，因为上面是在循环当中创建的，我就认为BuySLTNode(i)中主要是i相同，就认为结点也就相同了，下面来看一下我当时错误的代码。❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌

SLTNode* CreateSList(int n)//插入n个连续的数
{
	SLTNode* phead = NULL;
	SLTNode* ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		if (phead == NULL)
		{
			//SLTNode* newnode = BuySLTNode(i);
			phead = ptail = BuySLTNode(i);
		}
		else
		{
			ptail->next = BuySLTNode(i);
			ptail = BuySLTNode(i);
		}
	}
	return phead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.3数据打印

在这里尽量养成一个好习惯，不要直接使用形式参数，最好在重新创建一个变量来接收形参，尽管后面不会用到，也要尽量创建新的变量。

void SLTPrint(SLTNode* phead)
{//打印数据
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

1.4单链表尾插

在这里看到用的是二级指针，因为将头结点设为NULL指针了，在传参的时候（形参是实参的一份临时拷贝），所以再传一级指针的时候，改变形参的时候，并不会对头结点（实参）造成影响。所以采用二级指针的方法，或者采用返回值的方法（这里并不提倡用，太麻烦）到后来用带头的链表时这些问题就都不在了。

void SLTPushBack(SLTNode** phead, SLTDataType x)
{//单链表尾插
	if (*phead == NULL)//判断头结点是否为NULL
	{
		*phead = BuySLTNode(x);
	}
	else
	{
		SLTNode* ptail = *phead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = BuySLTNode(x);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.5单链表尾删

在尾删的情况下就要判断一下该链表是否为NULL，在NULL的情况下在删除也会出现错误。还要判断一下是否就只有头结点一个结点，如果是就可以直接释放头结点就可以了，因为是动态开辟的空间所以需要释放。

void SLTPopBack(SLTNode** phead)
{//单链表尾删
	assert(*phead);
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* ptail = *phead;
		while (ptail->next->next)
		{
			ptail = ptail->next;
		}
		free(ptail->next);
		ptail->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.6单链表头插

void SLTPushFront(SLTNode** phead, SLTDataType x)
{//单链表头插
	SLTNode* newnode = BuySLTNode(x);
	if (*phead == NULL)
	{
		*phead = BuySLTNode(x);
	}
	else
	{
		SLTNode* ptail = *phead;
		*phead = newnode;
		(*phead)->next = ptail;
		ptail = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.7单链表头删

头删和尾删的过程是差不多的，记住要判断是否为NULL,为NULL就不能再删除了。

void SLTPopFront(SLTNode** phead)
{//单链表头删
	assert(*phead);
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* ptail = (*phead)->next;
		*phead = ptail;
		ptail = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.8查找数据

查找数据，再找到就返回它当前的结点地址，如果没有找到就返回NULL
这里就不需要判断是否为NULL了,因为空也是可以查找的，同样也是没找到所以也返回空。

SLTNode* SLTFind(SLTNode* plist, SLTDataType x)
{//查找数据
	SLTNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

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

1.9在指定位置后面插入

在这里指定的位置需要断言一下，不能为NULL，而在这段代码的下面是在指定位置插入的可以对比一下差别，当在当前位置插入时，指定位置为头结点时可以直接调用头插。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//指定当前位置后面删除
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	if (pos->next == NULL)
	{
		pos->next = newnode;
	}
	else
	{
		SLTNode* ptail = pos->next;
		pos->next = newnode;
		newnode->next = ptail;
		newnode->data = x;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//指定位置插入
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySLTNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.10指定位置删除

下面的两段代码分别是在指定位置后面删除，和删除指定位置。这里也是需要断言一下，并且释放被删除的空间，删除指定位置如果是删除头结点一样是可以调用头删。

void SLTEraseAfter(SLTNode* pos)//指定位置后面删除
{
	assert(pos);
	if ((pos->next) != NULL)
	{
		SLTNode* ptail = pos->next->next;
		free(pos->next);
		pos->next = ptail;
	}
}
1
2
3
4
5
6
7
8
9
10
11

void SLTErase(SLTNode** pphead, SLTNode* pos)
{//指定位置删除
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* 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

1.11销毁数据

这里是将所有的数据都进行删除，全部释放，并且置为空，这里也是需要断言一下。

void SLTDestroy(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next ==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* cur = *pphead;

		while (cur)
		{
			SLTNode* next = cur->next;
			free(cur);
			cur = next;

		}
		*pphead = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在最后简单的说一下为什么有的时候用二级指针，有的时候用一级指针，简单理解就是当你认为需要改变数据的内容时就用二级指针，比如添加数据和删除数据都是需要改变数据所以用二级指针，而打印和查找就只是调用数据并不修改所以用一级指针。

2.SLT.h

SLT.h中是一些头文件，结构体的生成，还有对功能函数的实现，对类型的自定义，因为在这里自定义会对后来如果改数据类型的时候有很大的方便。

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include
#include
#include

typedef int SLTDataType;
//自定义
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;

}SLTNode;
//创建结构体
SLTNode* BuySLTNode(SLTDataType x);
//创建新的结点
SLTNode* CreateSList(int n);
//创建连续数据的链表
void SLTPrint(SLTNode* phead);
//打印数据
void SLTPushBack(SLTNode** phead, SLTDataType x);
//尾插
void SLTPopBack(SLTNode** phead);
//尾删
void SLTPushFront(SLTNode** phead, SLTDataType x);
//头插
void SLTPopFront(SLTNode** phead);
//头删

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 单链表查找


void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表在pos位置之后插入x
void SLTEraseAfter(SLTNode* pos);
// 单链表删除pos位置之后的值


void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos之前插入x

void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos位置
void SLTDestroy(SLTNode** pphead);
//销毁数据
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

3.test.c

下面就是对链表功能的一些测试。

#define _CRT_SECURE_NO_WARNINGS 1
#include"SLT.h"
int main()
{
	SLTNode* SLT = CreateSList(5);
	SLTPrint(SLT);
	SLTPushBack(&SLT, 6);
	SLTPrint(SLT);
	SLTPopBack(&SLT);
	SLTPrint(SLT);
	SLTPushFront(&SLT,9);
	SLTPrint(SLT);
	SLTPopFront(&SLT);
	SLTPrint(SLT);
	SLTNode* SLF=SLTFind(SLT, 4);
	if (SLF == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了！\n");
	}

	SLTPrint(SLF);
	SLTInsertAfter(SLF,9);
	SLTPrint(SLT);
	SLTNode* SLC = SLTFind(SLT, 9);
	SLTEraseAfter(SLC);
	SLTPrint(SLT);
	SLTInsert(&SLT,SLT, 8);
	SLTPrint(SLT);
	SLTErase(&SLT,SLF);
	SLTPrint(SLT);

	SLTDestroy(&SLT);
	SLTPrint(SLT);

	return 0;
}
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

四、顺序表和链表的优缺点

顺序表的优点
1️⃣ 顺序表的内存空间连续,物理上一定连续。
2️⃣ 支持随机访问，可以高效的按下标进行操作，时间复杂度是O(1)。
3️⃣尾插、尾删效率较高，时间复杂度是O(1)。
顺序表的缺点
1️⃣在任意位置和头结点插入删除，效率低，要将数据向后移时间复杂度为O(N)。
2️⃣顺序表长度固定，有时需要扩容，扩容可能还会在成空间浪费。
链表的优点
1️⃣不用担心扩容问题，也不会造成空间浪费。
2️⃣链表的插入和删除操作的效率较高，可以把通过地址直接改变节点的指向。
3️⃣逻辑上连续，但物理上不一定连续。
链表的缺点
1️⃣链表不支持随机访问，查找元素效率低，需要遍历节点，时间复杂度是O(n)。