本文實例講述了C#數據結構之雙向鏈表(DbLinkList)。分享給大家供大家參考，具體如下：
這是繼上一篇《C#數據結構之單鏈表(LinkList)實例詳解》的繼續，對于雙向鏈接，節點上除了Next屬性外，還要有Prev屬性用來指向前一個節點，DbNode定義如下：
namespace 線性表{ public class DbNode<T> { private T data; private DbNode<T> prev; private DbNode<T> next; public DbNode(T data, DbNode<T> next,DbNode<T> prev) { this.data = data; this.next = next; this.prev = prev; } public DbNode(T data, DbNode<T> next) { this.data = data; this.next = next; this.prev = null; } public DbNode(DbNode<T> next) { this.data = default(T); this.next = next; this.prev = null; } public DbNode(T data) { this.data = data; this.next = null; this.prev = null; } public DbNode() { data = default(T); next = null; prev = null; } public T Data { set { this.data = value; } get { return this.data; } } public DbNode<T> Prev { get { return prev; } set { prev = value; } } public DbNode<T> Next { get { return next; } set { next = value; } } }}雙鏈表的插入操作要稍微復雜一點，示意圖如下：
同樣對于刪除操作，也要額外處理prev指向
完整實現DbLinkList<T>：
using System;using System.Text;namespace 線性表{ public class DbLinkList<T> : IListDS<T> { private DbNode<T> head; public DbNode<T> Head { get { return head; } set { head = value; } } public DbLinkList() { head = null; } /// <summary> /// 類索引器 /// </summary> /// <param name="index"></param> /// <returns></returns> public T this[int index] { get { return this.GetItemAt(index); } } /// <summary> /// 返回單鏈表的長度 /// </summary> /// <returns></returns> public int Count() { DbNode<T> p = head; int len = 0; while (p != null) { len++; p = p.Next; } return len; } /// <summary> /// 清空 /// </summary> public void Clear() { head = null; } /// <summary> /// 是否為空 /// </summary> /// <returns></returns> public bool IsEmpty() { return head == null; } /// <summary> /// 在最后附加元素 /// </summary> /// <param name="item"></param> public void Append(T item) { DbNode<T> d = new DbNode<T>(item); DbNode<T> n = new DbNode<T>(); if (head == null) { head = d; return; } n = head; while (n.Next != null) { n = n.Next; } n.Next = d; d.Prev = n; } //前插 public void InsertBefore(T item, int i) { if (IsEmpty() || i < 0) { Console.WriteLine("List is empty or Position is error!"); return; } //在最開頭插入 if (i == 0) { DbNode<T> q = new DbNode<T>(item); q.Next = head;//把"頭"改成第二個元素 head.Prev = q; head = q;//把自己設置為"頭" return; } DbNode<T> n = head; DbNode<T> d = new DbNode<T>(); int j = 0; //找到位置i的前一個元素d while (n.Next != null && j < i) { d = n; n = n.Next; j++; } if (n.Next == null) //說明是在最后節點插入(即追加) { DbNode<T> q = new DbNode<T>(item); n.Next = q; q.Prev = n; q.Next = null; } else { if (j == i) { DbNode<T> q = new DbNode<T>(item); d.Next = q; q.Prev = d; q.Next = n; n.Prev = q; } } } /// <summary> /// 在位置i后插入元素item /// </summary> /// <param name="item"></param> /// <param name="i"></param> public void InsertAfter(T item, int i) { if (IsEmpty() || i < 0) { Console.WriteLine("List is empty or Position is error!"); return; } if (i == 0) { DbNode<T> q = new DbNode<T>(item); q.Next = head.Next; head.Next.Prev = q; head.Next = q; q.Prev = head; return; } DbNode<T> p = head; int j = 0; while (p != null && j < i) { p = p.Next; j++; } if (j == i) { DbNode<T> q = new DbNode<T>(item); q.Next = p.Next; if (p.Next != null) { p.Next.Prev = q; } p.Next = q; q.Prev = p; } else { Console.WriteLine("Position is error!"); } } /// <summary> /// 刪除位置i的元素 /// </summary> /// <param name="i"></param> /// <returns></returns> public T RemoveAt(int i) { if (IsEmpty() || i < 0) { Console.WriteLine("Link is empty or Position is error!"); return default(T); } DbNode<T> q = new DbNode<T>(); if (i == 0) { q = head; head = head.Next; head.Prev = null; return q.Data; } DbNode<T> p = head; int j = 0; while (p.Next != null && j < i) { j++; q = p; p = p.Next; } if (j == i) { p.Next.Prev = q; q.Next = p.Next; return p.Data; } else { Console.WriteLine("The node is not exist!"); return default(T); } } /// <summary> /// 獲取指定位置的元素 /// </summary> /// <param name="i"></param> /// <returns></returns> public T GetItemAt(int i) { if (IsEmpty()) { Console.WriteLine("List is empty!"); return default(T); } DbNode<T> p = new DbNode<T>(); p = head; if (i == 0) { return p.Data; } int j = 0; while (p.Next != null && j < i) { j++; p = p.Next; } if (j == i) { return p.Data; } else { Console.WriteLine("The node is not exist!"); return default(T); } } //按元素值查找索引 public int IndexOf(T value) { if (IsEmpty()) { Console.WriteLine("List is Empty!"); return -1; } DbNode<T> p = new DbNode<T>(); p = head; int i = 0; while (!p.Data.Equals(value) && p.Next != null) { p = p.Next; i++; } return i; } /// <summary> /// 元素反轉 /// </summary> public void Reverse() { DbLinkList<T> result = new DbLinkList<T>(); DbNode<T> t = this.head; result.Head = new DbNode<T>(t.Data); t = t.Next; //(把當前鏈接的元素從head開始遍歷，逐個插入到另一個空鏈表中，這樣得到的新鏈表正好元素順序跟原鏈表是相反的) while (t!=null) { result.InsertBefore(t.Data, 0); t = t.Next; } this.head = result.head;//將原鏈表直接掛到"反轉后的鏈表"上 result = null;//顯式清空原鏈表的引用，以便讓GC能直接回收 } //得到某個指定的節點(為了下面測試從后向前遍歷) private DbNode<T> GetNodeAt(int i){ if (IsEmpty()) { Console.WriteLine("List is empty!"); return null; } DbNode<T> p = new DbNode<T>(); p = head; if (i == 0) { return p; } int j = 0; while (p.Next != null && j < i) { j++; p = p.Next; } if (j == i) { return p; } else { Console.WriteLine("The node is not exist!"); return null; } } /// <summary> /// 測試用prev屬性從后面開始遍歷 /// </summary> /// <returns></returns> public string TestPrevErgodic() { DbNode<T> tail = GetNodeAt(Count() - 1); StringBuilder sb = new StringBuilder(); sb.Append(tail.Data.ToString() + ","); while (tail.Prev != null) { sb.Append(tail.Prev.Data.ToString() + ","); tail = tail.Prev; } return sb.ToString().TrimEnd(','); } public override string ToString() { StringBuilder sb = new StringBuilder(); DbNode<T> n = this.head; sb.Append(n.Data.ToString() + ","); while (n.Next != null) { sb.Append(n.Next.Data.ToString() + ","); n = n.Next; } return sb.ToString().TrimEnd(','); } }}測試代碼片段：
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());//5Console.WriteLine(dblink.ToString());//v,w,x,y,zConsole.WriteLine(dblink[1]);//wConsole.WriteLine(dblink[0]);//vConsole.WriteLine(dblink[4]);//zConsole.WriteLine(dblink.IndexOf("z"));//4Console.WriteLine(dblink.RemoveAt(2));//xConsole.WriteLine(dblink.ToString());//v,w,y,zdblink.InsertBefore("x", 2);Console.WriteLine(dblink.ToString());//v,w,x,y,zConsole.WriteLine(dblink.GetItemAt(2));//xdblink.Reverse();Console.WriteLine(dblink.ToString());//z,y,x,w,vdblink.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());//8Console.ReadKey(); //8,v,6,w,x,y,2,1,z當然從上面的測試代碼中，似乎并不能看出雙鏈表的優點，雙鏈表的好處在于，如果需要在鏈表中，需要通過某個節點得到它的前驅節點時，雙鏈表直接用prev屬性就能找到；而單鏈表要做到這一點，必須再次從Head節點開始一個一個用Next向下找，這樣時間復雜度從O(n)降到O(1)，顯然更有效率。
注：如果把雙鏈表再做一下改造，讓頭尾接起來，即Head的Prev屬性指向最后一個節點(就叫做Tail吧)，同時把Tail節點的Next屬性指向Head節點，就形成了所謂的“循環雙向鏈表”
當然，這樣的結構可以在鏈表中再增加一個Tail節點屬性，在做元素插入或刪除時，可以循環到底以更新尾節點Tail(當然這樣會給插入/刪除元素帶來一些額外的開銷)，但是卻可以給GetItemAt(int i)方法帶來優化的空間，比如要查找的元素在前半段時，可以從Head開始用next向后找；反之，如果要找的元素在后半段，則可以從Tail節點用prev屬性向前找。
注：.Net中微軟已經給出了一個內置的雙向鏈表System.Collections.Generic.LinkedList<T>，在了解雙鏈表的原理后，建議大家直接系統內置的鏈表。
希望本文所述對大家C#程序設計有所幫助。
新聞熱點
疑難解答
