1. Toy模板网首页
  2. >Toy博客

数据结构《链表》无头单向非循环-动图详解

1年前作者：不会敲代码的小张:)分类：Toy博客阅读(10)违法举报

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

前言

前面学习了顺序表发现，顺序表虽然好，但也有很多不足的地方，比方说，顺序表是一块连续的物理空间，如果头插或者头删，那么整个数组的数据都要移动。但是链表不一样，链表是通过指针访问或者调整，链表是物理空间是不连续的，通过当前的next指针找到下一个。
插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可
链表的优点：
插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活
数据结构《链表》无头单向非循环-动图详解

链表的概念及结构

概念：
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
结构：
数据结构《链表》无头单向非循环-动图详解

注意：
1.从图上看，链式结构在逻辑上是连续的，但在物理上不一定连续
2.现实中节点一般都是从堆上申请出来的
3.从堆上malloc的空间是按照一定策略来分配的，第二次申请空间可能是连续的，也可能不是

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向或双向链表：
数据结构《链表》无头单向非循环-动图详解

带头节点或者不带头节点：
数据结构《链表》无头单向非循环-动图详解

循环或者非循环：

数据结构《链表》无头单向非循环-动图详解

最常用的两种链表

无头单向非循环链表：
数据结构《链表》无头单向非循环-动图详解
带头双向循环链表：
数据结构《链表》无头单向非循环-动图详解

————————————————

链表的创建

链表是由数据和指针组成
那么我们在创建链表的时候，需要一个指针指向下一个节点
如下：

typedef int SLTDataType;

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

}SListNode;

创建新的节点

创建新的节点，把要插入的值放进新的节点的data，然后再把next指针赋成空，最后返回这个节点的指针

//创建新的节点
SListNode* BuySLTNode(SLTDataType x)
{
	SListNode* ret = (SListNode*)malloc(sizeof(SListNode));
	if (ret == NULL)
	{
		perror("BuySLTNode");
		return NULL;
	}
	ret->data = x;
	ret->next = NULL;

	return ret;
}

尾插

既然是尾插，那就是在尾部插入元素

我们可以看到下面是用二级指针接收的，因为传过来的是一级指针的地址，所以我们要用二级指针接收，并且我们使用的时候要解引用，因为我们要改变的是一级指针本身

如果传过来的指针本身就是NULL，那就直接把新的节点赋给传过来的指针
如果不是空，那我们就找尾，找到尾之后，再把新的节点插入到尾部的next指针
注：
tail指针是指向元素当前位置，我们一般不直接使用原有的指针，因为我们要保留第一个元素指针的位置，以便后续使用。

//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);

	SListNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* tail = *pphead;
		//找尾
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

头插

我们把新节点的next指向第一个元素的指针，然后再把第一个节点的指针更新为newnode

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

	SListNode* newnode = BuySLTNode(x);
	SListNode* tail = *pphead;

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

尾删

分为三种情况：
1.链表没有元素，那我们直接断言解决
2.如果链表只有一个元素，那我们判断一下，然后free掉第一个指针指向的空间
3.链表多个元素，我们这里选择的是，判断tail->next->next是否为空，如果不为空，我们让tail指针向后走一步，再继续判断，直到tail->next->next为空，我们free掉tail->next即可

//尾删
void SLTPopBack(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);//如果*pphead为空，说明链表没有元素

	if ((*pphead)->next == NULL)//如果（*pphead）->next为空，说明链表只有一个元素，我们只需要free掉第一个指针指向的空间即可
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		//判断tail->next->next是否为空，如果不为空，tail向后走一步，再判断
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		//循环不满足，说明tail->next->next为空
		//我们只需要free掉tail的next
		free(tail->next);
		tail->next = NULL;
	}
}

头删

分为两种情况：
1.链表为空，直接用断言解决
2.链表多个元素，我们直接用tail指针保留第一个指针的位置，然后再更新第一个位置的指针，最后free掉刚刚保留的tail位置
数据结构《链表》无头单向非循环-动图详解

//头删
void SLTPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);

	SListNode* tail = *pphead;
	*pphead = tail->next;
	free(tail);
	tail = NULL;
}

