我的算法适用于动态增长的列表（连续内存，如 C++ 向量、Java ArrayList 或 C# 列表）。直到最近，这些算法才会将新值插入到列表的中间。当然，这通常是一个非常缓慢的操作。每次添加一个项目时，它之后的所有项目都需要移动到更高的索引。对每个算法都这样做几次，事情变得非常缓慢。
我意识到我可以将新项目添加到列表的末尾，然后稍后将它们旋转到位。这是一种选择！
另一种选择是，当我提前知道要添加多少项目时，将那么多项目添加到后面，移动现有项目，然后在我为自己制作的孔中就地执行算法。不利的是，我必须在列表末尾添加一些默认值，然后覆盖它们。
我对这些选项进行了快速分析，并得出结论认为第二个选项更有效。我的理由是第一个选项的轮换将导致就地交换（需要临时）。我对第二个选项的唯一担心是我正在创建一堆被丢弃的默认值。大多数情况下，这些默认值将是 null 或 mem 填充的值类型。
但是，我希望其他熟悉算法的人告诉我哪种方法更快。或者，也许还有一个我没有考虑过的更有效的解决方案。
数组对于在数组末尾以外的任何地方进行大量插入或删除操作效率不高。考虑使用不同的数据结构（例如在其他答案之一中建议的数据结构）是否可能更有效。在不知道您要解决的问题的情况下，几乎不可能提出一种数据结构（没有一种解决方案可以解决所有问题）。话虽如此...
第二种选择绝对是两者中更好的选择。一个更好的选择（避免默认值问题）：只需复制789到末尾并789用456. 所以唯一的中间步骤是0123789789.
但是，您的默认值问题（通常）不是一个大问题：
在 Java 中，就我所知，您甚至不能为非 0 或空值填充的数组分配内存。我相信 C++ STL 容器也会强制执行这一点（但不是 C++ 本身）。
与任何中等大小的类相比，指针的大小是最小的（因此将其分配给默认值也需要最少的时间）（在 Java 和 C# 中，一切都是指针，在 C++ 中，您可以使用指针（类似于boost::shared_ptr指针向量优于直接指针）（对原语不适用，它们一开始很小，所以通常也不是什么大问题）。
我还建议在开始插入数组末尾（JavaArrayList::ensureCapacity或 C++ vector::reserve）之前强制重新分配到指定的大小。如果您不知道 - 可变长度数组实现往往有一个内部数组，该数组大于size()返回值或可访问值（以防止在插入或删除值时不断重新分配内存）。
另请注意，与使用 for 循环（例如 Java's System.arraycopy）手动复制数组部分相比，复制数组部分的方法更有效。
您可能需要考虑将列表的表示形式从使用动态数组更改为使用其他结构。这里有两个选项可让您有效地实施这些操作：
顺序统计树是一种经过修改的二叉树，它支持在 O(log n) 时间内的任何地方进行插入和选择，以及在 O(log n) 时间内进行查找。由于指针的开销和额外的簿记，这将大大增加您的内存使用量，但应该会大大加快插入速度。但是，它会稍微减慢查找速度。
如果您总是提前知道插入点，您可以考虑切换到链表而不是数组，并保留一个指向将发生插入的链表单元格的指针。但是，这会减慢对 O(n) 的随机访问，这可能是您设置中的一个问题。
或者，如果您总是知道插入将发生在哪里，您可以考虑将您的数组表示为两个堆栈 - 一个堆栈将数组的内容保存在插入点的左侧，另一个将元素的（反向）保存在插入点。这使得插入速度很快，如果你有正确类型的堆栈实现可以保持快速随机访问。
希望这可以帮助！
HashMaps 和 Linked Lists 是为您遇到的问题而设计的。给定带有编号项目的索引数据结构，在中间插入项目的困难需要对列表中的每个项目重新编号。
您需要一个经过优化的数据结构，以使插入具有恒定的O(1)复杂性。HashMaps 旨在使插入和删除操作闪电般快速，无论数据集大小如何。
我不能通过描述来假装 HashMap 主题公正。这是一个很好的介绍：http ://en.wikipedia.org/wiki/Hash_table