什么是顺序表？

顺序表是一种线性数据结构，其中的元素在内存中是连续存储的。每个元素都有一个唯一的索引值或下标，可以通过这个索引值快速访问任何位置的元素。这使得顺序表在需要频繁随机访问元素的场景下具有高效的性能，例如根据索引值获取数组中的元素或修改特定位置的元素值。由于顺序表的这种随机访问特性，它在处理需要频繁读取或修改数据的应用中非常有用，如查找表、缓存等。

顺序表的一大优点是内存紧凑。相邻元素之间没有额外的指针或链接开销，而是按照逻辑顺序依次存储在内存中。当访问一个元素时，由于局部性原理，相邻的元素通常也会被缓存到CPU高速缓存中，从而减少了内存访问的开销。此外，顺序表内存紧凑，元素之间没有内存碎片，提高了内存利用率和访问效率。这使得顺序表在需要存储大量数据且内存空间受限的场景下具有优势，如嵌入式系统、物联网设备等。

虽然顺序表在随机访问和内存利用率方面具有优势，但它在频繁插入和删除操作时表现不佳。由于顺序表的有序性质，在插入或删除元素时需要移动后续元素来保持顺序，特别是在插入或删除位置靠前的情况下，需要移动的元素更多。因此，顺序表的插入和删除操作的时间复杂度可能接近 O（n），其中 n 为顺序表的元素个数。这使得顺序表不适合频繁插入和删除操作的场景，如日志记录、消息队列等。在这些场景下，链式存储结构如链表可能是更好的选择。

顺序表按顺序存储数据元素，不需要为存储指针或链接而浪费额外空间，因此存储密集，利用率高。

顺序表中数据元素存储连续，可以通过元素位置直接存取，存取速度快。对于有序表，还可以利用二分查找等高效算法快速查找数据。

顺序表的插入、删除等基本操作算法相对简单，易于实现和理解。

顺序表在创建时需要预先分配一块连续的存储空间，一旦分配后，存储空间就固定了，不能动态扩充。

当顺序表存储空间已满时，插入新元素需要移动大量元素以腾出空间，效率低下。删除元素后也需要移动后续元素以释放空间。

如果存储空间不足，需要重新分配更大的存储空间，并将原有数据复制过去，可能导致存储空间分散。

在创建顺序表时，预先分配一个较大的存储空间，当存储空间不够时，需要重新分配更大的存储空间，并将原有数据复制到新的存储空间中。这种方式浪费空间，且复制数据效率低下。

初始时分配一个较小的存储空间，当存储空间不够时，重新分配一个更大的存储空间，并将原有数据复制到新的存储空间中。这种方式可以节省空间，但复制数据效率仍然较低。

初始时分配一个较小的存储空间，当存储空间不够时，重新分配一个更大的存储空间，并将原有数据复制到新的存储空间的前半部分，后半部分作为新的存储空间。这种方式可以节省空间，且复制数据效率较高。

初始时分配一个较小的存储空间，当存储空间不够时，重新分配一个原来存储空间大小的两倍的新存储空间，并将原有数据复制到新的存储空间中。这种方式可以最大限度地减少复制数据的次数，提高效率。