当前位置: 首页 > 编程笔记 >

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

薛弘济
2023-03-14
本文向大家介绍C#数据结构之双向链表(DbLinkList)实例详解,包括了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#程序设计有所帮助。

 类似资料:
  • 本文向大家介绍C#数据结构之单链表(LinkList)实例详解,包括了C#数据结构之单链表(LinkList)实例详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了C#数据结构之单链表(LinkList)实现方法。分享给大家供大家参考,具体如下: 这里我们来看下“单链表(LinkList)”。在上一篇《C#数据结构之顺序表(SeqList)实例详解》的最后,我们指出了:顺序表要求开辟一组

  • 本文向大家介绍javascript数据结构之双链表插入排序实例详解,包括了javascript数据结构之双链表插入排序实例详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了javascript数据结构之双链表插入排序实现方法。分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。 换成链表时,显然无需

  • 本文向大家介绍C语言之双向链表详解及实例代码,包括了C语言之双向链表详解及实例代码的使用技巧和注意事项,需要的朋友参考一下 1,双向链表简介。 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 2,例子要求: 完成双向链表的插入、删除以及查找,将

  • 本文向大家介绍C#数据结构之顺序表(SeqList)实例详解,包括了C#数据结构之顺序表(SeqList)实例详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了C#数据结构之顺序表(SeqList)实现方法。分享给大家供大家参考,具体如下: 线性结构(Linear Stucture)是数据结构(Data Structure)中最基本的结构,其特征用图形表示如下: 即:每个元素前面有且只有

  • 本文向大家介绍C语言实现数据结构和双向链表操作,包括了C语言实现数据结构和双向链表操作的使用技巧和注意事项,需要的朋友参考一下 数据结构  双向链表的实现 双向链表中的每一个结点都含有两个指针域,一个指针域存放其后继结点的存储地址,另一个指针域则存放其前驱结点的存储地址。 双向链表结点的类型描述:     其中,prior域存放的是其前驱结点的存储地址,next域存放的是其后继结点的存储地址。 双

  • 1.一般链表 图解链表: 链表 实现: <!doctype html> <html> <head> <meta charset="utf-8" > </head> <body> <script> function Node(ele) { this.ele=ele; this.next=null; } func