[已解决]关于链表遍历高效问题

理想小青年

RT
双向链表可以实现前驱或者后继遍历，但还是依赖循环去遍历
插入也是循环到某一个节点然后插入，有没有算法来实现链表的高效插入？？？
我想到了一种办法，双向可以从尾部遍历插入，可以像二分法做个判断，获取链表长度/2，然后比较（插入节点），选择从后插还是前插遍历找到节点快一些，自己却没有感觉到如何高效.......
还有一个有个疑惑，如二分法，把长度/2这样查询，增加效率，那么第一次如何定位到 （长度/2）呢，是不是也是依靠循环到（长度/2）的中间点？
我在网上拷贝了很多代码，看了看都是装逼的，代码逻辑结构也不清晰。目前巩固C与学习汇编中，白天实习，抽不出时间看数据结构视频，完全靠想与画自己学的链表，原理可能有些地方还不懂，那么以上问题是实操代码中想到得，好人一生平安

最佳答案

月排行榜 / 总排行榜

人造人

2018-6-5 14:42:51

理想小青年 发表于 2018-6-16 05:31
谢谢  就像您说的那样都是开始循环进行定位  在循环这方面链表是不是也能用二分法思想或者其余的一些思想 ...

就链表本身貌似做不到
链表只是一个过渡，后面的树，图 要更好
虽然说链表本身就使用广泛，后面的树和图我不知道是否使用广泛，但是树和图更强大
下面是树，应该可以按你想的那样快速查找
但前提是这棵树有序
快速的前提是有序（我是这样认为的，后面的我没学好，不知道对不对^_^）

如果用链表，那么好像只能一路向下查找，最坏的情况下需要100次（这里是100次吧，虽然说到最后一次没有必要判断了，因为肯定是了，但前提是要查找的数据在这个集合中，也就是说有必要再判断一下？^_^）

如果用树，能在不超过7次完成
但是这棵树是有要求的，自己看图

跳转到最佳答案楼层

人造人

理想小青年 发表于 2018-6-16 05:31
谢谢  就像您说的那样都是开始循环进行定位  在循环这方面链表是不是也能用二分法思想或者其余的一些思想 ...

就链表本身貌似做不到
链表只是一个过渡，后面的树，图 要更好
虽然说链表本身就使用广泛，后面的树和图我不知道是否使用广泛，但是树和图更强大
下面是树，应该可以按你想的那样快速查找
但前提是这棵树有序
快速的前提是有序（我是这样认为的，后面的我没学好，不知道对不对^_^）

如果用链表，那么好像只能一路向下查找，最坏的情况下需要100次（这里是100次吧，虽然说到最后一次没有必要判断了，因为肯定是了，但前提是要查找的数据在这个集合中，也就是说有必要再判断一下？^_^）

如果用树，能在不超过7次完成
但是这棵树是有要求的，自己看图

理想小青年

求一些高效的算法来实现链表的快速查找，快速插入，快速删除等操作。
快来点高材生给出思路的

溯影

实际上楼主你的思想是正确的，链表增删方便，因为不用像顺序表那样增加一个元素，有可能后面的元素都要动（插入末尾除外）,但是顺序表的查找比链表方便，所以平时在进行实际应用这些东西的时候，要综合考虑，没有必要说链表比顺序表好或者顺序表比链表好，

所以我认为没有什么高效的快速删除，快速插入，快速查找（对于链表而言），都是要开始循环来进行定位指定的元素，来进行增删查改。


这里我说一下实际应用的时候应该要什么时候用顺序表，什么时候用链表吧，小弟有错的请大佬指正便是：
顺序表适用于线性表变化长度不大的情况；链表适合用于线性表长度变化较大的情况，但是对于经常增删的线性表来说，链表还是更容易的

理想小青年

溯影 发表于 2018-6-15 20:01
实际上楼主你的思想是正确的，链表增删方便，因为不用像顺序表那样增加一个元素，有可能后面的元素都要动（ ...

谢谢  就像您说的那样都是开始循环进行定位  在循环这方面链表是不是也能用二分法思想或者其余的一些思想来减少时间快速定位呢？

人造人

链表是一个节点指向另一个节点，这棵树是一个节点指向两个节点
就在链表的基础上又加了一个指针，就可以完成这个“快速查找”，如果你还承认这是链表的话 ^_^

溯影

理想小青年 发表于 2018-6-16 05:31
谢谢  就像您说的那样都是开始循环进行定位  在循环这方面链表是不是也能用二分法思想或者其余的一些思想 ...

No Way，只有顺序表才可以利用索引值进行快速的定位，其他的无论是楼上人造人大佬说的树或者图，都要区分是顺序存储还是链式存储，链式存储的二叉树中，除了中序穿线二叉树可以进行像顺序存储的二叉树一样可以进行查找外，其他的基本上都不可以，但是那些数据结构是树，不是线性表了。顺序表和链表是线性表。

人造人

我好像已经忘了顺序表和链表的区别了 ^_^

应该是
顺序表的链式存储结构是一个节点指向另一个节点，这棵树（链式存储）是一个节点指向两个节点
就在 顺序表的链式存储结构 的基础上又加了一个指针，就可以完成这个“快速查找”
^_^