雙鏈表每個數據節點都有兩個指針，分別指向其後繼和前驅節點。與單鏈表只能訪問其後繼結點相比 ，具有更大的靈活性；當然占用更多的存儲空間。
前面的單鏈表和這裡的雙鏈表都使用了空的頭結點或稱啞節點，目的是實現有序鏈表時更方便。
直接看代碼：
/*
* File : DoubleLinkedList.cs
* Author : Zhenxing Zhou
* Date : 2008-12-06, 2008-12-07
* Blog : http://www.xianfen.Net/
*/
using System;
using System.Collections.Generic;
namespace Xianfen.Net.DataStructure
{
public class DoubleLinkedListNode<T>
{
private T m_Value;
private DoubleLinkedListNode<T> m_Next;
private DoubleLinkedListNode<T> m_Prior;
public T Value
{
get { return m_Value; }
set { m_Value = value; }
}
public DoubleLinkedListNode<T> Next
{
get { return m_Next; }
set { m_Next = value; }
}
public DoubleLinkedListNode<T> Prior
{
get { return m_Prior; }
set { m_Prior = value; }
}
public DoubleLinkedListNode()
{
}
public DoubleLinkedListNode(T t)
{
m_Value = t;
}
}
public class DoubleLinkedList<T> : ILinearList<T>
{
protected int m_Count;
protected DoubleLinkedListNode<T> m_Head;
protected DoubleLinkedListNode<T> m_Tail;
public DoubleLinkedList()
{
m_Count = 0;
m_Head = new DoubleLinkedListNode<T>();
m_Tail = m_Head;
}
public DoubleLinkedList(T t)
: this()
{
m_Count = 1;
m_Head.Next = new DoubleLinkedListNode<T>(t);
m_Tail = m_Head.Next;
m_Tail.Prior = m_Head;
}
public void Add(T t)
{
InsertAt(t, m_Count);
}
public void AddHead(T t)
{
InsertAt(t, 0);
}
public void AddTail(T t)
{
Add(t);
}
public void Clear()
{
m_Count = 0;
m_Tail = m_Head;
m_Head.Next = null;
m_Head.Prior = null;
}
public int Count
{
get { return m_Count; }
}
public int Find(T t)
{
DoubleLinkedListNode<T> currentNode = m_Head;
int pos = 0;
while ((currentNode = currentNode.Next) != null)
{
if (currentNode.Value.Equals(t))
{
return pos;
}
pos++;
}
return -1;
}
public T GetAt(int pos)
{
return GetNodeAt(pos).Value;
}
public T GetHead()
{
return GetNodeAt(0).Value;
}
public T GetTail()
{
return m_Tail.Value;
}
public void InsertAt(T t, int pos)
{
if (pos > m_Count || pos < 0)
{
throw new IndexOutOfRangeException("pos");
}
if (m_Count == int.MaxValue)
{
throw new ArithmeticException();
}
DoubleLinkedListNode<T> insertNode = new DoubleLinkedListNode<T> (t);
if (pos == m_Count)
{
insertNode.Prior = m_Tail;
m_Tail.Next = insertNode;
m_Tail = insertNode;
m_Count++;
return;
}
DoubleLinkedListNode<T> currentNode = GetNodeAt(pos);
insertNode.Prior = currentNode.Prior;
insertNode.Next = currentNode;
currentNode.Prior.Next = insertNode;
currentNode.Prior = insertNode;
m_Count++;
}
private DoubleLinkedListNode<T> GetNodeAt(int pos)
{
if (pos >= m_Count || pos < 0)
{
throw new IndexOutOfRangeException("pos");
}
DoubleLinkedListNode<T> currentNode = null;
// 最近的途徑找到pos位置的節點
if (pos > m_Count / 2)
{
currentNode = m_Tail;
pos = m_Count - pos - 1;
while (pos-- > 0)
{
currentNode = currentNode.Prior;
}
}
else
{
currentNode = m_Head.Next;
while (pos-- > 0)
{
currentNode = currentNode.Next;
}
}
return currentNode;
}
public bool IsEmpty
{
get { return m_Count == 0; }
}
public void RemoveAll()
{
Clear();
}
public void RemoveAt(int pos)
{
if (pos == m_Count - 1)
{
m_Tail = m_Tail.Prior;
m_Tail.Next = null;
m_Count--;
return;
}
DoubleLinkedListNode<T> currentNode = GetNodeAt(pos);
currentNode.Prior.Next = currentNode.Next;
currentNode.Next.Prior = currentNode.Prior;
m_Count--;
}
public void RemoveHead()
{
RemoveAt(0);
}
public void RemoveTail()
{
RemoveAt(m_Count - 1);
}
public void SetAt(int pos, T t)
{
GetNodeAt(pos).Value = t;
}
public IEnumerator<T> GetEnumerator()
{
DoubleLinkedListNode<T> currentNode = m_Head;
while ((currentNode = currentNode.Next) != null)
{
yIEld return currentNode.Value;
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
}
如果發現BUG請留言指出，下一篇介紹循環鏈表的實現
