【数据结构初阶】一篇文章带你超深度理解【单链表】

云边有个稻草人

发布于 2024-10-21 19:55:17

8900

代码可运行

文章被收录于专栏：C++领域相关博客C++领域相关博客

运行总次数：0

代码可运行

正文开始——

前言：

前面我们学习了顺序表，实现了对数组内容增删查改等操作，但是顺序表仍然存在一些缺陷。

中间/头部的插入删除，时间复杂度为O(N)；
增容需要申请新空间，拷贝数据，释放旧空间，这是不小的消耗；
增容一般是成2倍的增长，大概率会有一些空间的浪费。

那我们该如何解决上面的问题呢？下面我们来学习一下链表。

1、链表的概念和结构

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

2、单链表（Single List，简写SList）的实现

上面我们了解了链表的概念和结构，链表又分为很多种，今天我们先学习链表之一单链表。

2.1 定义链表（结点）的结构

//定义链表（结点）的结构

typedef int SLTDataType;
typedef struct SListNode {
	SLTDataType data;  
	struct SListNode* next;
}SLTNode;

2.2 创建一个链表

这里申请空间使用 malloc，在链表里面不存在增容的操作，想插入数据直接申请一个新的结点即可！用 calloc 也可以，calloc会让申请空间的内容初始化为0。

【代码】

test.c

//创建一个链表
void creatSList()
{
	//链表是由一个一个的结点组成的

	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将结点之间连接起来
	node1->next=node2;
	node2->next=node3;
	node3->next=node4;
	node4->next = NULL;

}

2.3 打印链表

【思路图解】

【代码】

//链表的打印

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

2.4 尾插

【思路图解】

【代码】

SList.c

//申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		perror("malloc file!");
		exit(1);
	}
	node->data = x;
	node->next = NULL;

	return node;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请一个新结点
	SLTNode* newnode = SLTBuyNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* pcur = *pphead;

		//找尾结点
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
    //plist为指向第一个结点的指针
	SLTPushBack(&plist,100);
	SLTPrint(plist);
}

int main()
{
	SListTest01();
	return 0;
}

【验证】

【注意】

在 test.c 里面尾插时传的是&plist ，而不是 plist。我们希望形参的改变影响实参，所以我们取实参的地址。plist 作为参数传的是一个指针变量而不是一个地址，只有 &plist （有&）才算是真正的取地址使得形参的改变影响实参。用二级指针来接收。
找尾结点。循环的条件是 pcur->next，而不是 pcur。因为 pcur->next 为NULL跳出循环时，说明 pcur 为尾结点，当 pcur 为空跳出循环时，说明 pcur 是尾结点的下一个节点，而不是尾结点。
pphead==&plist；*pphead==plist（指向第一个结点的指针）。
assert (pphead)；传过来的地址不能为空。

2.5 头插

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	//申请一个新结点
	SLTNode* newnode = SLTBuyNode(x);

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

test.c

void SListTest01()
{
    //验证尾插
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPushBack(&plist,100);
	SLTPrint(plist);
    
    //验证头插
	SLTPushFront(&plist, 200);
	SLTPrint(plist);
}

int main()
{
	SListTest01();
	return 0;
}

【验证】

2.6 尾删

各结点的地址应为0x0012FF...，在此纠正下面的错误。谅解哈~~~

【思路图解】

当链表内不止一个结点时

当链表内只有一个结点时

【代码】

SList.c

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表为空，不可删除
	assert(pphead && *pphead);

	//处理只有一个结点的情况，要删除的就是头结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找 ptail 和 prev
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPushBack(&plist,100);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	SLTPopBack(&plist);
	SLTPrint(plist);
}

int main()
{
	/*createSList();*/
	SListTest01();
	return 0;
}

【验证】

2.7 头删

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//头删
void SLTPopFront(SLTNode** pphead)
{
	//链表不为空
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPushBack(&plist,100);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	SLTPopFront(&plist);
	SLTPrint(plist);

}

int main()
{
	/*createSList();*/
	SListTest01();
	return 0;
}

【验证】

2.8 查找

各结点的地址应为0x0012FF...，在此纠正下面的错误。

思路简单，直接上代码：

SList.c

//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

【注意】SLTNode* pcur = phead，重新定义一个指针变量 pcur 指向第一个结点，让 pcur 来遍历链表，防止头结点丢失。

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPushBack(&plist,100);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTNode* find = SLTFind(plist, 2);
	if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	}
}

【验证】

2.9 在指定位置之前插入数据

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//申请一个新的结点
		SLTNode* newnode = SLTBuyNode(x);

		//找pos的前一个结点prev
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 2);
	/*///*if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	//}*/

	SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist, find, 100);
	SLTPrint(plist);

}

【验证】

2.10 在指定位置之后插入数据

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 2);
	/*///*if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	//}*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist, find, 100);
	SLTPrint(plist);*/

	SLTNode* find = SLTFind(plist, 2);
	SLTInsertAfter(find, 100);
	SLTPrint(plist); 

}

【验证】

2.11 删除pos结点

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//删除pos结点
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
	assert(pphead && *pphead);
    //这里对pos进行限制，链表中必须有pos这个结点，在查找中若没有pos结点则返回NULL
	assert(pos);

	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到prev：pos的前结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 2);
	/*///*if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	//}*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist, find, 100);
	SLTPrint(plist);*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsertAfter(find, 100);
	SLTPrint(plist); */

	SLTNode* find = SLTFind(plist, 2);
	SLTErase(&plist, find);//这里的find由pos接收，SLTFind若没找到存储2这个结点则返回NULL
	SLTPrint(plist); 

}

【验证】

2.12 删除pos之后的结点

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 2);
	/*///*if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	//}*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist, find, 100);
	SLTPrint(plist);*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsertAfter(find, 100);
	SLTPrint(plist); */

	//SLTNode* find = SLTFind(plist, 2);
	//SLTErase(&plist, find);
	//SLTPrint(plist); 

	SLTNode* find = SLTFind(plist, 2);
	SLTEraseAfter(find);
	SLTPrint(plist); 

}

【验证】

2.13 销毁链表

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//销毁链表
void SListDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
    //*pphead=plist，链表为空，也要把*pphead置为空
	*pphead = NULL;
}

【验证】