資料結構 (C#)：雙向鏈結串列完整實作

雙向鏈結串列特性

• 每節點擁有前驅與後繼兩個指標，靈活性較高
• 佔用較多儲存空間
• 採用空白頭節點（哑節點）便於有序串列操作

完整程式碼

namespace Xianfen.Net.DataStructure {
    public class DoubleLinkedListNode<T> {
        private T m_Value;
        private DoubleLinkedListNode<T> m_Next, 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, m_Tail;
        public DoubleLinkedList() { m_Count = 0; m_Head = new DoubleLinkedListNode<T>(); m_Tail = m_Head; }
        public DoubleLinkedList(T t) : this() { /* 初始化頭尾節點 */ }
        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) { /* 從頭遍歷比對 */ }
        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) { /* 含尾部快速插入、中間插入雙向指標調整 */ }
        private DoubleLinkedListNode<T> GetNodeAt(int pos) { /* 雙向查找：從較近一端（頭或尾）開始遍歷 */ }
        public bool IsEmpty { get { return m_Count == 0; } }
        public void RemoveAll() { Clear(); }
        public void RemoveAt(int pos) { /* 含尾部快速移除、中間雙向指標調整 */ }
        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() { /* yield return 遍歷 */ }
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
    }
}

下一篇介紹循環鏈結串列。