C#数据结构之双向链表(DbLinkList)实例详解

2019-12-30 11:23:55王旭

测试代码片段:


Console.WriteLine("-------------------------------------");
Console.WriteLine("双链表测试开始...");
DbLinkList<string> dblink = new DbLinkList<string>();
dblink.Head = new DbNode<string>("x");
dblink.InsertBefore("w", 0);
dblink.InsertBefore("v", 0);
dblink.Append("y");
dblink.InsertBefore("z", dblink.Count());
Console.WriteLine(dblink.Count());//5
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink[1]);//w
Console.WriteLine(dblink[0]);//v
Console.WriteLine(dblink[4]);//z
Console.WriteLine(dblink.IndexOf("z"));//4
Console.WriteLine(dblink.RemoveAt(2));//x
Console.WriteLine(dblink.ToString());//v,w,y,z
dblink.InsertBefore("x", 2);
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink.GetItemAt(2));//x
dblink.Reverse();
Console.WriteLine(dblink.ToString());//z,y,x,w,v
dblink.InsertAfter("1", 0);
dblink.InsertAfter("2", 1);
dblink.InsertAfter("6", 5);
dblink.InsertAfter("8", 7);
dblink.InsertAfter("A", 10);//Position is error!
Console.WriteLine(dblink.ToString()); //z,1,2,y,x,w,6,v,8 
string _tail = dblink.GetItemAt(dblink.Count()-1);
Console.WriteLine(_tail);
Console.WriteLine(dblink.TestPrevErgodic());//8
Console.ReadKey(); //8,v,6,w,x,y,2,1,z

当然从上面的测试代码中,似乎并不能看出双链表的优点,双链表的好处在于,如果需要在链表中,需要通过某个节点得到它的前驱节点时,双链表直接用prev属性就能找到;而单链表要做到这一点,必须再次从Head节点开始一个一个用Next向下找,这样时间复杂度从O(n)降到O(1),显然更有效率。

注:如果把双链表再做一下改造,让头尾接起来,即Head的Prev属性指向最后一个节点(就叫做Tail吧),同时把Tail节点的Next属性指向Head节点,就形成了所谓的“循环双向链表”

C#数据结构之双向链表(DbLinkList)实例详解

当然,这样的结构可以在链表中再增加一个Tail节点属性,在做元素插入或删除时,可以循环到底以更新尾节点Tail(当然这样会给插入/删除元素带来一些额外的开销),但是却可以给GetItemAt(int i)方法带来优化的空间,比如要查找的元素在前半段时,可以从Head开始用next向后找;反之,如果要找的元素在后半段,则可以从Tail节点用prev属性向前找。