顺序表：ArrayList的原理及实现

顺序表在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

**线性表的特征：**
1.第一个数据元素没有前驱，这个数据元素被称为头结点。
2.最后一个数据元素没有后继，这个数据元素被称为尾结点。
3.除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

顺序表代码实现：

/// <summary>
/// 顺序表
/// </summary>
/// <typeparam name="T"></typeparam>
public class SequenceList<T> : IEnumerable
{
    //存储元素的数据
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;   
    public SequenceList(int capacity)
    {
        this.eles = new T[capacity];
        this.N = 0;
    }

    public void Clear()
    {
        this.N = 0;
    }

    public bool IsEmpty()
    {
        return N == 0;
    }

    public int Length()
    {
        return N;
    }

    public T Get(int i)
    {
        return this.eles[i];
    }

    public void insert(T t)
    {
        this.eles[N++] = t;
    }

    public void insert(int i, T t)
    {
        for (int index = N; index > i; index--)
        {
            eles[index] = eles[index - 1];
        }
        eles[i] = t;
        N++;
    }

    public T Remove(int i)
    {
        T current = eles[i];
        for (int index = i; index < N - 1; index++)
        {
            eles[index] = eles[index - 1];
        }
        N--;
        return current;
    }

    public int indexOf(T t)
    {
        for (int i = 0; i < N; i++)
        {
            if (Object.ReferenceEquals(eles[i], t))
            {
                return i;
            }
        }
        return -1;
    }

    public IEnumerator GetEnumerator()
    {
        return new MyEnumerator(eles);
    }

    public class MyEnumerator : IEnumerator
    {

        T[] eles;
        int idx = -1;
        public MyEnumerator(T[] eles)
        {
            idx = 0;
            this.eles = eles;
        }
        public object Current
        {
            get
            {
                if (idx == -1)
                    return new IndexOutOfRangeException();
                return eles[idx];
            }
        }
        public bool MoveNext()
        {
            idx++;
            return eles.Length > idx;
        }
        public void Reset()
        {
            idx = -1;
        }
    }
}

总结：由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显。