数组
数组是将 相同类型 的元素存储于 连续内存空间 的数据结构，其长度不可变；
访问/修改-索引 O(1)
插入元素 O(n)
删除元素 O(n)
合并数组 O(m+n)
数组的特殊性
-
JS 数组可以动态的改变容量，根据元素的数量来扩容、收缩；
-
JS 数组可以表现的像栈一样，为数组提供了 push 和 pop 方法；也可以表现的像队列一样，使用 shift 和 push 方法，可以像使用队列一样使用数组；
-
JS 数组可以使用 for-each 遍历，可以排序，可以倒置；
-
JS 提供了很多操作数组的方法，比如 Array.concat、Array.join、Array.slice；
快数组
快数组是一种 线性 的存储方式；
新创建的空数组，默认的存储方式是快数组，快数组长度是可变的，可以根据元素的增加和删除来动态调整存储空间大小，内部是通过扩容和收缩机制实现；
扩容后的新容量 = 旧容量的 1.5 倍 + 16- 需要根据
length + 1 == old_length进行判断，true 则将空出的空间收缩二分之一，false 则全部收缩掉；
慢数组
慢数组是一种 字典 的内存形式；
不用开辟大块连续的存储空间，节省了内存，但是由于需要维护这样一个 HashTable 其效率会比快数组低；
快数组 VS 慢数组
存储方式方面：快数组内存中是连续的，慢数组在内存中是零散分配的;
内存使用方面：由于快数组内存是连续的，可能需要开辟一大块供其使用，其中还可能有很多空洞，是比较费内存的；慢数组不会有空洞的情况，且都是零散的内存，比较节省内存空间；
遍历效率方面：快数组由于是空间连续的，遍历速度很快，而慢数组每次都要寻找 key 的位置，遍历效率会差一些；
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
算法基础🔮 空间复杂度
上一篇
评论
