Рассматривая этот вопрос, в котором вопросник заинтересован в первом и последнем экземплярах какого-либо элемента в List, кажется, более эффективное решение будет использовать DoubleLinkedList, который мог бы искать назад с конца списка. Однако в API коллекции есть только одна реализация, и она изменена.
Почему нет неизменяемой версии?
Потому что вам придется копировать весь список каждый раз, когда вы хотите внести изменения. С нормальным связанным списком вы можете, по крайней мере, добавить к списку, не копируя все. И если вы хотите скопировать все при каждом изменении, для этого вам не нужен связанный список. Вы можете просто использовать неизменяемый массив.
Существует много препятствий для такой структуры, но одно очень важно: двусвязный список не может быть постоянным.
Логика этого довольно проста: из любого node в списке вы можете связаться с любым другим node. Итак, если я добавил элемент X в этот список DL и попытался использовать часть DL, мне бы пришлось столкнуться с этим противоречием: из node, указывающего на X, можно достичь каждого элемента в части (DL), но, по свойствам дважды связанного списка, то есть из любого элемента части (DL) я могу достичь node, указывающего на X. Поскольку часть (DL) должна быть неизменной и частью DL, а так как DL не включите node, указывающий на X, который просто не может быть.
Непрерывные неизменяемые структуры данных могут иметь некоторые виды использования, но в большинстве случаев они плохо подходят для большинства операций, поскольку их необходимо воссоздавать всякий раз, когда производная создается.
Теперь возникает незначительная проблема создания взаимных ссылок на строгие объекты, но это преодолимо. Можно использовать параметры имени и ленивые суммы, или можно сделать как Scala List: на самом деле создать изменчивую коллекцию, а затем "заморозить" ее в неизменяемом состоянии (см. ListBuffer и метод toList).
Поскольку логически невозможно создать взаимную (круговую) ссылочную структуру данных со строгой неизменностью.
Вы не можете создать два узла, которые указывают друг на друга из-за простого экзистенциального приоритета заказа, поскольку по крайней мере один из узлов не будет существовать, когда другой будет создан.
Можно получить эту круглость с помощью трюков, связанных с лени (которая реализована с мутацией), но тогда возникает реальный вопрос, почему вы хотели бы эту вещь в первую очередь?
В качестве дополнения к ответу @KimStebel я хотел бы добавить:
Если вы ищете структуру данных, подходящую для вопроса, который побудил вас задавать этот вопрос, вы можете взглянуть на Extreme Cleverness: Структуры функциональных данных в Scala @DanielSpiewak.
Как отмечали другие, не существует постоянной реализации двойного списка. Вам понадобится какое-то дерево, чтобы приблизиться к характеристикам, которые вы хотите.
В частности, вы можете посмотреть деревья пальцев, которые обеспечивают O (1) доступ к спереди и сзади, амортизация O (1) вставки спереди и сзади и установка O (log n) в другом месте. (Это в отличие от большинства других обычно используемых деревьев, у которых есть O (log n) доступ и вставка везде.)
См. также: