数据结构——数组
数组是程序中最常见的数据结构，它可以存储一个固定大小的相同类型元素的顺序集合（强类型语言）。数组的元素都是由连续的内存位置组成。最低的地址对应第一个元素，最高的地址对应最后一个元素，通过索引可以非常容易找到某一个元素。
大多数时候我们需要使用一个大小可变的数组（C#、Python中的list），本文就基于数组来实现一个动态数组，由于在Python中的列表已经对数组封装的很好，这里我们使用C#来实现一个List。在后续介绍数据结构文章中，我会使用python和C#分别来实现相应的数据结构。
动态数组和普通数组在用户使用上没有区别，我们定义一个类MyArray，内部维护一个数组，并不需要实现太多方法，最核心的是提供扩容、索引和增删功能。
class MyArray<T>
{
private T[] array; //存储数组
private int count; //存储数组大小
private int capacity; //数组容量
public int Count { get { return count; } }
public int Capacity { get { return capacity; } }
//重载构造函数 接收一个初始容量
public MyArray(int capacity){ }
// 改变数组大小
private void resize(int capacity) { }
//在指定索引处插入元素
public void Insert(int index,T item) { }
//移除指定位置元素
public void RemoveAt(int index) { }
//正序获取元素位置
public int IndexOf(T item) { }
//实现索引器
public T this[int index] { }
}下面我们按上面的方法一点一点来实现我们的MyArray
1.实现构造函数
构造函数在功能上是为了初始化数组，所以用户可以传递一个初始数组容量，当然考虑到我们的数组本身是动态的，所以如果用户不传入初始容量时，我们应该使用默认大小创建数组。
public MyArray(int capacity)
{
//接收一个初始容量capacity
if (capacity > 0)
{
this.capacity = capacity;
array = new T[capacity];
}
else
throw new Exception("列表容量必须大于0");
}
public MyArray()
{
//构造函数 初始化默认数组
capacity = 4;
array = new T[capacity];
}在这里我们设置如果用户没有传入capacity，默认数组大小为4。我们还维护了一个变量this.capacity，其实这个变量并不必要，可以直接通过array.length获得数组容量。
2.实现数组扩容方法
思路十分简单，我们实例化一个新数组，把旧数组的数据复制到新数组即可。
private void resize(int capacity) {
// 改变数组大小
T[] newarray = new T[capacity];
Array.Copy(array, newarray, count);
array = newarray;
this.capacity = capacity;
}3.增加元素—Insert方法
把一个元素插入数组指定位置，可以分两种情况讨论：一是追加到数组末尾，二是插入到数组中。
第一种情况处理起来很简单，因为我们定义的类维护了一个count变量，它记录了数组的实际大小，所以我们只要赋值array[count]，count++就可以实现功能。
第二种情况代表原来的位置已经有元素了，那么原位置之后的元素都应该集体向后挪一个位置，array[i+1] = array[i]，我们可以用一个for循环来实现。
public void Insert(int index,T item)
{
//在指定索引处插入元素
if (index > count || index <0)
{
throw new Exception("索引超出范围");
}
if (capacity == count)
{
//数组扩容
resize(capacity * 2);
}
if (index == count)
{
//第一种情况，在末尾追加元素追加元素
array[count] = item;
count++;
} else
{
for (int i = count - 1; i>=index; i--)
{
//最后一次循环应为array[index+1] = array[index]
array[i + 1] = array[i];
}
array[index] = item;
count++;
}
}值得注意的是，插入元素可能会超出数组大小，所以我们做了一层capacity==count的判断，如果为真，我们就调用resize方法，将数组扩容至原来的两倍。
4.删除指定位置元素
删除元素的思路和增加元素的思路相反，把索引为i的元素删除后，后面的元素应该前进一位。
public void RemoveAt(int index)
{
//移除指定位置元素
if (index >= count || index < 0)
{
throw new Exception("索引超出范围");
} else
{
for (int i = index; i < count - 1; i++)
{
//只要实现array[index] = array[index+1]
//若i=count-1；则i+1可能会出现超出索引的情况，故条件为i<count-1
array[i] = array[i + 1];
}
count--;
if (count < capacity / 4) {
resize(capacity/2);
}
}
}在删除元素中，我们最后调用了resize方法，当元素个数小于数组的1/4时，我们把数组缩小至原来的1/2。
5.查找元素的索引
十分简单，循环数组即可
public int IndexOf(T item)
{
//正序获取元素位置 若无返回-1
for (int i = 0; i < count; i++)
{
if (array[i].Equals(item))
{
return i;
}
}
return -1;
}6.实现索引器
public T this[int index]
{
get { return array[index]; }
set { array[index] = value; }
} 好了，到现在我们的MyArray最核心的功能完成了，当然你可以为它添加其他方法，让它在用户使用体验上，和原生数组更为相近。最后我们来看看各项操作的时间复杂度。
Insert方法，在末尾添加元素时间复杂度为O(1)，在数组最前面添加元素为O(n)，均摊时间复杂度为O(n)
RemoveAt方法，在末尾删除元素时间复杂度为O(1)，在数组最前面添加元素为O(n)，均摊时间复杂度为O(n)
IndexOf和resize方法，遍历数组，时间复杂度为O(n)
索引器，按索引访问元素，时间复杂度为O(1)