Быстрая конкатенация списков

Question

В моей программе я очень много вычисляю конкатенации списков с отдельными элементами (т.е. я часто выполняю операции "concatenate(someList, <single-sized list containing one item>)").Как сделать эти конкатенации и выполнить итерацию по результирующим спискам как можно быстрее?

Я рассмотрел две реализации, но может быть и более быстрая:

• Наивная реализация конкатенации путем копирования всехэлементы к результирующему списку.Это приводит к O (n) затратам времени на итерацию, а также к O (n) производительности конкатенации.
• Перенос результата конкатенации в новый класс, ListsConcatenation (который также имеет интерфейс List), которыйсохраняет ссылки на все оригинальные списки и переадресовывает все вызовы на соответствующий.Это приведет к O (1) затратам времени на конкатенацию, но затраты времени на итерацию станут O (n * log (n)).

Answer 1

Обычно это требование появляется при заполнении списка слева направо. Если это так, то вопрос не в том, как вставить один элемент за O (1) время, а в том, как вставить n элементов за O ( n ), и в простом ответе это построить список задом наперед и полностью изменить его в конце.

Я, конечно, предполагаю некоторый функциональный язык, который обеспечивает неизменные типы данных. Если ваши типы данных изменчивы, вы можете просто запомнить последний узел и добавить новый элемент, назначив его указатель next.

Answer 2

Напишите связанный список, в котором есть указатель на конечный узел, а также указатель на заголовок.Чтобы объединить список в O (1), разыменуйте указатель «end» списка, к которому вы хотите перейти первым, и установите указатель «next» этого узла на начало списка, который вы хотите добавить.Не забудьте обновить конечную точку так, чтобы она указала на узел, на который ссылается указатель «конца» добавленного списка ...