什么是数组？

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

线性表：数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小

试着用swift根据动态数组的思路实现一下，对自己的收货也非常大。

动态数组的接口设计

动态数组的实现

add添加元素

往数组中第k个位置添加元素，后面第k~n个元素都需要顺序往后移动，才能保持内存连续性

最好情况：在数组末尾添加，不需要移动任何元素，时间复杂度为O(1)

最坏情况：在数组头部添加，从头开始所有元素往后移动一位，时间复杂度为O(n)

remove删除元素

删除数组中第k个位置元素，后面第k~n个元素都需要顺序往前移动，才能保持内存连续性

最好情况：删除数组末尾元素，不需要移动任何元素，时间复杂度为O(1)

最坏情况：删除数组头部元素，后面所有元素往前移动一位，时间复杂度为O(n)

动态扩容

说白了，就是当前这块存储空间满了，需要重新分配一块连续的内存，然后把所有的元素拷贝过去。

数组优化-环形缓冲

我们来对数组做一个优化

添加一个first指针，一直指向数组的首元素

以插入为例，分为头部插入，尾部插入和中间插入，最主要的是realIndex的计算

尾部插入：直接插入最后面就行，时间复杂度为O(1)

头部插入：插入到原来first往前的一个位置，时间复杂度为O(1)，此时first指向新插入的位置

中间插入：与中间位置进行对比，只移动一半的元素即可，时间复杂度会降低一半