C# 從零手寫鏈結清單：單向、雙向鏈結清單完整實作與應用場景

前言：為什麼要學習鏈結清單？

陣列雖然存取快（O(1)），但大小固定、中間插刪需大量搬移元素（O(n)）。鏈結清單透過節點指標串連，完美解決「動態擴容」與「高效插刪」問題，是理解資料結構、邏輯思維進階的必經之路。本文將帶你從 Node 節點定義出發，逐步實作單向與雙向鏈結清單，並附上貪食蛇、循環地圖等實際應用場景。

核心節點結構

/// 
單向鏈結清單節點
public class Node
{
    public int Data;      // 資料欄位
    public Node Next;     // 指向下一個節點
}

單向鏈結清單 MyList 實作

public class MyList
{
    private Node _head;   // 頭節點
    private Node _tail;   // 尾節點指標，O(1) 尾端新增

    public void Add(int value)
    {
        var newNode = new Node { Data = value };
        if (_head == null)
        {
            _head = _tail = newNode;
        }
        else
        {
            _tail.Next = newNode;
            _tail = newNode;
        }
    }

    public void Print()
    {
        var current = _head;
        while (current != null)
        {
            Console.WriteLine(current.Data);
            current = current.Next;
        }
    }
}

客戶端測試程式碼

var list = new MyList();
list.Add(1);
list.Add(11);
list.Add(111);
list.Add(1111);
list.Print();
// 輸出：1 11 111 1111

進階：雙向鏈結清單 DoublyLinkedList

雙向鏈結清單在單向基礎上新增 Prev 指標，支援雙向遍歷與 O(1) 刪除已知節點。

public class DNode
{
    public object Data;
    public DNode Next;
    public DNode Prev;

    public DNode(object data = null)
    {
        Data = data;
    }
}

public class DoublyLinkedList
{
    private readonly DNode _header = new DNode("Header"); // 哨兵節點

    public DoublyLinkedList()
    {
        _header.Next = _header.Prev = _header; // 循環雙向鏈結，簡化邊界判斷
    }

    // 尋找節點
    private DNode Find(object item)
    {
        var current = _header.Next;
        while (current != _header && !Equals(current.Data, item))
            current = current.Next;
        return current == _header ? null : current;
    }

    // 在指定節點後插入
    public void Insert(object newItem, object afterItem)
    {
        var current = Find(afterItem);
        if (current == null) return;

        var newNode = new DNode(newItem);
        newNode.Next = current.Next;
        newNode.Prev = current;
        current.Next.Prev = newNode;
        current.Next = newNode;
    }

    // 刪除節點
    public void Remove(object item)
    {
        var node = Find(item);
        if (node == null || node == _header) return;

        node.Prev.Next = node.Next;
        node.Next.Prev = node.Prev;
        node.Next = node.Prev = null; // 協助 GC
    }

    // 正向列印
    public void PrintForward()
    {
        var current = _header.Next;
        while (current != _header)
        {
            Console.WriteLine(current.Data);
            current = current.Next;
        }
    }

    // 逆向列印
    public void PrintReverse()
    {
        var current = _header.Prev;
        while (current != _header)
        {
            Console.WriteLine(current.Data);
            current = current.Prev;
        }
    }
}

哨兵節點設計優勢

• 頭尾皆指向 _header，形成循環結構，插刪邏輯無需分「頭/中/尾」三種情況，程式碼更簡潔、Bug 更少。
• Find 回傳 null 表示未找到，呼叫端可直接判斷。

實戰應用場景

總結

手寫鏈結清單不僅是面試必考題，更能深化對指標、記憶體佈局、邊界條件的理解。掌握單向與雙向兩種結構，並熟悉哨兵節點技巧，將為你處理複雜動態資料打下堅實基礎。