数据结构之数组

数组是最基础的数据结构，你可能觉得它非常简单。其实真的非常简单，但里面有一些细节还是稍微要注意一下的。

先看一下数组的定义：数组是一种线性的数据结构，用连续的内存存放相同类型的数据。线性结构表示数据只有前后两个方向，像队列、栈、链表都是线性结构。与之对立是的非线性结构，其表示不止前后两个方向，像树、堆、图都是非线性结构。连续的内存这个很好理解，表示程序会在内存中开辟一段连续的空间用于存放数据，这样才能实现随机访问，且时间复杂度为O(1)。

先说下随机访问，这是数组的最大优势了。随机访问可以实现只需要一步就能读取到要查询的值。我们知道数组变量，在访问里面的元素时，只要知道基址地址和数据类型大小就可以。比如定义数组int[] a = new int[10]，a[0]的地址为1000，数据类型大小为4字节(int)，现在要访问第三个元素，计算公式为1000*2*4，即1008这个地址就是a[2]的数据。CPU有了这个地址后，就可以直接跳到这个内存地址读取数据，其时间复杂度为O(1)。

上面说的随机读取，即事先要知道要访问元素的下标索引才能实现O(1)，如果你要在数组中查找一个元素，其时间复杂度为O(n)。因为查询数据，还是得从头到尾挨个遍历，假如查找的元素正好是第一个，则时间复杂度为O(1)，但我们计算时间复杂度一般是最坏情况下的复杂度，比如查找的数据正好在最后一个，则时间复杂度为O(n)。如果数组是有序的，可以使用二分查找，时间复杂度为O(logn)。

再说一下插入。如果插入到结尾，则时间复杂度为O(1)。如果插入到中间位置，还要再分两种情况：无序和有序。无序即不用考虑数据顺序，数据可以存放数组中的任意位置，这时如果将新数据插入到指定位置时，可以不用移动元素，直接将指定位置的元素放到数组最后，再将指定位置数据改为新数据即可，这样时间复杂度也是为O(1)。再说一下有序，有序表示数组内的元素是有顺序的，比如从小到大，这时插入新数据时，要维持其有序性，就要挨个元素比较，打到适合的位置，比如k位置插入，插入前要先将k到n的数据全部向后移动，移好后再将新数据添加至k位置，其时间复杂度为O(n)。

最后说一下删除。如果删除最后一个元素，则时间复杂度为O(1)。如果删除的元素位置在数组的中间，则为了保证数据的连续性，需要将后面的元素移动到删除的位置后。比如删除k位置的数据，删除后，需要将k到n的数据都向前挪一个位置，则时间复杂度为O(n)。但这里有一个技巧减少删除后数据的频繁移动，我们可以在删除数据时并不进行真正的删除操作，先给这个数据打一个已删除标记，然后正常使用数组，等数组空间不足时，再将这些已标上删除标记的元素统一删除，最后再整体移动一下数据，这样只要移动一次数据即可。CLR和JVM中的垃圾回收机制(GC)就是使用了这种方法。

在实际开发中，我们经常使用一些容器类来代替数组，比如List、ArrayList。容器类封装了数组的操作细节，比如动态扩容，大部分情况下我们使用这些容器类即可。但二维情况下尽量还是使用数组，比如int[][]就比List<List<int>>更直观。

最后再补充一下，开发中常见的其他数据结构，比如队列、栈。其实里面也是用的数组作为数据结构，只是不同的数据结构对数组进行不同的操作约束，比如队列只能先进先出，栈只能先进后出。具体大家可以看下自己使用语言下的这些数据结构的源码，就知道了。