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

本文实例讲述了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());//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节点，就形成了所谓的“循环双向链表”

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

注：.Net中微软已经给出了一个内置的双向链表System.Collections.Generic.LinkedList<T>，在了解双链表的原理后，建议大家直接系统内置的链表。

希望本文所述对大家C#程序设计有所帮助。