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#程序设计有所帮助。