关于链表的查询花费过大的问题

[tioover]

写了个链表，代码在下面：
https://github.com/tioover/c-study/blob/master/linklist.h
https://github.com/tioover/c-study/blob/master/linklist.c

应该没有人有闲心看我的代码，基本上链表的结构是这样的

List 结构体类似一般实现中的头节点，里面有节点总数和首末节点的指针。

每一个Node里面有自己的前驱和后继的指针以及连接到List结构体的指针。

问题是这样的，如果我要查询第42个节点，那必须从第一个节点开始不断用指针读取到下一个节点，直到数到42，但如果需要的是42^42或者更大的元素呢？那还是必须老老实实的跳吧，当然因为有节点总数，如果是靠后的节点可以从后往前跳，但是如果在一个极大链表中中间位置的节点不是还是要花费很多时间吗？而普通的数组需要的仅仅是对第一个元素的地址做加法运算。

我现在的想法是这样的，对于大链表，建立一个索引数组，如果链表总数超过了索引数组，那么数组最后一项会指向下一个索引数组，但这种方法首先是不好适用各种情况，并且如果考虑到删除的话会很麻烦，还有就是不够简洁简单。

[cheshirecat]

试试跳表 [Skip List] 或者红黑树。

[Stockard]

我是这样想的，链表只是很基础的一种结构，方便增删。
在你的场合下，数组的话最大的问题还不在于删而在于增。
如果要写专门的程序，为了效率，还需要研究最适合的 data structure
当然我只是说说。

[66450146]

What about a std::deque?

[aisk]

用链表就是为了方便中间增加和删除节点，用数组索引的话查找的时候先走数组再去找链表，为嘛不直接用数组？增加和删除的时候除了要更新链表外还要更新数组，要这数组索引干嘛？
剩下的就是二楼的意见了，看你的应用场景再考虑对应的数据结构。大部分情况存几百几千的元素做这些优化意义不是很大。

[iwinux]

隐约觉得这就变成 hash table 了 = =

[reus]

用skip list

[Parallel]

块状链表可以解决的吧。

@cheshirecat 红黑树是平衡二叉树，好像不符合LZ的要求。

[cheshirecat]

@Parallel 红黑树和Skip List都是log(n)的。块状链表是sqrt(n)。

当然实际做的话，瓶颈不见得在这里。你要留意cpu cache prefetch，这个才是大头。

[Ricepig]

@cheshirecat 表大得无法cache而链表查找不频繁的化，cache可以忽略

[bigwang]

链表不停的移位，开销并不大，只是用加法器

链表的使用场景是为了优化插入，删除操作，你要评估这个场景

[tioover]

话说诸如Python 的list 是怎么实现的？

[VYSE]

@tioover 普通ARRAY吧，反正里面存的都是对象的引用

[iandyh]

你说的已经像 B+ Tree 了。

[Brutal]

@tioover 可以看「Python源码剖析」
隐约记得Python的list每个元素都是一个object，list里都是指向元素的指针。然后list进行了预申请，list池机制。

[xatest]

LZ实现的是最简单的双向链表，在结构上与STL中最相似的是std::deque，这种数据结构的优点是两端增删效率极高，就是stl里的push_back()操作，看了LZ代码，也就是NodeAppend()方法~
但是LZ又增加了按数字下标快速定位到元素的需求，还按原来的结构遍历一一对比是低效的，如果要加索引的话，不应该是LZ这样，有2种方式：
1. 加个hash table，也就是LZ说的数组，但不是首尾相接的多个数组，而是一个数组就把hash的范围考虑好，有冲突了再往后追加，把数据样本、hash算法和落点范围考虑好的话，时间复杂度做到O(1)也是没问题的~
2. 用红黑树做索引，就是std::map的原理，优点是查找效率可控，时间复杂度最差不过指数级，缺点是插入删除相应变慢，因为要调整树节点~

[66450146]

@xatest 简单的双向链表是 std::list, std::deque 要复杂不少

数据结构的设计是一门大学问，没有一种单一的数据结构可以解决所有的问题

[xatest]

@66450146 谢谢，赞同你的观点，没有万能、通用的数据结构，想清楚需求场景，就能找到一定条件下最优的数据结构~