1
cheshirecat 2012-09-09 18:34:07 +08:00
试试跳表 [Skip List] 或者红黑树。
|
2
Stockard 2012-09-09 19:06:55 +08:00
我是这样想的,链表只是很基础的一种结构,方便增删。
在你的场合下,数组的话最大的问题还不在于删而在于增。 如果要写专门的程序,为了效率,还需要研究最适合的 data structure 当然我只是说说。 |
3
66450146 2012-09-09 19:23:19 +08:00
What about a std::deque?
|
4
aisk 2012-09-09 19:34:07 +08:00
用链表就是为了方便中间增加和删除节点,用数组索引的话查找的时候先走数组再去找链表,为嘛不直接用数组?增加和删除的时候除了要更新链表外还要更新数组,要这数组索引干嘛?
剩下的就是二楼的意见了,看你的应用场景再考虑对应的数据结构。大部分情况存几百几千的元素做这些优化意义不是很大。 |
5
iwinux 2012-09-09 20:03:59 +08:00
隐约觉得这就变成 hash table 了 = =
|
6
reus 2012-09-09 20:11:00 +08:00
用skip list
|
7
Parallel 2012-09-09 21:41:14 +08:00
|
8
cheshirecat 2012-09-09 22:42:30 +08:00
|
9
Ricepig 2012-09-10 00:45:57 +08:00
@cheshirecat 表大得无法cache而链表查找不频繁的化,cache可以忽略
|
10
bigwang 2012-09-13 19:51:00 +08:00
链表不停的移位,开销并不大,只是用加法器
链表的使用场景是为了优化插入,删除操作,你要评估这个场景 |
11
tioover OP 话说诸如Python 的list 是怎么实现的?
|
13
iandyh 2012-09-13 23:18:16 +08:00
你说的已经像 B+ Tree 了。
|
14
Brutal 2012-09-13 23:19:39 +08:00
@tioover 可以看「Python源码剖析」
隐约记得Python的list每个元素都是一个object,list里都是指向元素的指针。然后list进行了预申请,list池机制。 |
15
xatest 2012-09-14 00:08:28 +08:00
LZ实现的是最简单的双向链表,在结构上与STL中最相似的是std::deque,这种数据结构的优点是两端增删效率极高,就是stl里的push_back()操作,看了LZ代码,也就是NodeAppend()方法~
但是LZ又增加了按数字下标快速定位到元素的需求,还按原来的结构遍历一一对比是低效的,如果要加索引的话,不应该是LZ这样,有2种方式: 1. 加个hash table,也就是LZ说的数组,但不是首尾相接的多个数组,而是一个数组就把hash的范围考虑好,有冲突了再往后追加,把数据样本、hash算法和落点范围考虑好的话,时间复杂度做到O(1)也是没问题的~ 2. 用红黑树做索引,就是std::map的原理,优点是查找效率可控,时间复杂度最差不过指数级,缺点是插入删除相应变慢,因为要调整树节点~ |
16
66450146 2012-09-14 00:18:06 +08:00
|