在结点中设两个引用域，一个保存直接前驱结点的地址，叫prev，一个直接后继结点的地址，叫next，这样的链表就是双向链表(Doubly Linked List)。
双向链表的结点结构示意图如上，双向链表结点的定义与单链表的结点的定义很相似，因此，双向链表节点类的实现可以参考单链表的节点类。
C#实现：
1接口
引用线性表的接口IListDS<T>
2实现
（1）双向链表节点类，参考单链表的节点类
public class DBNode<T>
{
private T data; //数据域
private DBNode<T> next; //后继
private DBNode<T> prev; //前驱
public T Data
{
get { return data; }
set { data = value; }
}
public DBNode<T> Next
{
get { return next; }
set { next = value; }
}
public DBNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
public DBNode()
{
data = default(T);
prev = null;
next = null;
}
public DBNode(T val)
{
data = val;
next = null;
prev = null;
}
}
(2) 双向链表操作类实现
注意：由于双向链表的结点有两个引用，所以，在双向链表中插入和删除结点比单链表要复杂。双向链表中结点的插入分为在结点之前插入和在结点之后插入，插入操作要对四个引用进行操作
同样，删除操作也需要多多注意，其他的操作和单链表类似,不再赘述.
public class DBLinkList<T> : IListDS<T>
{
private DBNode<T> header;
public DBNode<T> Header
{
get { return header; }
set { header = value; }
}
public DBLinkList()
{
header = new DBNode<T>();
header.Next = null;
header.Prev = null;
}
/// <summary>
/// 获取长度
/// </summary>
/// <returns></returns>
public int GetLength()
{
DBNode<T> p = header;
int len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}
/// <summary>
/// 清空操作
/// </summary>
public void Clear()
{
header = null;
}
/// <summary>
/// 判断线性表是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
if (header.Data == null)
{
return true;
}
else
{
return false;
}
}
/// <summary>
/// 查找节点
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
private DBNode<T> FindNode(int i)
{
if (IsEmpty())
{
Console.Write("list is empty");
return null;
}
if (i < 1)
{
Console.Write("Index is error");
return null;
}
DBNode<T> current = new DBNode<T>();
current = header;
int j = 1;
while (current.Next != null && j < i)
{
++j;
current = current.Next;
}
return current;
}
/// <summary>
/// 插入操作,在第i个节点前面
/// </summary>
/// <param name="item"></param>
/// <param name="i"></param>
public void Insert(T item, int i)
{
DBNode<T> current = FindNode(i);
DBNode<T> newNode = new DBNode<T>(item);
if (current != null)
{
current.Prev.Next = newNode;
newNode.Next = current;
newNode.Prev = current.Prev;
current.Prev = newNode;
}
else
{
Console.Write("the node is not exist!");
}
}
/// <summary>
/// 插入操作,在第i个节点后面插入item
/// </summary>
/// <param name="item"></param>
/// <param name="i"></param>
public void InsertBack(T item, int i)
{
DBNode<T> current = FindNode(i);
DBNode<T> newNode = new DBNode<T>(item);
if (current != null)
{
current.Next.Prev = newNode;
newNode.Prev = current;
newNode.Next = current.Next;
current.Next = newNode;
}
else
{
Console.Write("the node is not exist!");
}
}
/// <summary>
/// 附加操作,线性表未满，将值为item的新元素添加到末尾
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
DBNode<T> newNode = new DBNode<T>(item);
DBNode<T> p = new DBNode<T>();
if (header == null)
{
header = newNode;
return;
}
p = header;
while (p.Next != null)
{
p = p.Next;
}
p.Next = newNode;
}
/// <summary>
/// 删除操作
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T Delete(int i)
{
DBNode<T> current = FindNode(i);
if (current != null)
{
current.Prev.Next = current.Next;
current.Next.Prev = current.Prev;
current.Prev = null;
current.Next = null;
return current.Data;
}
else
{
Console.Write("the node is not exist!");
return default(T);
}
}
/// <summary>
/// 取表元
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T GetElem(int i)
{
DBNode<T> current = FindNode(i);
if (current != null)
{
return current.Data;
}
else
{
Console.Write("the node is not exist!");
return default(T);
}
}
/// <summary>
/// 按值查找
/// </summary>
/// <param name="value"></param>
/// <returns>-1:链表或参数异常;0:节点不存在;1:值代表的位置</returns>
public int Locate(T value)
{
if (IsEmpty())
{
Console.Write("list is empty");
return -1;
}
if (value == null)
{
Console.Write("value is empty");
return -1;
}
DBNode<T> current = new DBNode<T>();
current = header;
int result = 0;
while (current.Next != null)
{
if (current.Data.Equals(value))
{
result = 1;
}
}
return result;
}
}
此外，循环链表的基本操作与单链表大体相同，只是判断链表结束的条件并不是判断结点的引用域是否为空，
而是判断结点的引用域是否为头引用，其它没有较大的变化