极简教程：数据结构与算法（二）
这是一套关于数据结构与算法的系列文章，值得你持续关注
2020-4-29
数组篇
我尽量用 最少的文字，最少的代码。来讲明白数据结构与算法。
1. 数组是“线性数据结构”，同样的数据结构还有“链表”，“栈”，“队列”
2. 与之对立的概念是 “非线性表” 。二叉树，堆，图等。因为这些数据结构的方向不只是“前”，“后”。
3. 数组的原理：在内存地址中找到开始的位置，划定一片连续的内存地址。只存储相同类型的数据，这样方便寻址。
4. 因为是连续的内存地址，所以才能实现随机访问元素
寻址算法
a[i] = 数组开始的位置 + i * 固定大小
5. 数组复杂度分析
| 动作 | 复杂度 |
|---|---|
| array 增 | O(n) |
| array 删 | O(n) |
| array 改 | O(1) |
| array 查：根据下标 | O(1) |
| array 查：循环查 | O(logn) |
6. 数组，插入优化
如果不需要排序，那么不用每次都对插入位置后的元素做位移。可以尝试替换法
7. 删除优化
不用每次删除都 给元素移位，可以先标记被删除的元素。等删除的元素积累一段之后一并删除。
8. 大部分语言都有对数组做扩张，比如 javascript 中 Array。其实 javascript 中没有严格意义上的数组。
9. 开发时一般都用 arrayList，如果初始化时给设定一个长度，那么可以起到优化的作用。减少一部分 O(n) 操作
10. 在数据长度固定的情况下，建议使用数组。这样执行效率更高。
如有不足，欢迎补充。