posts - 183,  comments - 10,  trackbacks - 0

单链表的访问改进

我们知道单链表的插入和删除的时间复杂度是 O(1)
但是其访问的时间复杂度是 O(N),不能实现随机访问。

而顺序表是随机访问的,插入和删除的时间复杂度是 O(N)

针对单链表的访问弊端,如何改进单链表数据结构,使得访问的效率有所提升?

每种数据结构都有各自的优劣以及适用情况。

这里有几种方案,其实不能算在方案吧,而是采用其他数据结构替换的策略。

第一种方案
采用平衡二叉树,插入、删除、访问的复杂度都是 O(logN)
或者红黑树,插入、删除、访问的时间复杂度都是 O(logN)
STL 中的 set、map 可以完成该功能。

第二种方案
采用分段的策略
针对每个节点的值,根据值进行分段,段数视具体情况而定。
插入和删除的时间复杂度保持不变,还是 O(1)
访问的时间复杂度变为 O(N / 段的数目)
这种方式访问的时间复杂度得到一定的改进,但是是常数级的。
这种策略实质上是哈希。
哈希函数为除法函数。
例如有 0 1 2 3 4 5 6 7 8 9 十个数,可以分为两段,0 - 4 为第一段,5 - 9 为第二段。
访问一个数时,首先计算其所在的段,m / 5,得到所在段的首地址,然后去遍历访问。

第三种方案
采用线索二叉树
线索二叉树将二叉树线索化,二叉树可以想链表那样操作。插入和删除的时间复杂度都是 O(1)。
访问按照二叉树的方式,这时二叉树是平衡二叉树,访问的时间复杂度是 O(logN)。

几种方案的比较
                插入和删除   访问
单链表              O(1)    O(N)
平衡二叉树    O(logN)    O(logN)
分段                 O(1)    O(N / 段的数目)
线索二叉树         O(1)    O(logN)

总结
这几种方案,与其说是改进,不如说是更换另一种数据结构。

另外哈希方式,最好在存在大量数据的情况下使用,否则会浪费空间,因为哈希表很大。

针对单链表访问效率的改进,另一个角度是采用辅助性数据结构,记录一些信息,以方便快速地访问。

posted on 2011-09-13 20:54 unixfy 阅读(738) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理