请问有没有快速定位list 节点的算法

我要思考

比如我有一个 100w个节点的list,
我现在想要取第10w个的节点数据。
一般情况下是遍历这个list,然后遍历到 第10w个的时候，然后取这个节点数据。

有没有快速定位到第10w个，不用遍历这么麻烦的

cjaizss

比如我有一个 100w个节点的list,
我现在想要取第10w个的节点数据。
一般情况下是遍历这个list,然后遍历到 ...
我要思考 发表于 2011-02-16 12:09

    重新设计数据结构与算法,都纯链表了.
   不过你可以考虑再加一个链表,每连续n个表元存进去一个地址.比如n取1000,你的需求就快许多了
...   o -------> o------->o---...
      |             |             |
o->o->........o->..........o->......

cjaizss

重新设计数据结构与算法,都纯链表了.
   不过你可以考虑再加一个链表,每连续n个表元存进去一个地 ...
cjaizss 发表于 2011-02-16 12:16

    不过想想,如果是单向链表,你删除表元的时候,这个辅助数据结构的修改会非常夸张,那么你只好改用双向链表

cjaizss

重新设计数据结构与算法,都纯链表了.
   不过你可以考虑再加一个链表,每连续n个表元存进去一个地 ...
cjaizss 发表于 2011-02-16 12:16

    当然,你也可以建立多层的
   ....
   ...o------->o-------->o-->...
        |             |           |
  ...   o ---...-> o-...--->o---...
      |             |             |
o->o->........o->..........o->...... 最终存储

我要思考

我打算 双向链表 + rbtree 索引key 来快速定位

cjaizss

我打算 双向链表 + rbtree 索引key 来快速定位
我要思考 发表于 2011-02-16 12:35

    总之肯定要改算法和数据结构的

mcemil

各种树表示毫无压力，比如最简单的二叉查找树。
有关键字可以上，没有关键字，创造关键字也可以上

linyunxian

内核对于这样的情况，一般会考虑hlist，即hash list。

我要思考

像list RANGE 取范围的操作。 如果列表有100w个节点数据，取list范的围，这个高效一点应该怎么做。
这个list 不能遍历吧

hellioncu

既然有直接定位的需求，考虑用数组吧