探究数据结构：单链表的实战攻略
✨✨ 欢迎大家来到贝蒂大讲堂✨✨

养成好习惯，先赞后看哦~

所属专栏：数据结构与算法 贝蒂的主页：Betty‘s blog

前语

在上一章节中咱们解说了数据结构中的次序表，知道了次序表的空间是接连存储的，这与数组非常相似，为咱们随机访问数据供给了便利的条件。但是同时当刺进数据时或许存在移动数据与扩容的情况，这大大增加咱们的时刻与空间成本。为了处理这个问题，就要学习咱们今天要解说的链表。

1. 什么是链表

链表是一种物理存储结构上非接连、非次序的存储结构，数据元素的逻辑次序是经过链表中的指针链接次序完成的 。与次序表不同，链表的存储数据在内存是随机分布的。

2. 链表的分类

链表的种类多种多样，其间最常见的有八种，它们大致能够分为三类：

2.1 单向或许双向

探究数据结构：单链表的实战攻略

2.2 带不带头节点

探究数据结构：单链表的实战攻略

2.3 循环不循环

探究数据结构：单链表的实战攻略

本专栏将挑选其间两种常见链表进行解说，那便是无头单向非循环链表与与带头双向循环链表，这两种优点主要有：

  • 无头单向非循环链表：结构简略，一般不会单独用来存数据。实践中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。别的这种结构在笔试面试中呈现许多。
  • 带头双向循环链表：结构最复杂，一般用在单独存储数据。实践中运用的链表数据结构，都是带头双向循环链表。别的这个结构虽然结构复杂，但是运用代码完成以后会发现结构会带来许多优势，完成反而简略了，后面咱们代码完成了就知道了。

3. 单链表的功用

单链表的主要功用有以下几个：

  1. 打印单链表中的数据。
  2. 对单链表进行头插(最初刺进数据)。
  3. 对单链表进行头删(最初删去数据)。
  4. 对单链表进行尾插(末尾刺进数据)。
  5. 对单链表进行尾删(末尾删去数据)。
  6. 对单链表进行查找数据。
  7. 对单链表数据进行修正。
  8. 恣意方位的删去和刺进数据。
  9. 销毁单链表。

4. 单链表的界说

单链表的结点界说方法与咱们以往界说的方法都不同，它是一个结构体中包含两个成员。一个是存储数值，一个存放下一个结点的地址。

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

实践内存存储结构：

探究数据结构：单链表的实战攻略

5. 单链表功用完成

5.1 打印单链表

打印链表需求对函数传参指向链表的指针，首先为了保证链表不为空(NULL)，需求对其进行断言。

(1) 代码完成

void PrintSList(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}

(2) 复杂度剖析

  • 时刻复杂度：因为需求遍历整个链表，明显时刻复杂度为O(N)。
  • 空间复杂度：打印链表不需求分外的空间，所以空间复杂度为O(1).

5.2 单链表头插

(1) 创立结点

单链表每次刺进都需求刺进一个节点，所以咱们最好写一个创立节点的函数方便后续调用。

SListNode* SListCreatNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
        	return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

(2) 头插代码完成

单链表的头插与次序表头插最大的不同便是单链表传参需求二级指针。因为头插数据需求改动一级指针plist的指向，而形参的改动无法影响实参，所以需求二级指针才能改动一级指针plist的指向。

void SListPushFront(SListNode** plist, SLTDataType x)
{
	assert(plist);
	SListNode* newnode = SListCreatNode(x);
	newnode->next = *plist;
	*plist = newnode;
}

(3) 复杂度剖析

  • 时刻复杂度：不需求额定时刻的耗费，时刻复杂度为O(1)。
  • 空间复杂度：固定发明一个节点，空间复杂度为O(1)。

5.3 单链表头删

头删与头插相似，都或许需求改动plist的指向，所以也需求二级指针。而且也需求避免链表为空的情况产生。

(1) 代码完成

void SListPopFront(SListNode** plist)
{
	assert(plist);
	assert(*plist);
	SListNode* cur = (*plist)->next;
	free(*plist);
	*plist = cur;
}

