线性表 - 数组
数组由于是紧凑连续存储，可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。
- 但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容， 要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)。
- 数组中间进行插入或删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
C++ 数组 array 和vector 间的联系和区别
相同点
- 都和数组类似，都可以使用标准数组的表示方法来访问每个元素；array和vector都针对下标运算符[]进行了重载
- 三者的存储都是使用的连续内存，都可以进行随机访问；在array和vector的底层存储结构均使用数组。
不同点
| 技术 | 数组 | array | vector |
|---|---|---|---|
| 容量 | 定长容量，定义后的空间是固定的，不能进行改变 | 定长容量，定义后的空间是固定的，不能进行改变 | 变长容器，提供了可以动态插入和删除元素的机制，可以根据数据的 插入删除重新构建容器容量（1.5-2倍），即可以进行再加或减。 |
| 元素数量 | 定义的时候必须定义数组的元素个数 | 定义的时候必须定义数组的元素个数 | 不需要预先定义数量 |
| 数据访问 | 只能通过下标访问，更容易引发访问错误 | 提供了更好的数据访问机制，即可以使用front()和back()以及at()（at()可以避免a[-1]访问越界的问题）访问方式，访问更加安全 | 提供了更好的数据访问机制，即可以使用front()和back()以及at()（at()可以避免a[-1]访问越界的问题）访问方式，访问更加安全 |
| 内容交换 | 只能通过遍历的方式，逐个元素交换的方式使用 | 两个容器对象的内容交换，即swap的机制 | 两个容器对象的内容交换，即swap的机制 |
| 容量获取 | 只能通过sizeof()/strlen()以及遍历计数来获取大小和是否为空 | 提供了size()和Empty()的获取机制 | 提供了size()和Empty()的获取机制 |
| 遍历机制 | 开箱即用的中台前端/设计解决方案 | 提供了更好的遍历机制，即有正向迭代器和反向迭代器两种 | 提供了更好的遍历机制，即有正向迭代器和反向迭代器两种 |
| 安全性 | 不安全的 | 比较安全的（有效的避免越界等问题） | 比较安全的（有效的避免越界等问题） |
| 内存使用 | 用new[ ]/malloc申请的空间，必须用对应的delete[ ]和free来释放内存 | 在声明周期完成后，会自动地释放其所占用的内存 | 在声明周期完成后，会自动地释放其所占用的内存 |
| 元素添加 | 数组一经定义就不允许添加新元素；若需要则要充许分配新的内存空间，再将员数组的元素赋值到新的内存空间。 | 数组一经定义就不允许添加新元素；若需要则要充许分配新的内存空间，再将员数组的元素赋值到新的内存空间。 | vector有一系列的函数操作，非常方便使用 |
数组与链表对比
数组由于是紧凑连续存储，可以随机访问， 通过索引快速找到对应元素，而且相对节约存储空间。
但正因为连续存储， 内存空间必须一次性分配够， 所以说数组如果要扩容， 需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)。
数组中间进行插入或删除，每次必须搬移后面的所有数据以保持连续， 时间复杂度 O(N)。
链表因为元素不连续， 而是靠指针指向下一个元素的位置， 所以不存在数组的扩容问题。
- 根据某个元素的前驱和后驱， 操作指针即可删除该元素或插入新元素， 时间复杂度 O(1)。
- 存储空间不连续，无法根据索引算出对应元素的地址，索引不能随机访问；
- 每个元素必须存储指向前后元素位置的指针， 会消耗相对更多的储存空间。