数组是程序中最常见的数据结构，它可以存储一个固定大小的相同类型元素的顺序集合（强类型语言）。数组的元素都是由连续的内存位置组成。最低的地址对应第一个元素，最高的地址对应最后一个元素，通过索引可以非常容易找到某一个元素。
大多数时候我们需要使用一个大小可变的数组（C#、Python中的list），本文就基于数组来实现一个动态数组，由于在Python中的列表已经对数组封装的很好，这里我们使用C#来实现一个List。在后续介绍数据结构文章中，我会使用python和C#分别来实现相应的数据结构。
动态数组和普通数组在用户使用上没有区别，我们定义一个类MyArray，内部维护一个数组，并不需要实现太多方法，最核心的是提供扩容、索引和增删功能。
下面我们按上面的方法一点一点来实现我们的MyArray
构造函数在功能上是为了初始化数组，所以用户可以传递一个初始数组容量，当然考虑到我们的数组本身是动态的，所以如果用户不传入初始容量时，我们应该使用默认大小创建数组。
在这里我们设置如果用户没有传入capacity，默认数组大小为4。我们还维护了一个变量this.capacity，其实这个变量并不必要，可以直接通过array.length获得数组容量。
思路十分简单，我们实例化一个新数组，把旧数组的数据复制到新数组即可。
把一个元素插入数组指定位置，可以分两种情况讨论：一是追加到数组末尾，二是插入到数组中。
第一种情况处理起来很简单，因为我们定义的类维护了一个count变量，它记录了数组的实际大小，所以我们只要赋值array[count]，count++就可以实现功能。
值得注意的是，插入元素可能会超出数组大小，所以我们做了一层capacity==count的判断，如果为真，我们就调用resize方法，将数组扩容至原来的两倍。
删除元素的思路和增加元素的思路相反，把索引为i的元素删除后，后面的元素应该前进一位。
在删除元素中，我们最后调用了resize方法，当元素个数小于数组的1/4时，我们把数组缩小至原来的1/2。
十分简单，循环数组即可
好了，到现在我们的MyArray最核心的功能完成了，当然你可以为它添加其他方法，让它在用户使用体验上，和原生数组更为相近。最后我们来看看各项操作的时间复杂度。
Insert方法，在末尾添加元素时间复杂度为O(1)，在数组最前面添加元素为O(n)，均摊时间复杂度为O(n)
RemoveAt方法，在末尾删除元素时间复杂度为O(1)，在数组最前面添加元素为O(n)，均摊时间复杂度为O(n)
IndexOf和resize方法，遍历数组，时间复杂度为O(n)
索引器，按索引访问元素，时间复杂度为O(1)
Original: https://www.cnblogs.com/lazyfish007/p/11746995.html
Author: 秋叶红了
Title: 数据结构——数组
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/603934/
转载文章受原作者版权保护。转载请注明原作者出处！