在数据结构的世界里，我们会认识各种各样的数据结构，每一种数据结构都能解决相应领域的问题，每一种数据结构都像是降龙十八掌中的某一掌，掌掌毙命。。。当然每个数据结构，有他的优点，必然就有它的缺点，那么如何创造一种数据结构来将某两种数据结构进行扬长避短，那就非常完美了。这样的数据结构也有很多，比如：双端队列，还有就是今天讲的块状链表，我们都知道数组具有O(1)的查询时间，O(N)的删除，O(N)的插入。。。链表具有O(N)的查询时间，O(1)的删除，O(1)的插入。。。
一：思路那么现在我们就有想法了，何不让“链表”和“数组”结合起来，来一起均摊CURD的时间，做法将数组进行分块，然后用指针相连接，比如我有N=个元素，那么最理想情况下，我就可以将数组分成x=10段，每段b=10个元素（排好序），那么我可以用√N的时间找到段，因为段中的元素是已经排好序的，所以可以用log√N的时间找到段中的元素，那么最理想的复杂度为√N+log√N≈√N。。。下面我们看看怎么具体使用：
二：结构定义这个比较简单，我们在每个链表节点中定义一个头指针，尾指针和一个数组节点。
publicclassBlockLinkNode{///summary///指向前一个节点的指针////summarypublicBlockLinkNodeprev;///summary///指向后一个节点的指针////summarypublicBlockLinkNodenext;///summary///链表中的数组////summarypublicListintlist;}三：插入
刚才也说了，每个链表节点的数据是一个数组块，那么问题来了，我们是根据什么将数组切开呢？总不能将所有的数据都放在一个链表的节点吧，那就退化成数组了，在理想的情况下，为了保持√N的数组个数，所以我们定了一个界限2√N，当链表中的节点数组的个数超过2√N的时候，当下次插入数据的时候，我们有两种做法：
①在元素的数组插入处，将当前数组切开，插入元素处之前为一个链表节点，插入元素后为一个链表节点。
②将元素插入数组后，将数组从中间位置切开。
///summary///添加元素只会进行块状链表的分裂////summary///paramname="node"/param///paramname="num"/param///returns/returnsprivateBlockLinkNodeAdd(BlockLinkNodenode,intnum){if(node==null){returnnode;}else{/**第一步：找到指定的节点*/if(node.list.Count==0){node.list.Add(num);total=total+1;returnnode;}//下一步：再比较是否应该分裂块varblockLen=(int)Math.Ceiling(Math.Sqrt(total))*2;//如果该节点的数组的最后位置值大于插入值，则此时我们找到了链表的插入节点，//或者该节点的next=null，说明是最后一个节点，此时也要判断是否要裂开if(node.list[node.list.Count-1]num
node.next==null){node.list.Add(num);//最后进行排序下，当然可以用插入排序解决，O(N)搞定node.list=node.list.OrderBy(i=i).ToList();//如果该数组里面的个数大于2*blockLen，说明已经过大了，此时需要对半分裂if(node.list.CountblockLen){//先将数据插入到数据库varmid=node.list.Count/2;//分裂处的前段部分varfirstList=newListint();//分裂后的后段部分varlastList=newListint();//可以在插入点处分裂，也可以对半分裂(这里对半分裂)firstList.AddRange(node.list.Take(mid));lastList.AddRange(node.list.Skip(mid).Take(node.list.Count-mid));//开始分裂节点，需要新开辟一个新节点varnNode=newBlockLinkNode();nNode.list=lastList;nNode.next=node.next;nNode.prev=node;//改变当前节点的next和listnode.list=firstList;node.next=nNode;}total=total+1;returnnode;}returnAdd(node.next,num);}}四：删除
跟插入道理一样，既然有裂开，就有合并，同样也定义了一个界限值√N/2，当链表数组节点的数组个数小于这个界限值的时候，需要将此节点和后面的链表节点进行合并。
///summary///从块状链表中移除元素,涉及到合并////summary///paramname="node"/param///paramname="num"/param///returns/returnsprivateBlockLinkNodeRemove(BlockLinkNodenode,intnum){if(node==null){returnnode;}else{//第一步：判断删除元素是否在该节点内if(node.list.Count0num=node.list[0]num=node.list[node.list.Count-1]){//定义改节点的目的在于防止remove方法假删除的情况发生varprevcount=node.list.Count;node.list.Remove(num);total=total-(prevcount-node.list.Count);//下一步：判断是否需要合并节点varblockLen=(int)Math.Ceiling(Math.Sqrt(total)/2);//如果当前节点的数组个数小于blocklen的话，那么此时改节点需要和后一个节点进行合并//如果该节点时尾节点，则放弃合并if(node.list.CountblockLen){if(node.next!=null){node.list.AddRange(node.next.list);//如果下一个节点的下一个节点不为null，则将下下个节点的prev赋值if(node.next.next!=null)node.next.next.prev=node;node.next=node.next.next;}else{//最后一个节点不需要合并，如果list=0，则直接剔除该节点if(node.list.Count==0){if(node.prev!=null)node.prev.next=null;node=null;}}}returnnode;}returnRemove(node.next,num);}}五：查询
在理想的情况下，我们都控制在√N，然后就可以用√N的时间找到区块，lg√N的时间找到区块中的指定值，当然也有人在查询的时候做链表的合并和分裂，这个就有点像伸展树一样，在查询的时候动态调整，拼的是均摊情况下的复杂度。这里顺便提醒你一下，其实你也可以这么做。。。
publicstringGet(intnum){varblockIndex=0;vararrIndex=0;vartemp=blockLinkNode;while(temp!=null){//判断是否在该区间内if(temp.list.Count0num=temp.list[0]num=temp.list[temp.list.Count-1]){arrIndex=temp.list.IndexOf(num);returnstring.Format("当前数据在第{0}块中的{1}个位置",blockIndex,arrIndex);}blockIndex=blockIndex+1;temp=temp.next;}returnstring.Empty;}
好了，CURD都分析好了，到这里大家应该对块状链表有个大概的认识了吧，这个代码是我下午抽闲写的，没有仔细测试，
完整代码参考我的博客园链接：