【数据结构之单链表】

数据结构学习笔记---003

数据结构之单链表

数据结构之单链表

前言：
前篇学习了数据结构的顺序表那么这篇继续学习数据结构线性表的第二种存储方法，链式存储的单链表。
/知识点汇总/

1、什么是单链表?

1.1、概念及结构

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

由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。

单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

单链表（Singly Linked List）是一种常用的数据结构，它由若干个节点组成，每个节点包含两部分：数据域和指针域。
数据域用于存储数据，而指针域则用于指向下一个节点的地址。单链表中每个节点只有一个指针域，指向下一个节点，最后一个节点的指针域指向NULL，表示链表的结尾。

2、单链表接口的实现

在实际应用中，单链表的存储思想就是用指针表示各结点之间的逻辑关系。本质就是掌握好结点间的链式处理。

然后与前篇学的顺序表不同，就不存在扩容的问题了，但仍然需要注意及时释放动态开辟的内存空间等问题。
实现过程继续采用阶段性测试，既方便调试也方便及时解决问题。
另外单链表又分为带头结点和不带头结点的方式，这里用不带头的进行编写，具体可根据实际符合的应用场景决定。

2.1、单链表的SList.h

2.1.1、定义单链表的结点存储结构

因为是采用的多种类型的数据，所以适用于结构体类型。然后知道了需要一个数据域和指针域，所以定义结构体如下所示：

//定义单链表的动态存储
typedef int SLNDataType;//这里的重命名主要作用是，不能保证每次使用都是整型，所以只需要改这里为其它类型更健壮和便利
//Single List
typedef struct SLNode    //定义单链表结点类型为结构体类型包括数据域和指针域
{
   
	SLNDataType val;         //结点数据域
	struct SLNode* next; //结点指针域，存放下一个结点的地址
}SLNode;

2.1.2、声明单链表各个接口的函数

//遍历打印链表
void SLPrint(SLNode* pphead);
//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x);
//尾删
void SLTPopBack(SLNode** pphead);
//头删
void SLTPopFront(SLNode** pphead);
//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x);
//pphaed = NULL ,错误
//*pphead = NULL，空表
//(*pphead)->next = NULL，一个结点
//在pos位置的前面插入
void SLTInsert(SLNode** pphead,SLNode* pos, SLNDataType x);
//删除pos的位置结点
void SLTErase(SLNode** pphead, SLNode* pos);
//在pos的位置之后的操作，就不存在头插头删的情况，参数就不用传plist了
//在pos的位置之后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x);
//在pos的位置之后删除
void SLTEraseAfter(SLNode* pos);
//销毁单链表
void SLTDestory(SLNode** pphead);

2.2、单链表的SList.c

主要还是要完成 SList.h 接口对应的 .c 功能函数。
有了前篇的意识和基础，对于单链表的初始化可以有但没必要，因为不带头结点本身不用就是空表，那么就体现在后面建立结点函数的写法中对初始化的处理了。但为了对比和理解，把带头结点的常规写法也写一下，但后面继续以不带头的结点写。
初始化单链表(带头结点)：

Node* InitList()
{
   
  Node* first = (Node*)malloc(sizeof(Node)); //生成头结点
  first->next = NULL;                        //头结点的指针域置空
  return first;
}

2.2.1、遍历打印链表

为了打印单链表的元素，这里需要像顺序表那样遍历，所以引用一个工作指针，依次访问指针域打印各个结点的数据域中元素。工作指针的本质是读数据域而不作更改，防止写动数据等问题。

//遍历打印链表
void SLPrint(SLNode* phead)
{
   
	SLNode* cur = phead;//定义工作指针，防止更改了phead的地址
	while (cur != NULL)
	{
   
		printf("%d->", cur->val);//读数据域
		cur = cur->next;        //偏移指针域
	}
	printf("NULL\n");
}

2.2.2、销毁单链表

为了避免忘记销毁开辟的动态内存空间。所以这里使用动态存储方法，那么通常把初始化和销毁一块就写出来了。