(2) 复杂度剖析

  • 时刻复杂度：不需求额定时刻的耗费，时刻复杂度为O(1)。
  • 空间复杂度：不需求分外的空间耗费，空间复杂度为O(1)。

5.4 单链表尾插

当链表为空时，单链表尾插就会变成单链表头插，也需求改动plist的指向。其余情况即可经过循环寻找尾节点。

(1) 代码完成

void SListPushBack(SListNode** plist, SLTDataType x )
{
	assert(plist);
	if (*plist== NULL)
	{
		*plist = SListCreatNode(x);
	}
	else
	{
		SListNode* ptail = *plist;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = SListCreatNode(x);
	}
}

(2) 复杂度剖析

  • 时刻复杂度：需求遍历整个链表，时刻复杂度为O(N)。
  • 空间复杂度：固定发明一个节点，空间复杂度为O(1)。

5.5 单链表尾删

与单链表尾插相似，当链表只要一个头结点时需求将plist置为空，所以也需求二级指针。而且也需求避免链表为空的情况产生。

(1) 代码完成

void SListPopBack(SListNode** plist)
{
	assert(plist);
	assert(*plist);//避免链表为空
	if ((*plist)->next == NULL)
	{
		free(*plist);
		*plist = NULL;
	}
	else
	{
		SListNode* ptail = *plist;
		while (ptail->next->next)
		{
			ptail = ptail->next;
		}
		free(ptail->next);
		ptail->next = NULL;
	}	
}

(2) 复杂度剖析

  • 时刻复杂度：需求遍历整个链表，时刻复杂度为O(N)。
  • 空间复杂度：不需求分外的空间耗费，空间复杂度为O(1)。

5.6 单链表的查找

如果找到就回来这个节点的地址，否则就回来空指针NULL

(1) 代码完成

SListNode* SListSearch(SListNode* plist, SLTDataType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

(2) 时刻复杂度

  • 时刻复杂度：或许需求遍历整个链表，时刻复杂度为O(N)。
  • 空间复杂度：不需求分外的空间耗费，空间复杂度为O(1)。

5.6 单链表的修正

单链表的修正能够与查找配套运用。

(1) 代码完成

void SListModify(SListNode*plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur == pos)
		{
			cur->data = x;
			break;
		}
		cur = cur->next;
	}
}

(2) 复杂度剖析

  • 时刻复杂度：或许需求遍历整个链表，时刻复杂度为O(N)。
  • 空间复杂度：不需求分外的空间耗费，空间复杂度为O(1)。

5.7 单链表恣意方位的刺进

(1) 代码完成

某个方位之前刺进，当链表为空或许在头节点刺进时运用头插。

