第2章 数组

2.1 数组的基础知识

数组是一种简单的数据结构，是由相同类型的元素组成的数据集合，并且占据一块连续的内存并按照顺序存储数据。面试中出现的数组通常是一维或二维的。最简单的数组是一维的，其中元素的存取以单一的下标表示。二维数组对应于数学上矩阵的概念，其中元素的存取需要行和列两个下标。

创建数组时需要先指定数组的容量大小，然后根据容量大小分配内存。即使只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此，数组的空间效率不一定很高，可能会有空闲的区域没有得到充分利用。

为了解决数组空间效率不高的问题，人们又设计实现了动态数组，如Java中的ArrayList。动态数组既保留了数组时间效率高的特性，又能够在数组中不断添加新的元素。为了避免浪费，可以先为数组分配较小的内存空间，然后在需要的时候在数组中添加新的数据。当数据的数目增加导致数组的容量不足时，需要重新分配一块更大的空间（通常新的容量是之前容量的2倍），把之前的数据复制到新的数组中，再把之前的内存释放。这样能减少内存的浪费，但每次扩充数组容量时都有大量的额外操作，这对时间性能有负面影响。