如何实现一个变长数组？

  1. 支持索引与随机访问
  2. 分配多长的连续空间？
  3. 空间不够用了怎么办？
  4. 空间剩余很多如何回收？

    参考实现： C++：vertor Java：ArrayList Python：list

简易的实现方法

  • 初始是一个空数组，分配常数空间，记录实际长度（size）和容量（capacity）
  • Push back ： 若空间不够，重新申请2倍大小的连续空间，拷贝到新空间，释放旧空间
  • Pop back：若空间利用率（size/capacity）不到 25% ，释放一半的空间
  • 均摊时间复杂度为设计变长数组（resizable array） - 图1
  • 在空数组中连续插入n个元素，总插入、拷贝次数为 设计变长数组（resizable array） - 图2
  • 一次扩容到下一次释放，至少需要再删除 设计变长数组（resizable array） - 图3 次

    思考：若释放空间的阈值设定为50%，会发生什么情况？ 当释放空间的阈值设定为50%，当插入元素超过一半时，Push back扩容至原来的2倍，但是随之回收垃圾，使之低于一半的容量，此时就会缩容。频繁的扩缩容是很影响性能的！