数组扩容：为什么要新建数组而不是在原数组增加

前言： ：我最近在java面试的时候，会问一个很简单的问题，数组和链表的区别，候选人一般都能回答上来但是一旦问到数组的扩容，就会有人回答不上来，即使有人回答上来，再问到为什么数组扩容是新建数组并复制，而不是在原数组上操作，会有很多人回答不上来。

为什么数组需要扩容？

在介绍数组扩容细节之前，先了解一下为什么需要数组扩容。数组的长度在创建时就确定了，并且无法动态增加。

内存存储是连续的

为了理解为何需要创建新数组并复制数据，我们需要了解数组在内存中的存储方式。数组通常被存储为一块连续的内存区域，每个元素占据一段内存空间，从而实现高效的访问。这也限制了数组的长度，因为它无法在原地进行扩展。

为何创建新数组？

深入了解为什么在进行数组扩容时，通常会选择创建新数组并复制数据的方式。

1. 保持连续内存空间

数组的连续内存空间是高效访问的关键。如果要直接在原数组后增加元素，就需要确保后续内存空间是连续且可用的。然而，实际上，原数组之后的内存可能已被其他数据占用，无法保证连续的内存块。因为这个数组后面的内存地址可能存的其他东西，已经被其他对象的占用了。 举例：就像你要去占位子一样，要求占的位子要在一起，你就占了16个连续的位子，但是过了很久来了第17个人，你发现你的位子不够用了，但是为了便于你们在一起好找，你们的座位又必须连续，但是第17个位子上已经被隔壁的阿姨占了，那你咋办嘛，你不得不找一个大于16个的位子，且连续的位子，你就找了一个连续24个的位置，然后让你们这16个人都移动（复制)过去，因此，为了保持元素的连续性，必须新建数组。

3. 内存分配与碎片问题

直接在原数组上增加元素涉及重新分配内存。这可能导致内存碎片，即存在许多不连续小块空闲内存，影响性能。通过新建数组并一次性分配更大内存块，可减少碎片问题，提高程序效率。

时间复杂度与性能考虑

创建新数组并复制数据可能增加一些开销，但确保了操作的稳定性与性能。这种方式使内存管理更高效，同时保证了数据有序性和连续性，提供可靠数据存储解决方案。

与其他数据结构比较

与其他动态数据结构如链表相比，为何选择创建新数组？链表不需要连续内存，但访问元素较慢。而数组通过连续内存访问元素高效，但需要扩容时的数据复制。因此，根据实际需求，选择创建新数组是更合适的方案。

时间复杂度分析

在插入元素时，数组扩容涉及数据复制，时间复杂度为O(n)，其中n是元素数量。然而，扩容不是频繁操作，而是在倍数递增，使得均摊时间复杂度仍然较低。此设计在不同情况下保持了良好性能。

结论

其实说到底我就是想考察你知道数组在内存中的分配情况不，知道数组是需要一块连续的内存地址不，连续，连续，连续说三遍，当问到数组时首先想到的是内存地址是连续的，那么这种问题就难不到你...打完收工

---