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

C# 雙向鏈結串列：雙指標節點、哨兵頭節點、雙向遍歷與最近路徑定位優化

雙向鏈結串列每節點擁有 Next 與 Prior 兩指標，支援雙向遍歷、O(1) 尾端插入刪除。本文採用哨兵頭節點 (Dummy Head) 簡化邊界條件，並實作「最近路徑」定位優化：索引 > 中點時從尾端反向尋找。

一、節點類別定義

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; }
}

二、DoubleLinkedList 核心實作

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;
    }

    // --- 核心輔助：最近路徑定位節點 ---
    private DoubleLinkedListNode<T> GetNodeAt(int pos)
    {
        if (pos >= m_Count || pos < 0) throw new IndexOutOfRangeException("pos");

        DoubleLinkedListNode<T> currentNode = null;

        // 索引在後半段：從尾端反向尋找
        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 void InsertAt(T t, int pos)
    {
        if (pos > m_Count || pos < 0) throw new IndexOutOfRangeException("pos");
        if (m_Count == int.MaxValue) throw new ArithmeticException();

        var insertNode = new DoubleLinkedListNode<T>(t);

        // 尾端插入：O(1)
        if (pos == m_Count)
        {
            insertNode.Prior = m_Tail;
            m_Tail.Next = insertNode;
            m_Tail = insertNode;
            m_Count++;
            return;
        }

        // 中間插入：四指標重連
        var currentNode = GetNodeAt(pos);
        insertNode.Prior = currentNode.Prior;
        insertNode.Next = currentNode;
        currentNode.Prior.Next = insertNode;
        currentNode.Prior = insertNode;
        m_Count++;
    }

    // --- 刪除 ---
    public void RemoveAt(int pos)
    {
        if (pos == m_Count - 1) // 尾端刪除：O(1)
        {
            m_Tail = m_Tail.Prior;
            m_Tail.Next = null;
            m_Count--;
            return;
        }

        var currentNode = GetNodeAt(pos);
        currentNode.Prior.Next = currentNode.Next;
        currentNode.Next.Prior = currentNode.Prior;
        m_Count--;
    }

    // --- 其他介面方法簡略 ---
    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 bool IsEmpty { get { return m_Count == 0; } }
    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 SetAt(int pos, T t) { GetNodeAt(pos).Value = t; }
    public int Find(T t) { /* 遍歷比對 */ }
    public void RemoveHead() { RemoveAt(0); }
    public void RemoveTail() { RemoveAt(m_Count - 1); }
    public void RemoveAll() { Clear(); }

    // 迭代器
    public IEnumerator<T> GetEnumerator()
    {
        var currentNode = m_Head;
        while ((currentNode = currentNode.Next) != null) yield return currentNode.Value;
    }
    IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
}

三、關鍵優化總結

• 哨兵頭節點：m_Head 不儲存資料，統一插入刪除邏輯，免去頭節點特判。
• 雙向指標：支援 Prior 反向遍歷，尾端操作 O(1)。
• 最近路徑定位：GetNodeAt 根據索引位置決定從頭或尾尋找，平均查找步數減半。
• 尾端快速路徑：InsertAt(pos==Count)、RemoveAt(pos==Count-1) 直接操作 m_Tail，無需遍歷。

四、下一步預告

下一篇將在此基礎上實作循環鏈結串列 (CircularlyLinkedList)，並解決約瑟夫問題。