函数：求有头结点单链表长度

点击联系发帖人 时间：2022-07-07 06:27

单链表的长度是什么

线性表是一种十分基础且重要的数据结构，它主要包括以下内容：

接下来，我将对这四种数据结构做一个详细的总结，其中对链表实现了十几种常见的操作。希望对你有所帮助。

数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
注意点：①.数组是一种线性表；②.连续的内存空间和相同类型的数据
由于第二个性质，数组支持 “随机访问”，根据下表随机访问的时间复杂度为O(1);但与此同时却使得在数组中删除，插入数据需要大量的数据搬移工作。

低效的“插入”和“删除”

假如数组的长度为n，我们需要将一个数据插入到数组的第k个位置，我们需要将第k~n位元素都顺序地往后挪动一位。
最好情况时间复杂度为O(1),此时对应着在数组末尾插入元素;
最坏情况时间复杂度为O(n),此时对应着在数组开头插入元素;
平均情况时间复杂度为O(n),因为我们在每个位置插入元素的概率相同，故(1+2+3+……+n)/n=O(n);
但是根据我们的需求，有一个特定的场景。如果数组的数据是有序的，那么我们在插入时就一定要那么做；但是如果数组中存储的数据并没有任何规律，数组只是被当成一个存储数据的集合，我们可以有一个取巧的方法：
直接将第k个元素搬移到数组元素的最后，把新的数据直接放入第k个位置即可（是不是很简单啊），这时插入元素的复杂度为O(1)。

和插入操作一样，为了保证内存的连续性，删除操作也需要搬移数据。
最好情况时间复杂度为O(1),此时对应着删除数组末尾的元素;
最坏情况时间复杂度为O(n),此时对应着删除数组开头的元素;
平均情况时间复杂度为O(n),因为我们删除每个位置的元素的概率相同，故(1+2+3+……+n)/n=O(n);
当然，在某些特殊情况下，我们并不一定非要进行复杂的删除操作。我们只是将需要删除的数据记录，并且假装它以经被删除了。直到数组没有更多空间存储数据时，我们再触发一次真正的删除操作即可。

这其实就和生活中的垃圾桶类似，垃圾并没有消失，只是被“标记”成了垃圾，而直到垃圾桶塞满时，才会清理垃圾桶。

在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。如果疏忽会造成严重的后果。当然，Java会自动检测。

单链表根据索引插入结点
单链表删除指定索引的结点
单链表实现元素查找，返回是否存在布尔值
单链表删除指定索引的后续节点

单链表根据索引插入结点

//完成节点的插入操作 //返回真正的链表头节点地址

单链表删除指定索引的结点

//完成节点的删除操作

单链表实现元素查找，返回是否存在布尔值

单链表删除指定索引的后续节点

//利用两个指针，fast和slow，它们之间差k个位置，判断如果fast.Nest=null,也就代表着slow这个位置就是倒数第k个结点

1.基于数组实现的顺序栈

//基于数组实现的顺序栈 //初始化数组，申请一个大小为n的数组空间 //数组空间不足，直接返回false，入栈失败 //栈为空，直接返回-1; //返回下标为count-1的数组元素，并且栈中元素个数count减一

//定义了结点的嵌套类

基于数组实现的普通队列
基于数组实现的循环队列

1.基于数组实现的普通队列

//数组：items，数组大小：n //head表示队头下标，tail表示队尾下标 //入队(一),基础版 //如果tail==n，表示队列末尾已经没有空间了 //入队（二），改进版 //如果tail==n，表示队列末尾已经没有空间了

2.基于链表实现的队列

//基于链表实现的队列 //定义了结点的嵌套类 //向表尾添加元素,即入队

3.基于数组实现的循环队列

//head表示队头下标，tail表示队尾下标

文章代码太多，我本来是希望分成几篇文章写的，但是由于一些原因，最终放在了一起，略显臃肿。代码都是经过测试用例测试过的，应该不会有错误。

如果体验不太好，可以移步我的,里面观感较好。

题外话：对于算法初学者，推荐一本十分 nice 的书籍 《算法第四版》，里面各种配图十分详细。如果你需要电子版文件，后台回复算法4即可获得下载链接。后台回复 算法01 送你一份算法与数据结构思维导图。最后，希望我们一起进步，一起成长！

}

单链表显示:e→a→a→d→b→c
删除第1个结点:单链表显示:a→a→d→b→c
删除第5个结点:单链表显示:a→a→d→b
删除开头3个结点:单链表显示:b

· 超过15用户采纳过TA的回答

下载百度知道APP，抢鲜体验

使用百度知道APP，立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。

}

在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的
数据的逻辑结构分为线性结构和非线性结构
- 集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。类似于数学上的集合
- 线性结构结构中的数据元素之间只存在一对一的关系。比如排队
- 树形结构结构中的数据元素之间存在一对多的关系。比如家族族谱
- 图状结构或网状结构结构中的数据元素之间存在多对多的关系。比如地图

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。

}

我就爱股票网