基本上，我们可以认为双向链表是单链表的一个改进。这个改进一个有益的地方就是，双链表不必像单链表一样，为了查找一个元素，沿着链表的特定一个方向，从头遍历到尾。通过双链表，我们可以沿着正反两个方向对链表内的元素进行查找。
双链表的结点与单链表（循环链表）的稍稍有点不同，主要的不同就在与，双链表的节点多出了一个连接前一个节点的字段（详见灰色部分）。如下所示
class DulNode<T>
{
private T data;
/// <summary>
/// 数据域
/// </summary>
public T Data
{
get {return data;}
set { data = value;}
}
private DulNode<T> next;
/// <summary>
/// 引用域
/// </summary>
public DulNode<T> Next
{
get {return next;}
set { next = value;}
}
private DulNode<T> prior;
public DulNode<T> Prior
{
get {return prior;}
set { prior = value;}
}
//头结点构造函数
public DulNode(DulNode<T> next)
:this(default(T),null, next)
{
}
//头结点构造函数
public DulNode(T data)
:this(data,null,null)
{
}
//普通结点构造函数
public DulNode(T data,DulNode<T> prior, DulNode<T> next)
{
this.Data = data;
this.Next = next;
this.Prior = prior;
}
/// <summary>
/// 空构造函数
/// </summary>
public DulNode()
:this(default(T),null,null)
{
}
//尾结点构造函数
public DulNode(T data,DulNode<T> prior)
:this(data, prior,null)
{
}
}
我们初始化一个双向链表，以便让大家更加直观的了解到双向链表中头结点和尾节点的不同。这个链表有四个节点，我们分别用0,1,2,3填充这个链表。
头节点如下所示：（其中next代表连接后一个节点的后导节点，prior代表连接前一个节点的前导节点）
尾节点如下所示：
普通的节点如下所示：
双向链表具体的实现如下所示
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure
{
class DulList<T>: IListDS<T>
{
class DulNode<T>
{
private T data;
/// <summary>
/// 数据域
/// </summary>
public T Data
{
get {return data;}
set { data = value;}
}
private DulNode<T> next;
/// <summary>
/// 引用域
/// </summary>
public DulNode<T> Next
{
get {return next;}
set { next = value;}
}
private DulNode<T> prior;
public DulNode<T> Prior
{
get {return prior;}
set { prior = value;}
}
//头结点构造函数
public DulNode(DulNode<T> next)
:this(default(T),null, next)
{
}
//头结点构造函数
public DulNode(T data)
:this(data,null,null)
{
}
//普通结点构造函数
public DulNode(T data, DulNode<T> prior, DulNode<T> next)
{
this.Data = data;
this.Next = next;
this.Prior = prior;
}
/// <summary>
/// 空构造函数
/// </summary>
public DulNode()
:this(default(T),null,null)
{
}
//尾结点构造函数
public DulNode(T data, DulNode<T> prior)
:this(data, prior,null)
{
}
}
private DulNode<T> Head;
public DulList(T[] t)
{
this.Head =new DulNode<T>(t[0]);
DulNode<T> Current;
Current = Head;
for(int i =1; i < t.Length; i++)
{
DulNode<T> newNode =new DulNode<T>(t[i]);
//设置前一个连接点
newNode.Prior = Current;
//当前节点的next设置为新的节点
Current.Next = newNode;
//将当前节点的引用域指向新的节点
Current = newNode;
}
}
public DulList()
{
}
publicint Lenth
{
get {returnthis.GetLength();}
}
public States Append(T item)
{
//(1)头结点没有
if(Head ==null)
{
Head =new DulNode<T>(item);
return States.Success;
}
//(2)正常的插入情况
DulNode<T> Last;
Last = Head;
//遍历到最后一个结点，在最后一个结点附加上
while(null!= Last.Next)
{
Last = Last.Next;
}
DulNode<T> newNode =new DulNode<T>(item);
Last.Next = newNode;
newNode.Prior = Last;
return States.Success;
}
publicvoid Clear()
{
Head =null;
}
public T Delete(int index,out States states)
{
bool isIndexTrue = index <0|| index >=this.GetLength();
if(IsEmpty()==true|| isIndexTrue)
{
states = States.Fail;
returndefault(T);
}
//找到指定的结点
DulNode<T> Current = Head;
DulNode<T> Previous = Head;
int Count =0;
while(Count != index && Current.Next !=null)
{
Previous = Current;
Current = Current.Next;
Count++;
}
T ValueToDel = Current.Data;
//是否是头结点
if(Count ==0)
{
Head = Current.Next;
Current.Next.Prior =null;
}
//是否是普通的结点
if(Count !=0&& Current.Next !=null)
{
Previous.Next = Current.Next;
Current.Next.Prior = Previous;
}
//是否是最后一个结点
if(Count !=0&& Current.Next ==null)
{
Previous.Next =null;
}
//删除结点
states = States.Success;
return ValueToDel;
}
public T GetElem(int i)
{
if(i <0|| i >=this.GetLength())
{
returndefault(T);
}
if(IsEmpty()==true)
{
returndefault(T);
}
DulNode<T> Last = Head;
int Count =0;
while(Count != i && Last.Next !=null)
{
Last = Last.Next;
Count++;
}
return Last.Data;
}
publicint GetLength()
{
if(Head ==null)
{
return0;
}
DulNode<T> Last;
Last = Head;
int Count =0;
while(Last.Next !=null)
{
Last = Last.Next;
Count++;
}
return++Count;
}
public States Insert(T item,int index)
{
bool isIndexTrue = index <0|| index >this.GetLength();
if(isIndexTrue)
{
return States.Fail;
}
//如果链表为空
if(IsEmpty()==true)
{
Head.Data = item;
}
//如果是第一个结点
if(index ==0)
{
DulNode<T> NewNode =new DulNode<T>(item);
NewNode.Next = Head;
Head.Prior = NewNode;
Head = NewNode;
return States.Success;
}
//如果是普通的结点
DulNode<T> Previous = Head;//当前节点的前一个
int Count =0;
while(Count != index -1&& Previous.Next !=null)//因为要取到插入位置的前一个节点所以用Count != index-1的判断
{
Previous = Previous.Next;
Count++;
}
//如果是最后一个结点
if(this.GetLength()== index)
{
DulNode<T> NewNode =new DulNode<T>(item);
Previous.Next = NewNode;
NewNode.Prior = Previous;
return States.Success;
}
if(Count == index -1)
{
DulNode<T> NewNode =new DulNode<T>(item);
DulNode<T> Current = Previous.Next;
NewNode.Next = Current;
Current.Prior = NewNode;
NewNode.Prior = Previous;
Previous.Next = NewNode;
}
return States.Success;
}
publicbool IsEmpty()
{
return Head ==null?true:false;
}
publicint Locate(T value,out States states)
{
if(IsEmpty()==true)
{
states = States.Fail;
return0;
}
DulNode<T> Last = Head;
int Index =0;
while(Last.Next !=null&&(!value.Equals(Last.Data)))
{
Last = Last.Next;
Index++;
}
states = States.Success;
return Index;
}
}
}
