位置:首页 > 数据结构之块状链表 >

数据结构之块状链表

作者:小牛君|发布时间:2017-03-24

小牛学堂的课程大纲最近进行了再一次升级,并且同时推出Java大数据平台开发班、Python爬虫与数据挖掘班、Spark项目班、Spark大神班、机器学习算法实战班、BI数据分析实战班, 目前这类人群凤毛麟角,导致这个行业的平均薪资极高,为此小牛学堂集合了行业的诸多大牛开设对应班级,为想学习的同学提供机会!
如果想了解详细情况,请联系 今日值班讲师 或者直接加入千人QQ群进行咨询:Spark大数据交流学习群613807316

以下是本文正文:



1、 概述

在进行算法设计时,我们常用的两种线性数据结构是数组和链表。它们各有优缺点。数组特点是元素在内存中紧挨着存储,因而优点是定位快(O(1)),缺点是插入删除慢(O(n));而链表则不同,它通过指针将不同位置的元素链接起来,因而优缺点与数组正好相反:定位慢(O(n)),插入删除快(O(1))。本文介绍一种新的数据结构:块状链表,它将数组和链表的优点结合来,各种操作的时间复杂度均为O(sqrt(n))。

2、 块状链表的基本操作

块状链表整合了数组和链表的优缺点,使得各种那个操作的时间复杂度均为O(sqrt(n))。 从整体上看,块状链表是一个链表, 而在链表的每个节点上,以数组的形式存储一组元素。具体如下:

基本操作:

(1)定位:先定位元素所在的链表节点,然后再定位该元素在数组中的位置。

(2)分裂:将某个链表节点分裂成两个节点。

(3)插入:首先定位要插入的位置,然后将所在节点分裂成两个节点,并将数据放到第一个节点的末尾。 如果要插入的是一大块数据,首先要将数据切成多个block(每个block对应一个块状链表的一个节点)并将这些block链起来,然后将它们插入那两个节点之间。

(4)删除:首先定位删除元素的位置,然后按照数组删除元素的方法删除该数据。如果删除一大块数据,首先要定位数据块首元素和末元素所在的位置,然后分别将它们所在的节点分裂成两个节点,最后删除首元素和末元素之间的节点即可。

3、 关键点和复杂度分析

该算法的核心是确定链表长度和每个节点的数组长度,以及怎么保证这个长度值?设块状链表中元素总个数为X,链表长度为n,每个节点中数据长度为m,则当m=n=sqrt(X)时,可保证m和n同时最小,此时各种操作的时间复杂度最低。在实际应用时,需维持块状链表的每个节点大小在[sqrt(n)/2, 2*sqrt(n)],否则,块状链表会退化。维护方法是,适当的时候,对节点进行合并与分裂(维护本身不会使复杂度增加)。

4、 应用

(1)     文本编辑器设计:http://download.noi.cn/T/noi/noi2003A.pdf

程序实现参考:

http://hi.baidu.com/wuyijia/blog/item/7085fa004423cd86e850cdeb.html

(2)     维护队列:http://download.noi.cn/T/noi/noi2005A.pdf

程序实现参考:

http://hi.baidu.com/zbwmqlw/blog/item/54cce1004e799c0c1d9583b7.html

5、 总结

由于块状链表的每个节点存储的是一个数组,如果数组是静态的(的大小固定),则会浪费存储空间;如是动态的,则需要频繁的申请或者释放空间,严重降低系能。因此,当数据量非常庞大时,设计合理的数组空间维护策略显得尤为重要。

6、 参考资料

(1)     论文《对块状链表的一点研究》

(2)     数组+链表=块状数组:http://starforever.blog.hexun.com/3184024_d.html

————————————————————————————————————-

更多关于数据结构和算法的介绍,请查看:数据结构与算法汇总

————————————————————————————————————-


了解更多详情请联系 今日值班讲师 或者直接加入千人QQ群进行咨询:Spark大数据交流学习群613807316

分享到: