假如有一个链表，链节为一个结构，已按某个成员的升序排好，对它有四种操作：
1、查询某个链节
2、增加一个链节，保持升序
3、删除一个链节，保持升序
4、按顺序输出全部链节的内容到屏幕

视野很重要，所以想知道有多少种实现办法，然后都有什么优缺点。

以下是我想到的：

1、全部遍历。
这个是最常规最低级的了
优点：易于实现，不易出错
缺点：链节多或者操作多的时候效率很低

2、树
构建一棵二叉树来维护链表，为避免退化还可以做成红黑树等等
优点：除输出外效率都不错
缺点：输出慢；遇到大量的极端数据，要么退化要么很慢（比如红黑树要转很多次）。

3、散列
将链节散列到多个地址，用拉链法保存散列值相同的链节
优点：增加和删除都快，一般情况下。
缺点：散列函数不好设计，设计得不好的话由占空间效率又低，跟没散列一样；输出的时候要重新组合在一起，时间复杂度至少是n，糟糕的散列函数可能会达到n^2。

4、懒惰标记
新建一个临时链表保存要添加的链节，直到删除和输出时才合并在一起（不知道删除也放在一个临时列表里效率会怎么样？）
优点：易于实现，连续的添加操作可以在O（n）完成
缺点：添加一次输出一次的话就变成跟第一种算法一样了。

5、类似标记排序法
用于排序的成员可能取值在一个不大的区间M内时，开辟一个M的数组，1表示有，0表示没有。
优点：输出为O(M)，其它都是O(1)
缺点：只能在部分情况下使用


想到的就这么多了……效率都不高的样子……

这个值得讨论，偶最近也在思考类似的问题。。
链表的还有一个问题就是malloc和free在分配节点内存时效率问题。偶的思考是采用内存池办法处理。
查询如果用树或是散列会大大加快查询的速度。
输出全部内容，用遍历。

其实这是大多数程序速度和空间的矛盾，想要快速，基本上拿空间来换，想要空间，拿速度来换。

[ 本帖最后由 hellovfp 于 2012-4-16 14:06 编辑 ]

我第一想到的是 链式堆 (二项堆，或者fib-heap)。

看看DW大侠的提示，或许还有其它更好的数据结构。
几种堆(BinaryHeap, FibHeap, PairHeap)
any more??

[ 本帖最后由 hellovfp 于 2012-4-16 14:21 编辑 ]

链表本身就是为了方便插入和删除而设计的数据结构，现在的问题根本不在插入和删除上，与内存分配无关。他的麻烦主要是对链表的查询，因为要维护已排序状态，就必须找出新插入项应在什么位置，插入不是问题，找到这个位置才是问题，链表的查询比线性表慢。解决的办法，不妨另外做一份对应的线性表，按照排序项排好的，每个元素附带对应的链表项的实际指针。说白了就是用List的查询高效补充Link的查询低效，用Link的增删高效补充List的增删低效，两种结构综合了用。在面向对象的类设计中，封装这么一个综合功能，不是很难的事。

收到的鲜花

• 绿茶盖儿 于 2012-04-17 10:25 送鲜花  10朵   附言：我很赞同

按现在的硬件水平，时间应该比空间重要了，那么有什么快的算法吗

嗯，也是……但是如果从零开始创建一个长链表呢？多久更新一次线性表合适？

Tong版说的，也是偶思考中的一个解决办法，用附加数组来解决链表的随机访问问题。

据说散列目前也有好几种比较不错的算法，ISBN就一种，md5也算一种，值得研究究。

我的思考是添加一个值，用来标识是否需要创建附加数组。1表示需要更新，0表示不需要。
在添加的时候可以重设这个值，直到用户添加完所有数据，第一次调用查询的时候，进行更新。