//顺序表的销毁
void SLDestory(SL* ps1)
{
   
	//暴力检查
	assert(ps1);//一定不能为空
	if (ps1->a != NULL)
	{
   
		free(ps1->a);
		ps1->a = NULL;
		ps1->size = 0;
		ps1->capacity = 0;
	}
}

2.2.3、打印单链表元素

为了直观的体现数据元素是否成功操作，所以接着写出打印接口函数。

//打印顺序表
void SLPrint(SL* ps1)
{
   
	//暴力检查
	assert(ps1);//一定不能为空
	for (int i = 0; i < ps1->size; i++)
	{
   
		printf("%d ", ps1->a[i]);
	}
	printf("\n");
}

2.2.4、单链表的基本操作

完成了上述函数的功能，那么就可以实现单链表的基本操作了。插入和删除以及查找（无非就是增删改查）。
头插和头删；尾插和尾删。
其次，对于开辟新结点的操作多个函数都涉及到，所以可以封装成单独的CreateNode函数，如下所示：

//开辟新结点，且next置空
SLNode* CreateNode(SLNDataType x)
{
   
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
   
		perror("malloc fail");
		//return;
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}

尾插、头插、尾删、头删的操作，需要注意一下，判空和空表的情况。

//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
   
	assert(pphead);
	//空结点的处理
	SLNode* newnode = CreateNode(x);
	if (*pphead == NULL)
	{
   
		*pphead = newnode;
	}
	else
	{
   
		//找尾（链表不为空，只需要下面的部分，但尽可能的健壮代码，所以需要考虑链表为空的情况）
		SLNode* tail = *pphead;
		//while (tail != NULL)，容易掉的坑，这样写画图很清楚的看到，链表并没有链接起来；而且除了作用域tail销毁，尾结点会存在内存泄漏的问题
		while (tail->next != NULL)
		{
   
			tail = tail->next;
		}
		//因为多个函数都需要开辟新节点，所以直接封装为函数
		//而且不能直接SLNode* newNode：来定义结构体来开辟，因为这里只能作用域为局部变量，所以需要malloc才行。
		//SLNode* newNode = (SListNode*)malloc(sizeof(SLNode));
		//SLNode* newnode = CreateNode(x);已放开头
		tail->next = newnode;
	}
}

//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
   
	assert(pphead);
	SLNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾删
void SLTPopBack(SLNode** pphead)
{
   
	//注意pphead一定不能为空，所以需要检查
	assert(*pphead);
	assert(pphead);
	//区分一个结点和多个结点

	//这两句的位置不同，对应的写法不同
	/*
	SLNode* tail = *pphead;
	//Node* prev = *pphead;//错误，初始化为*phead时，如果首结点被free时，那么prev就会成为野指针。
	SLNode* prev = NULL;
	if (tail->next == NULL)//一个节点
	{
		free(tail);
		tail = NULL;
	}
	*/
	if ((*pphead)->next == NULL)//一个节点
	{
   
		free(*pphead);
		*pphead = NULL;
	}
	else//找尾
	{
   
		//这两句的位置可以写这儿
		SLNode* tail = *pphead;
		//Node* prev = *pphead;//错误，初始化为*phead时，如果首结点被free时，那么prev就会成为野指针。
		SLNode* prev = NULL;

		while (tail->next != NULL)
		{
   
			/*tail = tail->next;
			prev = tail;*/
			//错误，注意顺序是不可以交换的，因为当tail到空时，还赋给prev就导致为野指针了
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
		//一种简化写法
		/*
		SLNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);//释放的是指针指向的内存空间，而不是指针本身
		tail->next = NULL;
		*/
	}
}
//头删
void SLTPopFront(SLNode** pphead)
{
   
	assert(*pphead);
	assert(pphead);
	//if ((*pphead)->next == NULL)//一个节点
	//{
   
	//	free(*pphead);
	//	*pphead = NULL;
	//}

	//一个以及以上结点都能处理
	//方法1：
	//SLNode* tail = *pphead;
	//tail = tail->next;
	//free(*pphead);
	//*pphead = tail;
		//方法2：
	//SLNode* tail = *pphead;
	//*pphead = (*pphead)->next;
	//free(tail);

	//方法3：
	SLNode* tmp = (*pphead)->next;;
	free(*pphead);//注意顺序不能交换
	*pphead = tmp;
}

查找、在pos位置的前面插入、删除pos的位置、在pos的位置之后插入和在pos的位置之后删除操作。

//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
   
	assert(phead);
	SLNode* cur = phead;//定义工作指针，防止更改了phead的地址
	while (cur != NULL)
	{
   
		if (cur->val == x)
			return cur;
		cur = cur->next;        //偏移指针域
	}
	return NULL;
}
//在pos位置的前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
   
	/*assert(pphead);
	assert(*pphead);
	assert(pos);*///这种检查严格限定了pos一定为链表里的有效节点

	assert(pphead);
	assert((!pos && !(*pphead)) ||(pos && *pphead));//要么都是空，要么都不是空

	//对空处理
	if (*pphead == pos)
	{
   
		//调用头插
		SLTPushFront(pphead, x);
	}
	else//找插入结点的前一个结点
	{
   
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
   
			prev = prev->next;
		}
		SLNode* newnode = CreateNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
