数组是不是不适合频繁的添加删除操作？

Question

今天网上看到一句话，大致意思是

如果要频繁的进行删除，添加操作，就用JSON。因为数组不适合频繁的添加删除操作。
如果要频繁的取数据就用 数组。

我的理解是这样的，因为平凡的对数组进行添加删除操作，会改变数组的长度，不利于遍历。尤其是在这种经常改变数组长度情况下，用forEach 就可能会出现问题。

1、不知道这样想对不对哦，只是从实践结果上去理解这个问题，感觉好粗浅，有没有什么更深层次的，原理上的原因啊？
2、还有，对于频繁的数组添加删除操作要用JSON,应该怎么用啊？把数组转换成JSON?然后呢？还是说我的理解有问题？
一脸懵逼啊~~~~

Answer 1

数组的定义是一段连续的内存空间，
根据下标查找是直接寻址，根据首节点地址跟每个节点的空间大小给算出来的，所以查找快。
同时数组的大小是固定的，不能变长，c/c++的变长其实是重新申请一块内存，把旧数组给复制过去了。
本质上数组append和replace是一样的，都是替换。对于insert，因为需要把数组指定位置后面的节点后移，所以涉及多步操作。
对于链表，因为本身就不是连续的空间，所以可以直接插入，但是查找需要便利，虽然有多种树形结构来提高查找复杂度，但是都有副作用，比如普通链表利于遍历，不利于指定查找，hash利于指定查找不利于遍历。
综上，数组利于查找，链表利于插入是对的。
但是此数组非彼数组，
php，js等脚本语言的数组并非传统意义的数组，他们都是用链表模拟的，
所以要看具体语言实现。

Answer 2

大部分情况下，我们不需要考虑两者之间的差异。

数组内部是哈希表。添加删除操作的复杂度接近 O(1)。

参考：http://blog.jobbole.com/102494/

Answer 3

你所谓的删除/添加操作具体是什么？是你手动删除/添加下标元素，还是使用splice之类的方法。
你需要把这些描述清楚。

Answer 4

因为在数组里面如果删除的不是第一个元素或者最后一个元素，那么需要将数组里的元素移位，因为数组在内存里是一块连续的单元。比如一个数组长度为10，我删除了下标为2的元素，那么需要把下标为3到下标为9的元素往前移一位，同时将length减去一（当时这些解释器帮你做了）。插入同理。所以数组不适合频繁插入和删除。但是取数组里的元素是非常快的，因为内存地址是连续的，比如我要取下标为6的元素，只需要将数组第一个元素的地址加上前面6个元素所占用的内存地址就行了。

对应的插入和删除比较快的数据结构是链表，而不是json，json本身也是用数组实现的（JAVA是这样，JS没去翻V8源码不清楚，不过数据结构这东西感觉语言的差别不大）。至于链表为什么插入和删除快，建议题主去百度吧，这些都是书上的东西

Answer 5

如 @tiyee 所说，作为一种基本的数据结构，数组通常是连续分析的空间，直接通过索引存取数据速度非常快，因为只需要算内存地址就找到了。但这确实是静态语言，像 C/C++/C#/Java 之类的实现。动态语言，解释性的语言，其实现就不一定是用数组了，可能是用链表，也可能是用哈希表，或者其它。

JavaScript 中的实现我没去研究过，估计 ECMAScript-262 里也不会对实现的具体的要求。不过 JavaScript 引擎众多，实现也有可能各不相同。我个人认为，对 JavaScript 的网页端来说，性能其实不那么重要，一般一个网页上多用个几十毫秒，少用个几十毫秒是感觉不出来的。不过对于服务端来说，性能累积效应就需要考虑了，但也不是说觉得哪里性能不好就去优化，而是要先感觉，再实测，确实是性能瓶颈，再去优化。

说起 JSON，我觉得可能是指的 JavaScript 对象字面量，就是 {} 这种。JSON 作为一种数据结构，有严格的规范，不这 JavaScript 对象字面量完全兼容 JSON，所以经常容易搞混淆。不过不管是字面量对象还是实体化出来的对象，在 JavaScript 里都可以模拟数组，被称为伪数组——jQuery 就是使用伪数组的大户。因为据称对象是通过 Hash 表来实现的，所以这种伪数组是通过哈希检索，检索效率高，但是对于增加删除等操作也涉及到改变索引号的问题，所以效率不见得就比数组高。

Answer 6

数组的删除操作复杂度并不是 O(1)，（猜测）是 O(n)

Answer 7

我觉得应该没什么太大关系的