C# 從零手寫雙向鏈表：泛型實現 IList 完整教學

鏈表基礎概念

鏈表由節點組成，每個節點包含：

• 資料域：儲存實際值（泛型 T）。
• 引用域：指向前驅 (Prev) 與後繼 (Next) 節點。

雙向鏈表同時維護頭尾指標，支援雙向遍歷、O(1) 尾部插入/刪除。

節點類別

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

    public DNode() { }
    public DNode(T value) { Data = value; }
    public DNode(T value, DNode prev, DNode next)
    {
        Data = value; Prev = prev; Next = next;
    }
}

鏈表主類別：實作 IList<T>

public class LinkList : IList
{
    private DNode _head;
    private DNode _tail;
    private int _count;
    private int _version; // 用於枚舉器版本檢查

    #region 核心操作

    public void Add(T item)
    {
        var node = new DNode(item);
        if (_head == null)
        {
            _head = _tail = node;
        }
        else
        {
            _tail.Next = node;
            node.Prev = _tail;
            _tail = node;
        }
        _count++; _version++;
    }

    public void Insert(int index, T item)
    {
        if (index < 0 || index > _count) throw new ArgumentOutOfRangeException();
        if (index == _count) { Add(item); return; }

        var node = new DNode(item);
        if (index == 0)
        {
            node.Next = _head;
            _head.Prev = node;
            _head = node;
        }
        else
        {
            var cur = GetNode(index);
            node.Prev = cur.Prev;
            node.Next = cur;
            cur.Prev.Next = node;
            cur.Prev = node;
        }
        _count++; _version++;
    }

    public bool Remove(T item)
    {
        var cur = _head;
        while (cur != null)
        {
            if (EqualityComparer.Default.Equals(cur.Data, item))
            {
                RemoveNode(cur);
                return true;
            }
            cur = cur.Next;
        }
        return false;
    }

    public void RemoveAt(int index)
    {
        var node = GetNode(index);
        RemoveNode(node);
    }

    private void RemoveNode(DNode node)
    {
        if (node.Prev != null) node.Prev.Next = node.Next;
        else _head = node.Next;

        if (node.Next != null) node.Next.Prev = node.Prev;
        else _tail = node.Prev;

        _count--; _version++;
    }

    private DNode GetNode(int index)
    {
        if (index < 0 || index >= _count) throw new ArgumentOutOfRangeException();
        // 從較近的一端開始遍歷
        DNode cur = (index < _count / 2) ? _head : _tail;
        int step = (cur == _head) ? index : _count - 1 - index;
        while (step-- > 0) cur = (cur == _head) ? cur.Next : cur.Prev;
        return cur;
    }

    #endregion

    #region 索引器與查詢
    public T this[int index]
    {
        get => GetNode(index).Data;
        set => GetNode(index).Data = value;
    }

    public int IndexOf(T item)
    {
        int i = 0;
        for (var cur = _head; cur != null; cur = cur.Next, i++)
            if (EqualityComparer.Default.Equals(cur.Data, item)) return i;
        return -1;
    }

    public bool Contains(T item) => IndexOf(item) >= 0;
    public int Count => _count;
    public bool IsReadOnly => false;
    public void Clear() { _head = _tail = null; _count = 0; _version++; }
    #endregion

    #region 複製與轉換
    public void CopyTo(T[] array, int arrayIndex)
    {
        int i = arrayIndex;
        for (var cur = _head; cur != null; cur = cur.Next)
            array[i++] = cur.Data;
    }
    #endregion

    #region 進階算法演示
    public void Reverse()
    {
        var cur = _head;
        while (cur != null)
        {
            var next = cur.Next;
            var tmp = cur.Next; cur.Next = cur.Prev; cur.Prev = tmp;
            cur = next;
        }
        var t = _head; _head = _tail; _tail = t;
        _version++;
    }

    // 合併兩個有序鏈表（僅示範 int）
    public static LinkList MergeSorted(LinkList a, LinkList b)
    {
        var result = new LinkList();
        var pa = a._head; var pb = b._head;
        while (pa != null && pb != null)
        {
            if (pa.Data <= pb.Data) { result.Add(pa.Data); pa = pa.Next; }
            else { result.Add(pb.Data); pb = pb.Next; }
        }
        while (pa != null) { result.Add(pa.Data); pa = pa.Next; }
        while (pb != null) { result.Add(pb.Data); pb = pb.Next; }
        return result;
    }

    // 去重（保留首次出現順序）
    public static LinkList Distinct(LinkList list)
    {
        var result = new LinkList();
        var set = new HashSet();
        for (var cur = list._head; cur != null; cur = cur.Next)
            if (set.Add(cur.Data)) result.Add(cur.Data);
        return result;
    }
    #endregion

    #region IEnumerable 實作
    public IEnumerator GetEnumerator()
    {
        int ver = _version;
        for (var cur = _head; cur != null; cur = cur.Next)
        {
            if (ver != _version) throw new InvalidOperationException("集合在枚舉過程中被修改");
            yield return cur.Data;
        }
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
    #endregion
}

測試驗證

var list = new LinkList();
list.Add(3); list.Add(1); list.Add(2);
list.Insert(1, 99); // 3, 99, 1, 2
list.Remove(1);     // 3, 99, 2
list.Reverse();     // 2, 99, 3
foreach (var x in list) Console.Write(x + " "); // 輸出: 2 99 3

教學重點總結

• 雙向指標：Prev/Next 讓頭尾操作均為 O(1)，中間插刪需 O(n) 定位。
• 版本號機制：_version 配合枚舉器檢測並發修改，符合 .NET 框架慣例。
• 實作 IList<T>：自動獲得 CopyTo、IndexOf、LINQ 支援等標準行為。
• 算法擴展：逆序、合併、去重展示鏈表指標操作的靈活性。