用跳表实现的动态数组
用类似跳表的数据结构来实现动态数组。该数组的插入、删除、以及用索引访问元素的平均时间复杂性均为O(logn)。比起一般的线性动态数组，它的插入和删除要快很多（一般数组的插入和删除的平均时间复杂性均为O(n)），可用于插入和删除操作比较多的场合。
using System;
using System.Collections;
namespace ClassData.Index
{
public class SkipIndexList
{
static Random r=new Random();
public IEnumerator GetEnumerator()
{
return (new SkipIndexListEnumerator(this));
}
public class SkipIndexListEnumerator:IEnumerator
{
private SkipListNode ln;
private SkipListNode head;
public SkipIndexListEnumerator(SkipIndexList SkipIndexList)
{
head=SkipIndexList.head;
ln=head;
}
public bool MoveNext()
{
ln=ln.nodelink[0].nextlink;
return (!(ln.nodelink[0].nextlink==null));
}
public void Reset()
{
ln=head;
}
public object Current
{
get
{
return ln;
}
}
}
public class SkipListNode
{
public struct link
{
public SkipListNode nextlink;
public SkipListNode previewlink;
public int distance;
}
public object data;
public int level;
public link[] nodelink;
public SkipListNode(int Level)
{
nodelink=new link[Level+1];
level=Level;
}
public int Index
{
get
{
int i=0,l=0;
for(SkipListNode ln=this;ln.nodelink[l].distance>0;ln=ln.nodelink[l].previewlink)
if (ln.level>=l)
{
l=ln.level;
i+=ln.nodelink[l].distance;
}
return i;
}
}
}
protected int MaxLevel;
private SkipListNode head,tail;
private int Levels;
private int mCount;
public SkipIndexList()
{
newSIL(32);
}
public SkipIndexList(int maxCount)
{
newSIL((int)System.Math.Log(maxCount,2)+1);
}
private void newSIL(int maxlevel)
{
MaxLevel=maxlevel;
head=new SkipListNode(MaxLevel);
tail=new SkipListNode(MaxLevel);
for(int i=0;i<=MaxLevel;i++)
{
head.nodelink[i].nextlink=tail;
head.nodelink[i].distance=0;
head.level=MaxLevel;
tail.nodelink[i].previewlink=head;
tail.nodelink[i].distance=1;
tail.level=MaxLevel;
}
}
public SkipListNode ItemAt(int Index)
{
if (Index>mCount)
return null;
SkipListNode ln=head;
for(int i=0,l=Levels;l>=0;l--)
while (ln.nodelink[l].nextlink.nodelink[l].distance+i<=Index)
{
ln=ln.nodelink[l].nextlink;
i+=ln.nodelink[l].distance;
}
return ln;
}
public SkipListNode Insert(object data,int Index)
{
if (Index<=0) return null;
int level;
for(level=0;r.NextDouble()<=0.5 && level<MaxLevel;level++);
SkipListNode newln=new SkipListNode(level);
SkipListNode Insertln,pln;
newln.data=data;
if (Index>mCount)
Insertln=tail;
else
Insertln=(SkipListNode)ItemAt(Index);
int newl=newln.level;
if (Levels<newl)
Levels=newl;
int l=0,d=1;
for(;l<=newl;l++)
{
if (l>Insertln.level)
for(;Insertln.level < l;Insertln=Insertln.nodelink[Insertln.level].nextlink)
d+=Insertln.nodelink[Insertln.level].nextlink.nodelink[Insertln.level].distance;
newln.nodelink[l].nextlink=Insertln;
pln=Insertln.nodelink[l].previewlink;
newln.nodelink[l].previewlink=pln;
pln.nodelink[l].nextlink=newln;
Insertln.nodelink[l].previewlink=newln;
newln.nodelink[l].distance=Insertln.nodelink[l].distance-d+1;
Insertln.nodelink[l].distance=d;
}
for(l=newl+1;l<=MaxLevel;l++)
{
for(;Insertln.level < l;Insertln=Insertln.nodelink[Insertln.level].nextlink);
Insertln.nodelink[l].distance+=1;
}
mCount++;
return newln;
}
public SkipListNode Insert(object data)
{
return Insert(data,mCount+1);
}
public bool Delete(int Index)
{
if ((Index<=0) || (Index>mCount))
return false;
SkipListNode delln=(SkipListNode)ItemAt(Index);
SkipListNode nnl=head;
SkipListNode pnl;
for(int l=delln.level;l>=0;l--)
{
nnl=delln.nodelink[l].nextlink;
pnl=delln.nodelink[l].previewlink;
nnl.nodelink[l].distance+=delln.nodelink[l].distance;
nnl.nodelink[l].distance-=1;
nnl.nodelink[l].previewlink=pnl;
pnl.nodelink[l].nextlink=nnl;
}
for(int l=delln.level+1;l<=MaxLevel;l++)
{
for(;nnl.level < l;nnl=nnl.nodelink[nnl.level].nextlink);
nnl.nodelink[l].distance-=1;
}
mCount--;
return true;
}
public int Count
{
get
{
return mCount;
}
}
public void Clear()
{
newSIL(MaxLevel);
}
}
}