开发学院 WEB开发 ASP.NET 数据结构C#版线性表(Data Structure)之单链表(Lin... 阅读

数据结构C#版线性表(Data Structure)之单链表(LinkList)

　2010-10-17 14:15:36　来源：WEB开发网　　　

核心提示：下面是单链表插入和删除的算法图解：可以看到：链表在元素插入/删除时，无需对后面的元素进行移动，数据结构C#版线性表(Data Structure)之单链表(LinkList)(2)，只需要自身以及相邻节点的next指向即可，所以插入/删除元素的开销要比顺序表小得多，它有助于某些情况下减少遍历循环的次数，本文中的这种仅有

下面是单链表插入和删除的算法图解：

可以看到：链表在元素插入/删除时，无需对后面的元素进行移动，只需要自身以及相邻节点的next指向即可。所以插入/删除元素的开销要比顺序表小得多，但是也应该注意到，其它操作比如：查找元素，反转倒置链表等，有可能需要遍历整个链表中的所有元素。

测试代码片断：

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

Console.WriteLine(link.ToString()); //z,1,2,y,x,w,6,v,8

至于具体在实际应用中应该选用顺序表 or 链表，主要是看：对于元素插入/删除的频繁程度以及对于内存分配的苛刻程序。如果不要求一开始就分配一组连续的内存区域，可是根据元素的增加而自动加大内存的使用量，同时插入/删除的次数很多，那么建议使用链表，反之用顺序表。

最后指出：可以给节点再添加一个prev元素，用于指出前一个节点是谁，即同时有next和prev二个指向，这种改进后的链表称为“双向链表”，它有助于某些情况下减少遍历循环的次数，本文中的这种仅有一个next指向的链表，称为“单链表”。

http://tech.cncms.com/web/aspnet/111434.html

上一页 1 2