在每一种编程语言中，基本都会有数组这种数据类型。不过它不仅仅是一种编程语言中的数据类型，还是一种最基础的数据结构。尽管它看起来十分简单，但是我们很多人都没有了解它的精髓。
首先，我们来想一个问题，为什么很多编程语言数组的下标都是从0开始的？从1开始不是更符合人类的思维模式吗？
接下来我们带着这个问题来学习接下来的内容？
如何实现随机访问？
我们都知道数组是一种线性表的数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
这里有两个重点：连续的内存空间和相同类型的数据。（线性表 线性结构 与之对立的还有非线性表 线性结构，想一条线那样，只有前和后两个方向 像数组、队列、栈、链表等都是线性结构）
那么数组是如何实现随机访问的？
正是因为它是一种线性的结构和连续的内存空间，他才可以有这个特性。但是这个特性也有弊端，这两个限制让它的删除和插入操作变得十分低效。比如在数组中删除插入了一个数据，为了保证它的连续性，那么就需要将大量的数据进行搬移。
我们要删除3，则需要将4和5进行移动，使他连续。
我们先来解决第一个问题，数组是如何实现根据下标随机访问的？
我们拿一个长度为10的int型数组int[] a = new int[10]来举例。计算机给数组分配了一块连续的内存空间1000~1039，其中内存的首地址为index = 1000
我们知道，计算机会给每个内存分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，他会首先通过寻址公式，计算出元素存储的地址：这个寻址公式我们在计算机硬件基础课程上学习过
a[i]_address = base_address + i*data_type_sizebase_address 首个元素地址，data_type_size(都是同一种对象)表示数组中每个元素的大小。
低效的插入和删除？
前面我们提到了为了保持内存数据的连续性，会导致插入和删除操作比较低效，那我们有没有什么解决办法来解决这种问题？或者为什么会导致低效？
我们线来看插入操作？
假设数组的长度为n你先在要往第k个位置上插入一个元素，为了将这第k个位置挪出来，给新的数据，我们需要将第k~n个位置的元素向后移动一位。那么插入的时间负责度是多少呢？
如果在第一个位置插入元素，那么所有的数据都需要移动，那么时间复杂度为o(n)这也是最坏时间复杂度，最好时间复杂度是向末尾插入，不需要移动元素，时间复杂度为o(1)。我们在每个位置插入的概率是相同的，所以平均时间复杂度为（1+2+…+n）/n =o(n)。
那么如果我们没有要求数组中的数据是有序的，我们在某个位置插入元素时。我们可以将这个位置的数放到数组的最后，在将元素插入该位置，当然这个前提是数组没有满，如果数组已经满了只需要直接插入即可。如果要保证数组是有序的，那么我们只能将第k个位置已经k位置之后的元素依次往后移动一位。
所以利用这种技巧，在特定的场景下可以做到插入的时间复杂度为o(1);
我们在来看看删除操作。
如果我们要删除数组中的某一个元素，为了数组的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。
和插入操作类似，最坏最好以及平均时间复杂度是一样的。
实际上在某些特殊的场景下，我们并不一定非得追求数据的连续性，如果我们将多次删除操作集中执行在一起，删除的效率是不是会提高很多呢？
如果大家了解jvm的标记清除算法，就会发现这种思想正是标记清除算法的核心思想？
我们在学习很多编程语言中也学到了容器技术，比如java中的ArrayList，它的底层是数组？那么容器是否可以完全替代数组？
我个人觉得容器相对于数组的优势就在于，它封装了很多数组的操作细节，以及支持动态扩容。
那么容器是否可以替代数组呢？
答案是否定的
1.容器无法存储基本数据类型 int boolean … 需要用数组来存储，当然也可以使用包装类
2.如果数据大小事先知道，并且数据操作简单，用不到容器提供的方法，也可以使用数组
3.当表示多维数组时，数组更加直观
其实对于业务开发，我们可以直接使用容器，省时省力。但对于一些底层的开发，对性能要求较高，我们这时候就要首选数组了
那么我们来解释下，为什么大多数编程语言，数组下标从0开始而不是从1开始
1.就是寻址公式
a[k]_address = base_address + k * type_size 从0开始
a[k]_address = base_address + (k-1)*type_size 从1开始
从1开始需要多做一次计算，对于cpu来说，就是多了一条指令
2.更主要的是c语言是从0开始的，之后的编程语言java js等都效仿了C语言为了降低学习成本就从0开始了
数据结构与算法之美学习笔记