我的意识是我可以将新项添加到列表的末尾,然后将它们旋转到位.这是一个选择！
另一种选择,当我知道我提前添加了多少项时,就是在后面添加许多项目,移动现有项目,然后在我为自己制作的洞中就地执行算法.否定的是我必须在列表的末尾添加一些默认值,然后才覆盖它们.
我对这些选项进行了快速分析,并得出结论,第二种选择更有效.我的理由是,使用第一个选项的轮换将导致就地交换(需要临时).我唯一担心的第二个选项是我创建了一堆默认值,这些默认值会被丢弃.大多数情况下,这些默认值将为null或mem-filled值类型.
但是,我希望有其他熟悉算法的人告诉我哪种方法会更快.或者,也许我没有考虑过更有效的解决方案.
对于除阵列末尾之外的任何位置的大量插入或删除,数组效率不高.考虑使用不同的数据结构(例如在其他答案之一中建议的数据结构)是否可能更有效.在不知道你想要解决的问题的情况下,几乎不可能建议数据结构(对于所有问题都没有一个解决方案).话虽如此…第二种选择绝对是两者的更好选择.一个更好的选择(避免默认值问题)：简单地将789复制到最后并用456覆盖中间789.因此唯一的中间步骤是0123789789.
但是,您的默认值问题(通常)不是一个大问题：
>在Java中,对于一个,你不能(据我所知)为不是0或空填充的数组分配内存. C STL容器也强制执行这个我相信(但不是C本身).
>与任何中等大小的类相比,指针的大小是最小的(因此将其分配给默认值也花费最少的时间)(在Java和C#中,一切都是指针,在C中你可以使用指针(类似于boost :: shared_ptr)或指针向量优先于直指针)(N / A到基元,它们起始很小,因此通常也不是一个大问题).
我还建议在开始插入数组末尾之前强制重新分配到指定的大小(Java的ArrayList :: ensureCapacity或C的vector :: reserve).如果您不知道 – 变长度数组实现往往有一个比size()返回的内部数组大或可访问的内部数组(为了防止在插入或删除值时不断重新分配内存).
另请注意,复制部分数组比使用for循环手动执行更有效的方法(例如Java的System.arraycopy).