算法和数据结构1.3数组

数组也是数据呈线性排列的一种数据结构。与链表不同的是，数组中访问数据十分简单，而添加和删除数据比较耗功夫。

a[0],a[1],a[2] 
//其中a是数组的名字，后面的“[]”中的数字表示该数据是数组中第几个数据（这个数字叫做数组下标），下标从0开始计数。

数据按照顺序存储在内存的连续空间内。

由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存中的位置）都可以通过数组下标算出，我们也就可以借此直接访问目标数据（这叫做随机访问）。

数据的访问:

如果想要访问数组arr的第三个元素，直接操作

a[2]

即可。

数据的插入

对一拥有8个数据的数组，如果想要在第三个位置插入一条数据3，那么要操作如下步骤

a[8] = a[7];
a[7] = a[6];
a[6] = a[5];
...
a[3] = a[2]
a[2] = 3

这样为了给新数据腾位置，要把已有的数据一个个移开。

数据的删除

对于一个拥有8个数据的数组，如果要删掉第3个元素，那么就要进行如下操作：

a[2] = a[3];
a[3] = a[4];
a[4] = a[5];
...
a[6] = a[7]

最后再删除掉多余的a[7]的空间即可。

操作数组的时间

关于操作数组的时间计算：假设数组中有n个数据，由于访问数组时使用的是随机访问（通过下标可以计算出内存地址），所以需要的运行时间仅仅为恒定的O（1）。

但是另一方面：想要向数组中添加新的数据是偶，需要把目标位置后面的数据一个个移开。所以要在数组头部添加数据，就需要O(n)的数据。同样的道理，如果想要在数组头部删掉一条数据，那么就要O(n)的时间。

链表和数组对比：
链表访问数据慢 添加快 删除快
数组访问快，添加慢，删除慢