數據結構(C#)：雙鏈表

雙鏈表每個數據節點都有兩個指針，分別指向其後繼和前驅節點。與單鏈表只能訪問其後繼結點相比 ，具有更大的靈活性；當然占用更多的存儲空間。

前面的單鏈表和這裡的雙鏈表都使用了空的頭結點或稱啞節點，目的是實現有序鏈表時更方便。

直接看代碼：

/*
* 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請留言指出，下一篇介紹循環鏈表的實現。