当前位置: 首页 > article >正文

【数据结构】初识链表

顺序表的优缺点

缺点:

  • 中间/头部的插入删除,时间复杂度效率较低,为O(N)

  • 空间不够的时候需要扩容。

    • 如果是异地扩容,增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗。
  • 扩容可能会存在空间浪费。

    • 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

优点:

  • 尾差尾删足够快。
  • 下标的随机访问和修改足够快。

链表的初步认知

针对顺序表的缺点,链表就被设计出来了。
链表的特点即,按需申请释放。
当我们需要一块空间时,我们就申请一块空间。当我们需要添加数据时,就继续增加一个一个小块。
主要是就是一个一个小块之间的连接。为了方便连接和管理,每一个结点中都存有一个指针,用于指向下一个结点。正式一个一个“链接”起来,所以叫做链表。

下面图中主要标识了顺序表和链表的逻辑结构的不同。
对于顺序表,我们只需要知道指向这块内存空间的指针即可。
但是对于链表,我们仅仅知道指向第一块内存空间的指针是不够的,因为一块与一块之间没有连接。所以对于每一块,都必须存有指向下一块空间的指针。

定义单链表的结构

链表的逻辑图:

链表的物理图:

//Single List Table
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
	//SLTNode* next 是不可以的
}SLTNode;

下面,我们再来写一个打印单链表的的函数。

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

然后,接下来,我们再来在主函数中自己建一个单链表,其实也就是开辟几个结点的空间,然后使得结点之间可以“链接”起来即可。

int main()
{
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	n1->data = 1;
	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	n2->data = 2;
	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	n3->data = 3;
	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	PrintSList(n1);
}

由上图,我们可以知道代码的逻辑。

  • 动态分配内存,创建3个 SLTNode 类型的节点,并将其地址赋值给指针 n1、n2、n3。
  • 然后将3个结点的next字段都赋值。
  • 然后将链表链接起来。
    • n1->next = n2;将节点 n1 的 next 指针指向节点 n2,表示 n1 的下一个节点是 n2。
    • n2->next = n3;将节点 n2 的 next 指针指向节点 n3,表示 n2 的下一个节点是 n3。
    • n3->next = NULL;将节点 n3 的 next 指针设置为 NULL,表示链表到此结束。
  • 最后打印链表。


我们进行逐语句调试,在监视窗口中观察n1,n2,n3的变化。

我们可以看出来,n1、n2 和 n3 的物理地址并不连续。
根据结构体的定义,我们可以计算出结构体的大小。

如果内存连续,地址应该是:

而根据我们的监视信息,并非连续,这正是因为在代码中使用了 malloc 动态分配内存。
malloc 从堆中分配内存,而堆内存的分配通常是非连续的,具体取决于系统内存分配器的实现和当前堆内存的使用情况。因此,动态分配的内存块通常在物理地址上是分散的。



这一篇小博客,我们认识链表,下面我们将接着实现链表。
加油!


http://www.kler.cn/a/524810.html

相关文章:

  • Nginx 安装配置指南
  • 航空客户价值的数据挖掘与分析(numpy+pandas+matplotlib+scikit-learn)
  • 定制Centos镜像(一)
  • 速通Docker === Docker Compose
  • 卡特兰数学习
  • UiAutomator的详细介绍
  • MongoDB常见的运维工具总结介绍
  • 《刚刚问世》系列初窥篇-Java+Playwright自动化测试-19- 操作鼠标悬停(详细教程)
  • 代码随想录|动态规划 300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组
  • Go学习:格式化输入输出
  • solon-flow 你好世界!
  • C++传送锚点的内存寻址:内存管理
  • G. Rudolf and CodeVid-23
  • [250125] DeepSeek 发布开源大模型 R1,性能比肩 OpenAI o1 | 希捷推出高达 36TB 的硬盘
  • 【C++】STL容器使用与实现详解:vector
  • STM32 PWM驱动直流电机
  • 2024 CVPR Highlight Learning-Feedback
  • C# 环境:深入探讨与优化
  • Python中的函数(上)
  • 十大主流联邦学习框架:技术特性、架构分析与对比研究
  • 【电工基础】1.电能来源,触电伤害,触电预防,触电急救
  • 从 SAP 功能顾问到解决方案架构师:破茧成蝶之路
  • 联想拯救者R720笔记本外接显示屏方法,显示屏是2K屏27英寸
  • Kubernetes(一)
  • HBuilderX构建Vue项目
  • Redis缓存穿透,雪崩,击穿