void SListInsertF(SListNode** plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	if (*plist == pos || *plist == NULL)
	{
		SListPushFront(plist, x);//头插
	}
	else
	{
		SListNode* newnode = SListCreatNode(x);
		SListNode* prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

某个方位之后刺进，当链表为空或许在尾节点刺进时运用尾插。

void SListInsertB(SListNode** plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	if (*plist == NULL||pos->next==NULL)
	{
		SListPushBack(plist, x);//尾插
	}
	else
	{
		SListNode* tmp = pos->next;
		SListNode* newnode = SListCreatNode(x);
		pos->next = newnode;
		newnode->next = tmp;
	}
}

(2) 复杂度剖析

  • 时刻复杂度：无论向前刺进还是向后刺进都或许需求遍历整个链表，所以时刻复杂度为O(N)。
  • 空间复杂度：固定发明一个节点，空间复杂度为O(1)。

5.8 恣意方位的删去

恣意方位的删去需求提前保存好前一个节点与后一个节点的方位。

(1) 代码完成

void SListErase(SListNode** plist, SListNode* pos)
{
	assert(plist);
	assert(*plist);
	assert(pos);
	if (*plist == pos)
	{
		SListPopFront(plist);//头删
	}
	SListNode* prev = *plist;
	while (prev->next!=pos)
	{
		prev = prev->next;
	}
	SListNode* tmp = pos->next;
	prev->next = tmp;
	free(pos);
	pos = NULL;
}

(2) 复杂度剖析

  • 时刻复杂度：或许需求遍历整个链表，所以时刻复杂度为O(N)。
  • 空间复杂度：固定发明一个节点，空间复杂度为O(1)。

5.9 销毁链表

销毁链表需求顺次遍历释放节点。

(1) 代码完成

void SListDestroy(SListNode** plist)
{
	assert(plist);
	assert(*plist);
	SListNode* cur = *plist;
	while (cur)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur =tmp;
	}
	*plist = NULL;//避免野指针
}

(2) 复杂度剖析

  • 时刻复杂度：需求遍历整个链表，所以时刻复杂度为O(N)。
  • 空间复杂度：不需求分外的空间耗费，空间复杂度为O(1)。

6. 完好代码

(1) SList.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;
void PrintSList(SListNode* plist);//打印链表
void SListPushFront(SListNode** plist, SLTDataType x);//头插
void SListPopFront(SListNode** plist);//头删
void SListPushBack(SListNode** plist,SLTDataType x);//尾插
void SListPopBack(SListNode** plist);//尾删
SListNode* SListSearch(SListNode* plist, SLTDataType x);//查找
void SListModify(SListNode* plist, SListNode* pos, SLTDataType x);//修正
void SListInsertF(SListNode** plist, SListNode* pos, SLTDataType x);//恣意方位之前刺进
void SListInsertB(SListNode** plist, SListNode* pos, SLTDataType x);//恣意方位之后刺进
void SListErase(SListNode** plist, SListNode* pos);//恣意方位的删去
void SListDestroy(SListNode** plist);//销毁链表

(2) SList.c

#include"SList.h"
SListNode* SListCreatNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void PrintSList(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}
void SListPushFront(SListNode** plist, SLTDataType x)
{
	assert(plist);
	SListNode* newnode = SListCreatNode(x);
	newnode->next = *plist;
	*plist = newnode;
}
void SListPopFront(SListNode** plist)
{
	assert(plist);
	assert(*plist);//避免链表为空
	SListNode* cur = (*plist)->next;
	free(*plist);
	*plist = cur;
}
void SListPushBack(SListNode** plist, SLTDataType x )
{
	assert(plist);
	if (*plist== NULL)
	{
		*plist = SListCreatNode(x);
	}
	else
	{
		SListNode* ptail = *plist;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = SListCreatNode(x);
	}
}
void SListPopBack(SListNode** plist)
{
	assert(plist);
	assert(*plist);//避免链表为空
	if ((*plist)->next == NULL)
	{
		free(*plist);
		*plist = NULL;
	}
	else
	{
		SListNode* ptail = *plist;
		while (ptail->next->next)
		{
			ptail = ptail->next;
		}
		free(ptail->next);
		ptail->next = NULL;
	}
}
SListNode* SListSearch(SListNode* plist, SLTDataType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SListModify(SListNode*plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur == pos)
		{
			cur->data = x;
			break;
		}
		cur = cur->next;
	}
}
void SListInsertF(SListNode** plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	if (*plist == pos || *plist == NULL)
	{
		SListPushFront(plist, x);//头插
	}
	else
	{
		SListNode* newnode = SListCreatNode(x);
		SListNode* prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}
void SListInsertB(SListNode** plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	if (*plist == NULL||pos->next==NULL)
	{
		SListPushBack(plist, x);//尾插
	}
	else
	{
		SListNode* tmp = pos->next;
		SListNode* newnode = SListCreatNode(x);
		pos->next = newnode;
		newnode->next = tmp;
	}
}
void SListErase(SListNode** plist, SListNode* pos)
{
	assert(plist);
	assert(*plist);
	assert(pos);
	if (*plist == pos)
	{
		SListPopFront(plist);//头删
	}
	SListNode* prev = *plist;
	while (prev->next!=pos)
	{
		prev = prev->next;
	}
	SListNode* tmp = pos->next;
	prev->next = tmp;
	free(pos);
	pos = NULL;
}
void SListDestroy(SListNode** plist)
{
	assert(plist);
	assert(*plist);
	SListNode* cur = *plist;
	while (cur)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur =tmp;
	}
	*plist = NULL;//避免野指针
}
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。