//删除pos的位置
void SLTErase(SLNode** pphead, SLNode* pos)
{
   
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//头结点梳理
	if ((*pphead)->next == NULL)
	{
   
		//调用头删
		SLTPopFront(pphead);
	}
	else
	{
   
		SLNode* prev = *pphead;
		if (prev == pos)
		{
   
			//调用头删
			SLTPopFront(pphead);
		}
		else
		{
   
			while (prev->next != pos)
			{
   
				prev = prev->next;
			}
			prev->next = pos->next;
			free(pos);
			pos = NULL;
		}
	}
}

//在pos的位置之后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
   
	assert(pos);
	SLNode* newnode = CreateNode(x);
	//经典错误，单链表断开，自己指向了自己
	/*pos->next = newnode;
	newnode->next = pos->next;*/

	newnode->next = pos->next;
	pos->next = newnode;
}

//扩展：只给pos位置，如何完成想在pos之前插入呢？
//只需要在pos后面插入，交换pos的结点值即可

//在pos的位置之后删除
void SLTEraseAfter(SLNode* pos)
{
   
	assert(pos);
	assert(pos->next);//因为当只有一个结点时，cur=pos->next,为空，所以对pos->next访问就非法访问了。
	SLNode* cur = pos->next;
	pos->next = cur->next;
	free(cur);
	cur = NULL;
}

3.3、单链表的main.c

简单的写几个测试应用，目的是检测各个接口函数是否满足需求，是否存在一些bug。

3.3.1、TestSL1()

主要检测尾插、头插、打印和销毁接口函数，以及参数的传址调用和传值调用。

#include "SList.h"
//测试1：
void TestSLT1()
{
   
	SLNode* plist = NULL;
	//SLTPushBack(plist, 1);//传参为SLNode*,要想实现操作，还得使用二级指针，所以这里必须传地址 ==>不然phead只是plist的临时拷贝
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);//尾插
	SLPrint(plist);//打印
	
	SLTPopBack(&plist);//尾删
	SLPrint(plist);
	
	SLTPushFront(&plist, 5);//头插
	SLPrint(plist);
	SLTPushFront(&plist, 6);//头插
	SLPrint(plist);
	
	SLTPopBack(&plist);//尾删
	SLPrint(plist);
	SLTPopBack(&plist);//尾删
	SLPrint(plist);
}
int main()
{
   
	TestSLT1();
	//TestSLT2();
	//TestSLT3();
	//TestSLT4();
	//TestSLT5();
	return 0;
}

测试效果展示：
在这里插入图片描述

3.3.2、TestSL2()

主要检测接口函数是否满足需求，并深刻认识指针、二级指针的应用。

#include "Seqlist.h"
//测试二：
void TestSLT2()
{
   
	SLNode* plist = NULL;
	//SLTPushBack(plist, 1);//传参为SLNode*,要想实现操作，还得使用二级指针，所以这里必须传地址 ==>不然phead只是plist的临时拷贝
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);//尾插
	SLPrint(plist);//打印

	SLTPopFront(&plist);
	SLPrint(plist);
}
int main()
{
   
	//TestSL1();
	TestSL2();
	//TestSL3();
	//TestSL4();
	//TestSL5();
	//TestSL6();
	//TestSL7();
	return 0;
}