查找

把phead指针赋给cur，如果cur->data和要查找的值相同，返回cur，如果不相同让cur继续向后走，直到相同位置，返回cur，如果走到NULL都没有相同的，说明没有。

//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;

	}
	return NULL;
}

指定位置插入

进来直接判断pos是不是第一个元素的空间，如果是，直接头插
走到else里，我们定义一个prev指针，记录pos前一个的位置，直到prev的next等于pos，然后把要插入的值放进prev的next位置，再把pos给newnode的next
数据结构《链表》无头单向非循环-动图详解

//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);
	SListNode* newnode = BuySLTNode(x);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

指定位置删除

判断要删除的节点是否就是第一个节点，如果是，直接调用头删
反之，定义一个prev指针记录pos的前一个位置，直到prev的next指针等于pos的时候，把pos的next赋给prev的next进行拼接，然后free掉pos即可
数据结构《链表》无头单向非循环-动图详解

//指定删除
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	//判断pos是否就是第一个节点
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

pos位置后插入

pos位置后插入相比指定插入，通俗易懂
直接把newnode的next指向pos的next，然后再把pos的next指向newnode
数据结构《链表》无头单向非循环-动图详解

//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x)
{
	assert(pos);

	SListNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

pos位置后删除

把pos的next给del，del是等会要删除的位置
然后pos的next指向del的next，最后free掉del
数据结构《链表》无头单向非循环-动图详解

//pos位置后删除
void SLTEease_After(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

打印

把phead给cur指针，让cur指针往后走，每次cur打印data数据，直到走到NULL。

//打印
void SLTPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

销毁

定义一个cur指针，再记录一下cur的下一个位置，然后free掉cur，再把刚刚记录的cur的next位置赋给cur，直到cur走到NULL为止
数据结构《链表》无头单向非循环-动图详解

//销毁
void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;

	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

完整代码

SList.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

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

}SListNode;

//打印
void SLTPrint(SListNode* phead);
//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SListNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SListNode** pphead);
//头删
void SLTPopFront(SListNode** pphead);

//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x);

//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);

//指定删除
void SLTErase(SListNode** pphead, SListNode* pos); 

//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x);

//pos位置后删除
void SLTErase_After(SListNode* pos);

//销毁
void SLTDestroy(SListNode** pphead);

SList.c

#include "SList.h"

//打印
void SLTPrint(SListNode* phead)
{
	SListNode* cur = phead;

	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL\n");
}

//创建新的节点
SListNode* BuySLTNode(SLTDataType x)
{
	SListNode* ret = (SListNode*)malloc(sizeof(SListNode));
	if (ret == NULL)
	{
		perror("BuySLTNode");
		return NULL;
	}
	ret->data = x;
	ret->next = NULL;

	return ret;
}

//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);

	SListNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* tail = *pphead;
		//找尾
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}

}

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

	SListNode* newnode = BuySLTNode(x);
	SListNode* tail = *pphead;

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

//尾删
void SLTPopBack(SListNode** pphead)
{
	assert(pphead);


	assert(*pphead != NULL);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;

		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}

}

//头删
void SLTPopFront(SListNode** pphead)
{
	assert(pphead);

	assert(*pphead != NULL);

	SListNode* tail = *pphead;
	*pphead = tail->next;
	free(tail);
	tail = NULL;

}

//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;

	}
	return NULL;
}


//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);
	SListNode* newnode = BuySLTNode(x);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;

	}
	
}
//指定删除
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x)
{
	assert(pos);

	SListNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

}

//pos位置后删除
void SLTEease_After(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}


void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;

	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

Test.c(测试代码)

void SListTest2()
{
	SListNode* plist = NULL;

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SListNode* ret = SLTFind(plist, 2);
	//SLTPrint(plist);

	SLTInsert(&plist, ret, 22);
	SLTPrint(plist);

	SLTErase(&plist, ret);
	SLTPrint(plist);
}
int main()
{
	SListTest3();
	return 0;
}

下期讲解带头双向循环链表文章来源地址https://www.toymoban.com/news/detail-463634.html

