資料結構 (C#)：順序表 (Sequential List) 完整實作

C# 順序表實作：介面定義、動態陣列擴容、完整 CRUD 操作

線性表邏輯相鄰元素在記憶體物理相鄰，支援快速隨機存取 (O(1))，但插入刪除需移動元素 (O(n))。本文定義 ILinearList<T> 介面，以動態陣列實作 SequentialList<T>。

一、線性表統一介面

using System.Collections.Generic;

namespace Xianfen.Net.DataStructure
{
    interface ILinearList<T> : IEnumerable<T>
    {
        void Add(T t);
        void AddHead(T t);
        void AddTail(T t);
        void Clear();
        int Count { get; }
        int Find(T t);
        T GetAt(int pos);
        T GetHead();
        T GetTail();
        void InsertAt(T t, int pos);
        bool IsEmpty { get; }
        void RemoveAll();
        void RemoveAt(int pos);
        void RemoveHead();
        void RemoveTail();
        void SetAt(int pos, T t);
    }
}

二、SequentialList 完整實作

using System;
using System.Collections;
using System.Collections.Generic;

namespace Xianfen.Net.DataStructure
{
    public class SequentialList<T> : ILinearList<T>
    {
        private T[] m_List;
        private int m_Count;
        private int m_Capacity;

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

        public SequentialList() : this(16) { }

        public SequentialList(int capacity)
        {
            m_Count = 0;
            m_Capacity = capacity;
            m_List = new T[m_Capacity];
        }

        public void Add(T t) { InsertAt(t, m_Count); }
        public void AddHead(T t) { InsertAt(t, 0); }
        public void AddTail(T t) { Add(t); }

        public void Clear() { m_Count = 0; }

        public int Find(T t)
        {
            for (int i = 0; i < m_Count; i++)
                if (m_List[i].Equals(t)) return i;
            return -1;
        }

        public T GetAt(int pos)
        {
            if (pos >= m_Count || pos < 0) throw new IndexOutOfRangeException("pos");
            return m_List[pos];
        }

        public T GetHead() { return m_List[0]; }
        public T GetTail() { return m_List[m_Count - 1]; }

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

            EnsureCapacity();

            // 向後搬移元素騰出空位
            for (int i = m_Count - 1; i >= pos; i--)
                m_List[i + 1] = m_List[i];

            m_List[pos] = t;
            m_Count++;
        }

        public void RemoveAll() { Clear(); }

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

            // 向前搬移元素覆蓋被刪除位置
            for (int i = pos; i < m_Count; i++)
                m_List[i] = m_List[i + 1];

            m_Count--;
        }

        public void RemoveHead() { RemoveAt(0); }
        public void RemoveTail() { RemoveAt(m_Count - 1); }

        public void SetAt(int pos, T t)
        {
            if (pos >= m_Count || pos < 0) throw new IndexOutOfRangeException("pos");
            m_List[pos] = t;
        }

        // 動態擴容：容量不足時翻倍，參考 StringBuilder 策略
        private void EnsureCapacity()
        {
            if (m_Count + 1 > m_Capacity)
            {
                m_Capacity *= 2;
                if (m_Count + 1 > m_Capacity) m_Capacity = m_Count + 1;

                T[] tempArray = new T[m_Capacity];
                for (int i = 0; i < m_Count; i++) tempArray[i] = m_List[i];
                m_List = tempArray;
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            for (int i = 0; i < m_Count; i++) yield return m_List[i];
        }

        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
    }
}

三、關鍵設計解析

四、下一步預告

下一篇將實作單向鏈結串列 (SingleLinkedList)，以指標取代搬移，優化插刪效能。