数据结构与算法：数组

一、概念

数组是一种线性表结构。它用一组连续的内存空间来存储一组具有相同类型的数据
**线性表：**数据拍成像一条线一样的结构。eg：数组、链表、队列、栈
非线性表： 二叉树、堆、图


**连续的内存空间来存储一组具有相同类型的数据：**正是因为这两个限制，它才有了随机访问。但是其弊端是如果像插入和删除数据，为了保证连续性，需要做大量的数据搬移工作。
数组和链表区别：
数组适合随机访问，时间复杂度为O(1),数组查找即便是还好序进行二分查找，时间复杂度也要O(logn)链表适合插入和删除，时间复杂度为O(1)

二、数组随机查找、插入、删除

随机查找：
数组如何根据下标随机访问数组元素？
计算机会给内个内存单元分配一个地址，计算机通过地址来访问内存中数据。
当计算机需要随机访问数组中某个元素时，会根据寻址公式计算出该元素的内存地址
寻址公式：a[i]_address = base_address + i * data_type_size
插入：
最优在最后插入时间复杂度为O(1)，最差时间复杂度为O(n)
几种插入：（1）在数组最后插入（2）在数组中插入后面元素整体后移（3）数组中插入，将位置中原元素放在最后
删除：
最优在最后删除时间复杂度为O(1)，最差时间复杂度为O(n)
删除操作：先记录下已经删除的数据，每次删除操作并不是真正的搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，再触发真正的删除操作，大大减少了删除操作导致的数据搬移（JVM标记清除垃圾回收算法的核心思想同）

三、数组访问越界问题

c中会出现访问越界问题，java中会自动解决越界问题

四、为什么数组从0开始编号

计算机会根据寻址公式找到其内存地址
a[k]_address = base_address + k * type_size
a为首地址，i为偏移（下标），如果从1开始编号，寻址公式会变为a[k]_address = base_address + (k-1)*type_size，为了减少一次减法操作