Я понимаю изменчивую индексированную коллекцию, которая использует массив для хранения своих элементов (например, List<T> в .NET или ArrayList в Java) имеет амортизируется O (1) время вставки в конце коллекции. Но тогда всегда есть одна надоедливая вставка на критических стыках, где коллекция только что достигла своей емкости, а следующая вставка требует полной копии всех элементов во внутреннем массиве к новому (предположительно вдвое больше).
Общей ошибкой (по моему мнению) является переход со связанным списком, чтобы "исправить" эту проблему; но я считаю, что накладные расходы на выделение node для каждого элемента могут быть довольно расточительными и на самом деле будут затмевать преимущество гарантированной установки O (1) в том редком случае, что вставка массива является дорогостоящей, каждая другая вставка массива значительно дешевле (и быстрее).
То, что я думал, может иметь смысл - это гибридный подход, состоящий из связанного списка массивов, где каждый раз, когда текущий массив "head" достигает своей емкости, в связанный список добавляется новый массив, вдвое больший. Тогда никакой копии не потребуется, поскольку связанный список все равно будет иметь исходный массив. По существу это похоже на мой подход к List<T> или ArrayList, за исключением того, что, когда бы вы ранее не понесли затраты на копирование всех элементов внутреннего массива, здесь вы берете на себя только расходы на выделение нового массив плюс одна вставка node.
Конечно, это усложняло бы другие функции, если бы они были желательными (например, вставка/удаление в/из середины коллекции); но, как я уже сказал в названии, я действительно ищу только коллекцию add-only (и итерацию).
Существуют ли какие-либо структуры данных, идеально подходящие для этой цели? Или вы можете сами подумать об этом?
