编程语言中，基本都会有数组这种数据类型。不过，它不仅仅是编程语言中的一种数据类型，还是一种最基础的数据结构。
一、数组支持随机访问
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组类型相同的数据。
1.1 线性表
线性表就是数据排成一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。
与线性表相对应的是非线性表，在非线性表中，数据之间并不是简单的前后关系，比如二叉树、堆、图等。
1.2 连续的内存空间和相同的数据类型
正是因为这两个特点，数组才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个特点也让数组的插入、删除变得低效，因为为了保证连续性，需要做大量的数据搬移工作。
说到数据的访问，那你知道数组是如何实现根据下标随机访问数组元素的吗？
我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10] 来举例。在下面的图中，计算机给数组 a[10] 分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。
我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：
a[i]_address = base_address + i * data_type_size
其中 data_type_size 表示数组中每个元素的大小。在这个例子里，数组中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。
所以，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。另外，缓存行让数组的访问变得更快。
二、数组插入和删除速度慢
2.1 插入
假如有一个长度为 n 的数组，如果要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～(n - 1) 这部分元素都往后挪一位。如果 k = n - 1，也就是在数组末尾插入数据，那就不需要移动其他数据，这时的时间复杂度为 O(1)。但如果 k = 0，也就是在数组的开头插入元素，那所有的数据都需要依次往后移动一位，最坏的时间复杂度是 O(n)。 因为在数组每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1 + 2 + ... n) / n = O(n)。
如果数组中的数据是有序的，要在某个位置插入一个新元素时，就必须搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数据插入到第 k 个位置，为了避免大规模的数据搬移，可以直接将第 k 位的数据移到数组的最后，把新元素直接放入第 k 个位置。利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。快速排序就用到了这个处理思想。
为了更好地理解，我们看一个例子。假设数组 a[10] 中存储了如下 5 个元素：a，b，c，d，e。现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5]，将 a[2] 赋值为 x 即可。最后，数组中的元素如下： a，b，x，d，e，c。
2.2 删除
和插入类似，如果要删除数组第 k 个位置的数据，为了内存的连续性，也需要搬移数据。如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)。
实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率会提高很多。
比如，数组 a[10] 中存储了 7 个元素：a，b，c，d，e，f，g。现在，我们要依次删除 a，b，c 三个元素。
为了避免 d，e，f，g 这几个数据会被搬移三次，就可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录对应下标的数据已经被删除。当数组没有更多空间存储数据时，再执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。这就是 JVM 中“标记清除”垃圾回收算法的核心思想。
数据结构和算法的魅力就在于此，很多时候我们并不需要死记硬背某个数据结构或者算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。如果你细心留意，不管是在软件开发还是架构设计中，总能找到某些算法和数据结构的影子。
三、警惕数组下标越界
数组下标越界是开发者常犯的错误，一定要谨记。长度为 n 的数组，下标是 [0, n - 1]。
四、数组下标从0开始的原因
在大多数编程语言中，数组下标都是从 0 开始，而不是从 1 开始。原因可能有两方面：
4.1 性能更好
从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。我们知道，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 data_type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：
a[k]_address = base_address + k * data_type_size
但是，如果数组下标从 1 开始，计算数组元素 a[k] 的内存地址就会变为：
a[k]_address = base_address + (k-1) * data_type_size
对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。
4.2 历史原因
上面说的性能优势应该算不上压倒性的证明，数组下标从 0 开始，最主要的可能是历史原因。
C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在一定程度上减少 C 语言程序员学习 Java 的成本，因此继续沿用了从 0 开始的习惯。实际上，很多语言中数组也并不是从 0 开始计数的，比如 Matlab。甚至还有一些语言支持负数下标，比如 Python。
五、容器不能完全替代数组
5.1 容器的优势
封装细节
针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList。它将很多数组操作的细节封装起来，比如数组插入、删除数据时需要搬移其他数据等，使用起来更加方便。
动态扩容
数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。如果使用 ArrayList，我们就完全不需要关心底层的扩容逻辑。每次存储空间不够的时候，它都会将空间自动扩容为原来的 1.5 倍。
不过，扩容操作涉及内存申请和数据搬移，是比较耗费性能的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候指定容量，避免大数据量造成的内存和性能消耗。
5.2 数组的优势
可存储基本数据类型
Java 的 ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
多维数组更直观
当要表示多维数组时，用数组往往会更加直观。比如 int[ ][ ] arr，而用容器的话则需要这样定义：ArrayList<ArrayList<Integer>> list。
总的来说，日常业务开发，直接使用容器就足够了，省时省力。毕竟损耗一点性能，完全不会影响到系统整体的性能。但如果是做一些非常底层的开发，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。
标签：基本,下标,删除,元素,插入,数组,数据结构,数据 From： https://www.cnblogs.com/luwei0424/p/17162443.html