数组是一种最基础的数据结构，在大部分编程语言中，数组都是从 0 开始编号的。
线性表（Linear List），就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向，包括数组，链表、队列、栈等。
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
非线性表，数据之间并不是简单的前后关系，有二叉树、堆、图等，如下图：
数组使用了连续的内存空间和相同类型的数据。使得它可以“随机访问”，但同时也让数组的删除、插入等操作变得非常低效，为了保证连续性，就需要做大量的数据搬移工作。
数组是如何实现根据下标随机访问数组呢？
以一个长度为 10 的 int 类型的数组 int[] a = new int[10]为例。
计算机会给每个内存单元分配一个地址，并通过地址来访问内存中的数据。
下图中，假设计算机给数组 a[10]，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。
当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：
a[i]_address = base_address + i * data_type_size
上面的数组中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。