基本上，我們可以認為雙向連結清單是單連結清單的一個改進。這個改進一個有益的地方就是，雙連結清單不必像單連結清單一樣，為了查找一個元素，沿着連結清單的特定一個方向，從頭周遊到尾。通過雙連結清單，我們可以沿着正反兩個方向對連結清單内的元素進行查找。
雙連結清單的結點與單連結清單（循環連結清單）的稍稍有點不同，主要的不同就在與，雙連結清單的節點多出了一個連接配接前一個節點的字段（詳見灰色部分）。如下所示
class DulNode<T>
{
private T data;
/// <summary>
/// 資料域
/// </summary>
public T Data
{
get {return data;}
set { data = value;}
}
private DulNode<T> next;
/// 引用域
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;
/// 空構造函數
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;
/// 引用域
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;
/// 空構造函數
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())
if(IsEmpty()==true)
DulNode<T> Last = Head;
while(Count != i && Last.Next !=null)
return Last.Data;
publicint GetLength()
return0;
while(Last.Next !=null)
return++Count;
public States Insert(T item,int index)
bool isIndexTrue = index <0|| index >this.GetLength();
if(isIndexTrue)
return States.Fail;
//如果連結清單為空
Head.Data = item;
//如果是第一個結點
if(index ==0)
DulNode<T> NewNode =new DulNode<T>(item);
NewNode.Next = Head;
Head.Prior = NewNode;
Head = NewNode;
//如果是普通的結點
DulNode<T> Previous = Head;//目前節點的前一個
while(Count != index -1&& Previous.Next !=null)//因為要取到插入位置的前一個節點是以用Count != index-1的判斷
Previous = Previous.Next;
//如果是最後一個結點
if(this.GetLength()== index)
Previous.Next = NewNode;
NewNode.Prior = Previous;
if(Count == index -1)
DulNode<T> Current = Previous.Next;
NewNode.Next = Current;
Current.Prior = NewNode;
publicbool IsEmpty()
return Head ==null?true:false;
publicint Locate(T value,out States states)
int Index =0;
while(Last.Next !=null&&(!value.Equals(Last.Data)))
Index++;
return Index;
本文轉自陳哈哈部落格園部落格，原文連結http://www.cnblogs.com/kissazi2/p/3193965.html如需轉載請自行聯系原作者
kissazi2