什么是数组？

数组是一种线性表数据结构，它用一组连续的存储空间，来存储一组具有相同类型的数据

什么是线性表？

• 线性表：数据存储结构像一条线一样，数据之间有前后关系。线性表有数组、链表、队列和栈等
• 非线性表：数据存储结构不局限于前后关系，比如图、二叉树和堆等
• 两者之间最主要的区别是线性表上的数据最多只有前后两个方向

连续的存储空间和相同类型的数据

数组的这两个特性是实现随机访问的根本，但也因为这个特性导致数组的删除和插入操作比较低效

如何实现随机访问？

因为存储空间的连续，我们只要知道起始地址、访问下标和存储该类型所需字节数就可以得出数组中元素的访问地址
访问地址 = 起始地址 + 访问下标 * 存储该类型所需字节数

删除和插入操作？

数组的删除和插入操作都需要搬移数据来确保数组的连续性。

• 在插入一个元素时，如果不是插入是在末尾，就需要将插入位置之后的所有数据后移。
• 删除也类似，删除的元素如果不在末尾，数组将不连续，需要将删除位置之后的所有数据左移
• 在无序数组中避免数据搬移：在插入时将数据插入尾部，如果删除中间元素就将尾部元素移动到删除的位置。

数组的优缺点

数组支持随机访问，根据数组下标随机访问的时间复杂度为O(1)。
数组不善于插入和删除操作，为了保持连续的存储空间需要搬移数据。

文章整理自：数据结构与算法之美