效果展示：
在这里插入图片描述

4、单链表巩固练习

4.1、单链表巩固练习题01 — 求链表的中间节点

求链表的中间节点 — 经典快慢指针

#include "SList.h"
//定义单链表的结构体类型
struct ListNode
{
   
	int val;
	struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{
   
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	while (fast && fast->next)
	{
   
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}

int main()
{
   
	SLNode* plist = NULL;
	//SLTPushBack(plist, 1);//传参为SLNode*,要想实现操作，还得使用二级指针，所以这里必须传地址 ==>不然phead只是plist的临时拷贝
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);//尾插
	SLPrint(plist);//打印

	struct ListNode* pos = middleNode(plist);
	printf("pos = %d\n", pos->val);
	return 0;
}

4.2、单链表巩固练习题02 — 移除链表元素

移除链表元素 – 返回新的头结点
方法1：遍历删除

#include "SList.h"
//定义单链表的结构体类型
struct ListNode
{
   
	int val;
	struct ListNode* next;
};
struct ListNode* removeELements(struct ListNode* head, int val)
{
   
	struct ListNode* prev = NULL;//prev的作用，是在于删除对应结点后，能找到next断开之后再链接
	struct ListNode* cur = head;
	while (cur)
	{
   
		if (cur->val == val)
		{
   
			struct ListNode* tmp = cur->next;
			free(cur);
			if (prev)//必须判断首节点是否val,被free后，可能为空
				prev->next = tmp;
			else//否则,新的头结点更新
				head = tmp;
			cur = tmp;
		}
		else
		{
   
			prev = cur;
			cur = cur->next;
		}
	}
	return head;
}

int main()
{
   
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));

	n1->val = 7;
	n2->val = 7;
	n3->val = 2;
	n4->val = 3;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* head = removeELements(n1, 7);
	SLPrint(head);
	return 0;
}

方法2：遍历把不是val的结点链接到新链表，添加尾指针

#include "SList.h"
//定义单链表的结构体类型
struct ListNode
{
   
	int val;
	struct ListNode* next;
};
//打印链表
void SLPrint1(struct ListNode* phead)
{
   
	struct ListNode* cur = phead;//定义工作指针，防止更改了phead的地址
	while (cur != NULL)
	{
   
		printf("%d->", cur->val);//读结点域
		cur = cur->next;        //偏移指针域
	}
	printf("NULL\n");
}
struct ListNode* removeELements(struct ListNode* head, int val)
{
   
	struct ListNode* newnode = NULL;
	struct ListNode* tail = NULL;
	struct ListNode* cur = head;
	while (cur)
	{
   
		//如果不是val把结点拿到新链表(新链表为空)
		if (cur->val != val)
		{
   
			//尾插：两种情况
			if (tail == NULL)
			{
   
				newnode = tail = cur;
			}
			else
			{
   
				tail->next = cur;
				tail = tail->next;
			}
			cur = cur->next;
		}
		else
		{
   
			struct ListNode* tmp = cur;
			cur = cur->next;
			free(tmp);
		}
	}
	if(tail)//注意最后尾节点的判空，防止野指针，同时判空处理空表
		tail->next = NULL;
	head = newnode;
	return head;
}

int main()
{
   
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));

	n1->val = 7;
	n2->val = 7;
	n3->val = 2;
	n4->val = 3;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* head = removeELements(n1, 7);
	SLPrint1(head);
	return 0;
}

方法3：添加哨兵位头结点
哨兵位的头结点，不存储有效数据置NULL

#include "SList.h"
//定义单链表的结构体类型
struct ListNode
{
   
	int val;
	struct ListNode* next;
};
//打印链表
void SLPrint1(struct ListNode* phead)
{
   
	struct ListNode* cur = phead;//定义工作指针，防止更改了phead的地址
	while (cur != NULL)
	{
   
		printf("%d->", cur->val);//读结点域
		cur = cur->next;        //偏移指针域
	}
	printf("NULL\n");
}
struct ListNode* removeELements(struct ListNode* head, int val)
{
   
