快速维护链表的方法
假如有一个链表,链节为一个结构,已按某个成员的升序排好,对它有四种操作:1、查询某个链节
2、增加一个链节,保持升序
3、删除一个链节,保持升序
4、按顺序输出全部链节的内容到屏幕
视野很重要,所以想知道有多少种实现办法,然后都有什么优缺点。
以下是我想到的:
1、全部遍历。
这个是最常规最低级的了
优点:易于实现,不易出错
缺点:链节多或者操作多的时候效率很低
2、树
构建一棵二叉树来维护链表,为避免退化还可以做成红黑树等等
优点:除输出外效率都不错
缺点:输出慢;遇到大量的极端数据,要么退化要么很慢(比如红黑树要转很多次)。
3、散列
将链节散列到多个地址,用拉链法保存散列值相同的链节
优点:增加和删除都快,一般情况下。
缺点:散列函数不好设计,设计得不好的话由占空间效率又低,跟没散列一样;输出的时候要重新组合在一起,时间复杂度至少是n,糟糕的散列函数可能会达到n^2。
4、懒惰标记
新建一个临时链表保存要添加的链节,直到删除和输出时才合并在一起(不知道删除也放在一个临时列表里效率会怎么样?)
优点:易于实现,连续的添加操作可以在O(n)完成
缺点:添加一次输出一次的话就变成跟第一种算法一样了。
5、类似标记排序法
用于排序的成员可能取值在一个不大的区间M内时,开辟一个M的数组,1表示有,0表示没有。
优点:输出为O(M),其它都是O(1)
缺点:只能在部分情况下使用
想到的就这么多了……效率都不高的样子……