本文实例讲述了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#程序设计有所帮助。
dy("nrwz");
查看更多关于C#数据结构之双向链表(DbLinkList)实例详解的详细内容...