单向--＞不带头--＞非循环链表（简称：单链表）-Toy模板网

这篇具有很好参考价值的文章主要介绍了单向--＞不带头--＞非循环链表（简称：单链表）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、链表的介绍

1.链表的概念

2.单链表的节点类型

3.单链表简图

二、单链表的增删查改

1.单链表的头插

2.单链表的尾插

3.单链表的头删

4.单链表的尾删

5.单链表pos位置之后插入一个节点

6.单链表删除pos位置后的一个节点

一、链表的介绍

1.链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针链接次序实现的。（可以和数组进行比较理解，数组中的相邻元素在内存心中的地址是连续的，不需要额外的指针）

2.单链表的节点类型

链表的节点一般是一个结构体类型的变量，结构体成员包括一个有效数据value和一个指向下一个节点的结构体类型指针next（如果是双向链表，还会有一个指向上一个节点的结构体类型指针prev）。代码如下：

struct SListNode
{
SLTDateType data;
struct SListNode* next;
};

下文均使用typedef struct SListNode SListNode

3.单链表简图

单向--＞不带头--＞非循环链表（简称：单链表）,链表,数据结构

单链表的最后一个节点已经不需要指向下一个节点的指针，所以next=NULL ，最后一个节点指向空指针是单链表的结束方式。

二、单链表的增删查改

1.单链表的头插

简图：

注：pList存储的是链表头节点的地址

单向--＞不带头--＞非循环链表（简称：单链表）,链表,数据结构

代码实现：文章来源地址https://www.toymoban.com/news/detail-646117.html

// 单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
	if (NewNode == NULL)
	{
		perror("malloc:");
		return NULL;
	}
	NewNode->data = x;
	NewNode->next = *pplist;
	*pplist = NewNode;
}

2.单链表的尾插

简图：

单向--＞不带头--＞非循环链表（简称：单链表）,链表,数据结构

代码实现：

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
	if (NewNode == NULL)
	{
		perror("malloc:");
		return;
	}
	NewNode->data = x;
	NewNode->next = NULL;
	if (*pplist == NULL)
	{
		*pplist = NewNode;
	}
	else
	{
		SListNode* cur = *pplist;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = NewNode;
	}
}

3.单链表的头删

简图：

单向--＞不带头--＞非循环链表（简称：单链表）,链表,数据结构

代码实现：

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tmp = *pplist;
		*pplist = (*pplist)->next;
		free(tmp);
		tmp = NULL;
	}
}

4.单链表的尾删

简图：

单向--＞不带头--＞非循环链表（简称：单链表）,链表,数据结构

代码实现：

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* prev = *pplist;
		SListNode* cur = prev->next;
		while (cur->next)
		{
			cur = cur->next;
			prev = prev->data;
		}
		prev->next = NULL;
		free(cur);
		cur = NULL;
	}
}

5.单链表pos位置之后插入一个节点

简图：

单向--＞不带头--＞非循环链表（简称：单链表）,链表,数据结构

代码实现：

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
	if (NewNode == NULL)
	{
		perror("malloc:");
		return;
	}
	NewNode->data = x;
	if (pos == NULL)
	{
		NewNode->next = NULL;
		pos = NewNode;
	}
	else if (pos->next == NULL)
	{
		NewNode->next = NULL;
		pos->next = NewNode;
	}
	else
	{
		NewNode->next = pos->next;
		pos->next = NewNode;
	}
}

6.单链表删除pos位置后的一个节点

简图：

单向--＞不带头--＞非循环链表（简称：单链表）,链表,数据结构

代码实现：

// 单链表删除pos位置之后的节点
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;
}

到了这里，关于单向--＞不带头--＞非循环链表（简称：单链表）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！