	struct ListNode* newnode = NULL;
	struct ListNode* tail = NULL;
	struct ListNode* cur = head;
	//添加哨兵位
	newnode = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
	while (cur)
	{
   
		//如果不是val把结点拿到新链表(新链表为空)
		if (cur->val != val)
		{
   
			//尾插：两种情况
			tail->next = cur;
			tail = tail->next;
			cur = cur->next;
		}
		else
		{
   
			struct ListNode* tmp = cur;
			cur = cur->next;
			free(tmp);
		}
	}
	//哨兵位方法前面简化，而这里就需要处理
	tail->next = NULL;
	struct ListNode* tmp = newnode;
	newnode = newnode->next;
	free(tmp);
	head = newnode;//头结点next为首节点符合题目要求
	return head;
}

int main()
{
   
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));

	n1->val = 7;
	n2->val = 7;
	n3->val = 2;
	n4->val = 3;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* head = removeELements(n1, 7);
	SLPrint1(head);
	return 0;
}

4.3、单链表巩固练习题03 — 链表分割

链表分割 — 返回重新排列后的头指针,相对顺序不变
3 6 1 8 4 6 9 — val=5分割
3 1 4 (5)6 8 6 9
思路1：不带哨兵位，比较val小的放一个链表，大于等于val的放一个链表，再合并两个链表，同时注意判断两边链表为空的情况，即全比val大或者小的处理，所以相对于带头结点的操作就比较复杂。
思路2：带2个哨兵位，直接比较后，执行相应的尾插操作即可，最后合并。
建议采用带头结点的方法，更好处理这题

#include "SList.h"
//#include <cstddef>

//定义单链表的结构体类型
struct ListNode
{
   
	int val;
	struct ListNode* next;
};
//打印链表
void SLPrint1(struct ListNode* phead)
{
   
	struct ListNode* cur = phead;//定义工作指针，防止更改了phead的地址
	while (cur != NULL)
	{
   
		printf("%d->", cur->val);//读结点域
		cur = cur->next;        //偏移指针域
	}
	printf("NULL\n");
}
struct ListNode* removeELements(struct ListNode* phead, int x)
{
   
	struct ListNode* head1;
	struct ListNode* head2;
	struct ListNode* tail1;
	struct ListNode* tail2;
	//oj题，一般malloc不会申请失败，可不作检查
	head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	head2 = tail2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* cur = phead;
	while (cur)
	{
   
		//尾插 -- < val -->tail1
		if (cur->val < x)
		{
   
			tail1->next = cur;
			tail1 = tail1->next;
		}
		else//尾插 -- >= val -->tail2
		{
   
			tail2->next = cur;
			tail2 = tail2->next;
		}
		cur = cur->next;//判断一个走一个
	}
	//链接tail1和tail2
	tail1->next = head2->next;
	tail2->next = NULL;
	//更新头结点
	phead = head1->next;
	free(head1);
	free(head2);
	return phead;
}

int main()
{
   
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));

	n1->val = 7;
	n2->val = 7;
	n3->val = 2;
	n4->val = 3;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* head = removeELements(n1, 6);
	SLPrint1(head);
	return 0;
}

5、单链表总结

主要有以下两点：
与顺序表不同，单链表的元素不是连续存储的，而是通过指针相连形成链式结构。因此，单链表具有以下优缺点。
优点：
支持动态内存分配。由于单链表不需要预先分配一段连续的空间，因此可以根据实际需求动态地申请、释放节点空间，避免浪费内存。
支持高效的插入、删除操作。由于单链表中的节点是通过指针相连的，因此在插入、删除一个节点时，只需要修改其前驱节点或后继节点的指针即可，时间复杂度为O(1)O(1)O(1)。
缺点：
不支持随机访问。由于单链表中的节点不是连续存储的，因此不能像数组一样通过下标来直接访问一个元素，需要从头节点开始遍历整个链表才能访问任意位置的元素。