C# 資料結構實作：雙向鏈表完整程式碼與操作詳解

理論基礎

雙向鏈表每個節點擁有 prev (前驅) 與 next (後繼) 兩個引用，可雙向遍歷，插入/刪除僅需調整 4 個引用，不需從頭查找前驅。

節點類別

public class DbNode
{
    public T Data { get; set; }
    public DbNode Next { get; set; }
    public DbNode Prev { get; set; }

    public DbNode() : this(default) { }
    public DbNode(T val) { Data = val; }
}

雙向鏈表操作類別 (實作 IListDS<T>)

public class DbLinkList : IListDS
{
    private DbNode _header;

    public DbLinkList() { _header = new DbNode(); }

    // 輔助：尋找第 i 個節點 (1-based)
    private DbNode FindNode(int i)
    {
        if (i < 1) return null;
        DbNode cur = _header;
        for (int j = 1; cur.Next != null && j < i; j++)
            cur = cur.Next;
        return cur;
    }

    // 插入於第 i 個節點之前
    public void Insert(T item, int i)
    {
        DbNode cur = FindNode(i);
        if (cur == null) throw new ArgumentException("節點不存在");

        var n = new DbNode(item);
        n.Next = cur;
        n.Prev = cur.Prev;
        cur.Prev.Next = n;
        cur.Prev = n;
    }

    // 插入於第 i 個節點之後
    public void InsertAfter(T item, int i)
    {
        DbNode cur = FindNode(i);
        if (cur == null) throw new ArgumentException("節點不存在");

        var n = new DbNode(item);
        n.Prev = cur;
        n.Next = cur.Next;
        if (cur.Next != null) cur.Next.Prev = n;
        cur.Next = n;
    }

    // 尾部附加
    public void Append(T item)
    {
        var n = new DbNode(item);
        if (_header.Next == null) { _header.Next = n; n.Prev = _header; return; }

        DbNode cur = _header;
        while (cur.Next != null) cur = cur.Next;
        cur.Next = n;
        n.Prev = cur;
    }

    // 刪除第 i 個節點
    public T Delete(int i)
    {
        DbNode cur = FindNode(i);
        if (cur == null) throw new ArgumentException("節點不存在");

        cur.Prev.Next = cur.Next;
        if (cur.Next != null) cur.Next.Prev = cur.Prev;
        T val = cur.Data;
        cur.Prev = cur.Next = null; // 協助 GC
        return val;
    }

    // 取得第 i 個元素
    public T GetElement(int i)
    {
        DbNode cur = FindNode(i);
        return cur?.Data ?? throw new ArgumentException("節點不存在");
    }

    // 其他介面方法：GetLength、Clear、IsEmpty、Locate 略
}

關鍵操作圖解

• 插入前：新節點 Prev→原前驅、Next→原節點；原前驅 Next→新節點；原節點 Prev→新節點。
• 刪除：前驅 Next→後繼；後繼 Prev→前驅；斷開被刪節點引用。

循環雙向鏈表提示

將尾節點 Next 指向頭節點、頭節點 Prev 指向尾節點，判斷結束條件改為 cur.Next == _header，其餘邏輯同。

小結

雙向鏈表以空間換時間，適合頻繁雙向遍歷、任意位置插刪場景。掌握 4 引用調整邏輯是核心。