C# 泛型約束實戰：打造型別安全的可排序單向鏈表

約束語法速覽

where T : IComparable<T>   // 必須實作介面
where T : class             // 必須為參考型別
where T : struct            // 必須為值型別（非 Nullable）
where T : new()             // 必須有無參建構子
where T : BaseClass         // 必須繼承指定基類
where T : U                 // 裸型別參數約束

案例：可排序單向鏈表

節點定義

public class Node<T> : IComparable<Node<T>> where T : IComparable<T> {
    public T Data { get; }
    public Node<T> Next { get; private set; }
    public Node<T> Prev { get; private set; }

    public Node(T data) => Data = data;

    public int CompareTo(Node<T> other) => Data.CompareTo(other.Data); // 約束保證 T 有 CompareTo
}

鏈表核心邏輯：遞迴插入維持有序

public class LinkedList<T> where T : IComparable<T> {
    private Node<T> _head;

    public void Add(T data) {
        var node = new Node<T>(data);
        if (_head == null) _head = node;
        else _head = _head.Add(node); // 從頭節點開始遞迴找位置
    }

    // 索引器：O(n) 遍歷
    public T this[int index] {
        get {
            var cur = _head;
            for (int i = 0; cur != null && i <= index; i++, cur = cur.Next)
                if (i == index) return cur.Data;
            throw new ArgumentOutOfRangeException();
        }
    }
}

Node.Add 遞迴插入邏輯

public Node<T> Add(Node<T> newNode) {
    if (this.CompareTo(newNode) > 0) { // 新節點小於目前 → 插在前面
        newNode.Next = this;
        if (Prev != null) { Prev.Next = newNode; newNode.Prev = Prev; }
        Prev = newNode;
        return newNode; // 可能成為新頭節點
    }
    else { // 大於等於 → 往後找
        if (Next != null) Next.Add(newNode);
        else { Next = newNode; newNode.Prev = this; }
        return this; // 頭節點不變
    }
}

測試驗證

var intList = new LinkedList<int>();
var rnd = new Random();
for (int i=0; i<10; i++) { var n = rnd.Next(10); intList.Add(n); Console.Write(n + " "); }
// Adding: 2 1 2 6 1 5 9 0 5 3

var empList = new LinkedList<Employee>();
empList.Add(new Employee("John"));
empList.Add(new Employee("Paul"));
empList.Add(new Employee("George"));
empList.Add(new Employee("Ringo"));

Console.WriteLine(intList);  // 0,1,1,2,2,3,5,5,6,9
Console.WriteLine(empList);  // George, John, Paul, Ringo

約束帶來的安全性

• Node<T>.CompareTo 直接呼叫 Data.CompareTo，**編譯期保證 T 實作 IComparable<T>**，無需執行期檢查。
• 嘗試 new LinkedList() 即編譯失敗，錯誤訊息明確指出缺少介面實作。
• 結構 Employee 實作 IComparable<Employee> 即可放入鏈表，展現值類型同樣適用。

延伸應用

同樣模式可建構：

• 二元搜尋樹（where T : IComparable<T>）
• 優先權佇列（where T : IComparable<T>）
• 泛型快取（where T : class, new()）