Scala, какая структура данных наиболее эффективна для моих предполагаемых операций?

Question

Я запускаю функцию динамического программирования, где я переношу список строк в течение всего процесса.

Со временем я добавляю новые строки в конец этого списка, и иногда я могу удалить последний элемент. Сейчас я использую mutable ListBuffer, делая += для добавлений и .trimEnd(1) для удаления.

После выполнения моей процедуры динамического программирования мне необходимо эффективно иметь доступ к каждому элементу этого списка/последовательности/etc и по порядку (первый элемент, который я вставил, будет первым, а последний элемент, который я вставил, будет быть последним доступным).

Я также попробовал ArrayBuffers, но они оба кажутся слишком медленными. Я пытаюсь ускорить этот процесс, и мне интересно, использую ли я структуру данных, которая имеет операции O (n), когда может быть что-то, у которого есть O (1) операторы времени для того, что мне нужно.

Answer 1

Простой одиночный список предоставит O (1) для добавления/удаления частей того, что вы описываете. В худшем случае, если вам нужно перевернуть список в конце перед обработкой, это будет операция O (n), заплаченная один раз.

Обратите внимание, что если вы спуститесь по этой дороге, на этапе накопления «первый» и «последний» будет отменен (вы добавите предметы и опустите первый элемент, получив хвост списка).