Предположим, у вас есть упорядоченный набор, который вы также хотите изменить, добавив и удалив элементы. Кроме того, вам нужна возможность сохранить ссылку на элемент таким образом, чтобы позже вы могли получить предыдущий или следующий элемент. Например, список дел или набор абзацев в книге.
Во-первых, мы должны отметить, что если вы хотите сохранить ссылки на объекты вне самого набора, вы, скорее всего, в конечном итоге будете хранить указатели в массиве, а не сами объекты. В противном случае вы не сможете вставить в массив - если объекты встроены в массив, они будут перемещаться во время вставки, и любые указатели на них станут недействительными. То же самое верно для индексов массива.
Ваша первая проблема, как вы сами отметили, заключается в том, что связанный с вставкой список позволяет вставлять в O (1), но массив обычно требует O (n). Эта проблема может быть частично преодолена - можно создать структуру данных, которая предоставляет массивоподобный обычный порядок доступа, где чтение и запись в худшем случае являются логарифмическими.
Ваша вторая и более серьезная проблема заключается в том, что заданным элементом для нахождения следующего элемента является O (n). Если набор не был изменен, вы могли бы сохранить индекс элемента в качестве ссылки вместо указателя, таким образом делая find-next операцией O (1), но, как и все, что у вас есть, это указатель на сам объект и никак определить его текущий индекс в массиве, кроме как путем сканирования всего «массива». Это непреодолимая проблема для массивов - даже если вы можете оптимизировать вставки, вы ничего не можете сделать для оптимизации операции поиска следующего типа.