数据结构与算法-数组

几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。

数组通常情况下用于存储一系列同一种数据类型的值，但在 JavaScript 里，数组中可以保存不同类型的值。

数组

JS对数组的封装很完善，不过在其它语言中，如Java中，并不会直接使用数组，而是对数组做一层封装ArrayList，因为Java中数组结构相对来说比较底层。

• 常见语言的数组不能存放不同的数据类型，因此所有在封装时通常存放在数组中的是Object类型，这样就可以存放不同的类型。但如果此时想要限制存放类型，如只能存放Person、Animal，可以使用泛型来对类型进行限制。

• 常见语言的数组容量不会自动改变，需要扩容操作。如创建一个数组时，申请的空间是存放5个元素，那么就不能再存放第6个元素。此时，如果需要存放第6个，那么就需要申请一个更大的数组即创建一个新数组，如申请10个；然后将原来的数组元素拷贝过来，这个新的数组被占据了一半，剩下的一半就可以用来存储第6个、第7个元素... 那如果存放满之后呢，就需要再申请一个新数组，以此往复。Java中的ArrayList就是这样来扩容的。由此可看出，数组的扩容是一个比较耗时的操作。

• 常见语言的数组进行中间插入和删除操作性能比较低。当在数组中间插入一个元素时，需要将数组在插入位置后的元素向后移动，然后再插入新的元素；删除时，将指定元素删除后，删除位置后的元素需要向前移动。所以数组中间插入和删除元素也比较耗时。如下图中，在数组首位插入一个元素，那么其它元素都要后移，然后插入新元素。

• 基于元素内容查找，效率比较低，但是通过数组的下标获取元素，或修改指定下表元素，效率是非常高的。