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

我要思考

用数组也麻烦.比如删除
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4
array[4] = 5

我把array[2]的值删了. 下面的 array[3]、array[4] 也跟着换位置

cjaizss

像list RANGE 取范围的操作。 如果列表有100w个节点数据，取list范的围，这个高效一点应该怎么做。
这个li ...
我要思考 发表于 2011-02-16 13:31

    像我在开始时候写的那样做

我要思考

直接遍历做的？

liexusong

跳跃表也可以~

drangon

没有一个数据结构是万能的，优化这方面，自然要在另一方面付出代价，要综合评估

如果说只是定位10w这一个需求，那么另外加一个指针专门指向10w这个位置，链表增删时按需调整这个指针就是了，如果这个操作很少，说不定到时从头遍历的开销还少于平常调整这个指针的开销

如果要定位很多地方，而且还要很频繁定位，那么用数组说不定开销还小，付出一些数组增删时候的代码，只要增删不频繁就好，

所以关键还是看应用场合

lysde

同意楼上。优化是根据具体环境而定的。

同时像有这么多的数据，又要频繁的定位数据，用一个单链表是不够的。
用rbtree做索引也不错。

wmmy2008

用散列表应该要快的多。

fanronghua

哈希表啊，

summerfeel

用二叉树应该比哈希表要好，哈希表多一步根据哈希函数来计算元素落入哪个桶里，而且设计一个理想的哈希函数让这些元素均匀分布也不是那么容易。而二叉树则操作简单，一旦树建立完毕，操作的时间复杂度为lgn.

gothicane

用vector代替数组