到了这里，关于数据结构《链表》无头单向非循环-动图详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包赞助服务器费用

相关文章

  • 数据结构入门（C语言版）线性表中链表介绍及无头单向非循环链表接口实现

    数据结构入门（C语言版）线性表中链表介绍及无头单向非循环链表接口实现

    概念 ： 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这

    2023年04月09日
    浏览(15)
  • 【数据结构】单向链表

    【数据结构】单向链表

    哈喽，大家好，今天我们学习的是数据结构里的链表，这里主要讲的是不带哨兵卫头节点的单向链表，下篇将会继续带大家学习双向链表。 目录 1.链表的概念 2.单向链表接口的实现 2.1动态申请一个节点 2.2单链表打印 2.3单链表尾插 2.4单链表头插 2.5单链表尾删 2.6单链表头删

    2024年02月11日
    浏览(15)
  • 数据结构——实现单向链表

    数据结构——实现单向链表

    单链表是一种常见的数据结构，用于存储一系列的数据元素，每个节点包含数据和指向下一个节点的指针。 单链表通常用于实现某些算法或数据结构，如链式前向星、哈希表、链式栈、队列等等。 单链表在程序设计中的作用不可忽略，是很多基础算法的核心数据结构之一。

    2024年02月07日
    浏览(17)
  • 【数据结构】动图详解双向链表

    【数据结构】动图详解双向链表

    目录 1.单向链表的劣势 2.带头双向循环链表         1.逻辑结构        2.结点的代码实现 3.双向链表接口的实现         1.接口1---初始化         2.接口2，3---头插，尾插         3. 接口4，5---头删，尾删         3. 接口6---查找          4. 接口7，8--插入，

    2024年01月23日
    浏览(16)
  • 数据结构：详解【链表】的实现（单向链表+双向链表）

    数据结构：详解【链表】的实现（单向链表+双向链表）

    1.顺序表的问题和思考 问题： 中间/头部的插入删除，时间复杂度为O(N)。 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗。 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据

    2024年03月26日
    浏览(11)
  • 数据结构与算法（三）：单向链表

    数据结构与算法（三）：单向链表

    链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑是通过链表种的指针链接次序实现的。链表由一系列节点组成，每个节点包括两部分：一个是存储数据元素的数据域，一个是存储下一个节点地址的指针域。单向链表从头节点（也可以没有头节点）开始

    2024年02月15日
    浏览(17)
  • 【数据结构篇】手写双向链表、单向链表（超详细）

    【数据结构篇】手写双向链表、单向链表（超详细）

    什么是链表 ？ 链表（Linked List）是用链式存储结构实现的线性表。链表示意图： 链表的组成 ： 数据域 + 引用域 （数据域和引用域合称结点或元素） 数据域存放数据元素自身的数据 引用域存放相邻结点的地址 链表的特点 ： 链表中元素的联系依靠引用域 具有线性结构的特

    2024年02月11日
    浏览(16)
  • 【数据结构】单向链表实现 超详细

    【数据结构】单向链表实现 超详细

    目录 一. 单链表的实现 1.准备工作及其注意事项 1.1 先创建三个文件 1.2 注意事项：帮助高效记忆和理解 2.链表的基本功能接口 2.0 创建一个 链表 2.1 链表的 打印  3.链表的创建新节点接口 4.链表的节点 插入 功能接口 4.1 尾插接口 4.2 头插接口     4.3 指定位置 pos 之前  插入

    2024年02月19日
    浏览(17)

  • 数据结构——单向链表（C语言版）

    在数据结构和算法中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在C语言中，我们可以使用指针来实现单向链表。下面将详细介绍如何用C语言实现单向链表。 目录 1. 定义节点结构体 2. 初始化链表 3. 插入节点 4. 删除节点

    2024年03月24日
    浏览(12)
  • 【数据结构和算法】使用数组的结构实现链表（单向或双向）

    【数据结构和算法】使用数组的结构实现链表（单向或双向）

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现，我们或许在其他老师的教学中，只学到了用结构体的形式来实现链表、队列、栈等数据结构，本文我想告诉你的是，我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包