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

C# 單向鏈結串列：節點定義、哨兵頭節點、插入刪除無需搬移、ILinearList 介面實作

單向鏈結串列每節點僅含 Next 指標，插入刪除無需搬移元素 (O(1) 找到位置後)，支援動態記憶體配置，但隨機存取需 O(n) 遍歷。本文採用哨兵頭節點簡化邏輯。

一、節點類別

internal class SingleLinkedListNode<T>
{
    private T m_Value;
    private SingleLinkedListNode<T> m_Next;

    public T Value { get { return m_Value; } set { m_Value = value; } }
    public SingleLinkedListNode<T> Next { get { return m_Next; } set { m_Next = value; } }

    public SingleLinkedListNode() { m_Next = null; }
    public SingleLinkedListNode(T t) : this() { Value = t; }
}

二、SingleLinkedList 核心實作

public class SingleLinkedList<T> : ILinearList<T>
{
    private int m_Count;
    private SingleLinkedListNode<T> m_Head; // 哨兵頭節點

    public SingleLinkedList() { m_Count = 0; m_Head = new SingleLinkedListNode<T>(); }
    public SingleLinkedList(T t) : this() { m_Count = 1; m_Head.Next = new SingleLinkedListNode<T>(t); }

    public bool IsEmpty { get { return m_Count == 0; } }
    public int Count { get { return m_Count; } }

    public void Add(T t) { InsertAt(t, this.Count); }
    public void AddHead(T t) { InsertAt(t, 0); }
    public void AddTail(T t) { Add(t); }

    public void InsertAt(T t, int pos)
    {
        if (pos > this.Count || pos < 0) throw new IndexOutOfRangeException("pos");
        if (m_Count == int.MaxValue) throw new ArithmeticException();

        var currentNode = m_Head;
        while (pos-- > 0) currentNode = currentNode.Next; // 找到插入位置前一節點

        var tempNode = new SingleLinkedListNode<T>(t);
        tempNode.Next = currentNode.Next;
        currentNode.Next = tempNode;
        m_Count++;
    }

    public void RemoveAt(int pos)
    {
        if (pos >= Count || pos < 0) throw new IndexOutOfRangeException("pos");

        var currentNode = m_Head;
        while (pos-- > 0) currentNode = currentNode.Next; // 找到被刪節點前一節點

        currentNode.Next = currentNode.Next.Next; // 跳過被刪節點
        m_Count--;
    }

    public void RemoveHead() { RemoveAt(0); }
    public void RemoveTail() { RemoveAt(this.Count - 1); }
    public void RemoveAll() { m_Head.Next = null; m_Count = 0; }
    public void Clear() { RemoveAll(); }

    public T GetHead() { return GetAt(0); }
    public T GetTail() { return GetAt(this.Count - 1); }
    public T GetAt(int pos) { return GetNodeAt(pos).Value; }

    private SingleLinkedListNode<T> GetNodeAt(int pos)
    {
        if (pos >= Count || pos < 0) throw new IndexOutOfRangeException("pos");
        var currentNode = m_Head;
        while (pos-- > 0) currentNode = currentNode.Next;
        return currentNode.Next;
    }

    public void SetAt(int pos, T t) { GetNodeAt(pos).Value = t; }

    public int Find(T t)
    {
        var node = m_Head; int pos = 0;
        while ((node = node.Next) != null)
        {
            if (node.Value.Equals(t)) return pos;
            pos++;
        }
        return -1;
    }

    public IEnumerator<T> GetEnumerator()
    {
        var node = m_Head;
        while ((node = node.Next) != null) yield return node.Value;
    }
    IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
}

三、關鍵設計重點

• 哨兵頭節點：m_Head 不存資料，InsertAt(0)、RemoveAt(0) 邏輯與中間位置一致，免特判。
• 單向指標：僅能正向遍歷，GetNodeAt、Find 皆為 O(n)。
• 插入/刪除核心：找到前驅節點，調整 Next 指標即可，無陣列搬移開銷。
• 記憶體效率：每節點額外 1 個指標 (32/64-bit)，適合頻繁增刪、大小不定集合。

四、下一步預告

下一篇將擴充為雙向鏈結串列 (DoubleLinkedList)，增加 Prior 指標支援反向遍歷與尾端 O(1) 操作。