数据结构C#版线性表(Data Structure)之单链表(LinkList)
2010-10-17 14:15:36 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閹冣挃闁硅櫕鎹囬垾鏃堝礃椤忎礁浜鹃柨婵嗙凹缁ㄧ粯銇勯幒瀣仾闁靛洤瀚伴獮鍥敍濮f寧鎹囬弻鐔哥瑹閸喖顬堝銈庡亝缁挸鐣烽崡鐐嶆棃鍩€椤掑嫮宓佸┑鐘插绾句粙鏌涚仦鎹愬闁逞屽墰閹虫捇锝炲┑瀣╅柍杞拌兌閻ゅ懐绱撴担鍓插剱妞ゆ垶鐟╁畷銉р偓锝庡枟閻撴洘銇勯幇闈涗簼缂佽埖姘ㄧ槐鎾诲礃閳哄倻顦板┑顔硷工椤嘲鐣烽幒鎴旀瀻闁规惌鍘借ⅵ濠电姷鏁告慨顓㈠磻閹剧粯鈷戞い鎺嗗亾缂佸鏁婚獮鍡涙倷閸濆嫮顔愬┑鐑囩秵閸撴瑦淇婇懖鈺冪<闁归偊鍙庡▓婊堟煛鐏炵硶鍋撻幇浣告倯闁硅偐琛ラ埀顒冨皺閺佹牕鈹戦悙鏉戠仸闁圭ǹ鎽滅划鏃堟偨缁嬭锕傛煕閺囥劌鐏犻柛鎰ㄥ亾婵$偑鍊栭崝锕€顭块埀顒佺箾瀹€濠侀偗婵﹨娅g槐鎺懳熺拠鑼舵暱闂備胶枪濞寸兘寮拠宸殨濠电姵纰嶉弲鎻掝熆鐠虹尨宸ョ€规挸妫濆铏圭磼濡搫顫嶇紓浣风劍閹稿啿鐣烽幋锕€绠婚悹鍥у级瀹撳秴顪冮妶鍡樺鞍缂佸鍨剁粋宥夋倷椤掍礁寮垮┑鈽嗗灣閸樠勭妤e啯鍊垫慨妯煎亾鐎氾拷

核心提示:下面是单链表插入和删除的算法图解:可以看到:链表在元素插入/删除时,无需对后面的元素进行移动,数据结构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指向的链表,称为“单链表”。
编辑推荐:数据结构C#版线性表(Data Structure)之顺序表(顺序表(SeqList)的实现)
http://tech.cncms.com/web/aspnet/111434.html
[]
更多精彩
赞助商链接