Почему нет неизменного двойного связанного списка в коллекциях Scala?

Question

Глядя на этот вопрос, где спрашивающий интересуется первым и последним экземплярами некоторого элемента в List, кажется, что более эффективным решением было бы использование DoubleLinkedList, которое могло быпоиск назад от конца списка.Однако в API коллекций есть только одна реализация, и она изменчива.

Почему нет неизменной версии?

Answer 1

Потому что вам придется копировать весь список каждый раз, когда вы хотите внести изменения.С помощью обычного связанного списка вы можете, по крайней мере, добавить его в список, не копируя все.И если вы хотите копировать все при каждом изменении, вам не нужен связанный список для этого.Вы можете просто использовать неизменяемый массив.

Answer 2

Есть много препятствий для такой структуры, но одно очень актуально: двусвязный список не может быть постоянным.

Логика этого довольно проста: с любого узла в списке вы можете добраться долюбой другой узел.Итак, если бы я добавил элемент X в этот список DL и попытался использовать часть DL, я бы столкнулся с этим противоречием: из узла, указывающего на X, можно добраться до каждого элемента в части (DL), но, с помощьюсвойства двухсвязного списка, то есть из любого элемента части (DL) я могу добраться до узла, указывающего на X. Поскольку часть (DL) должна быть неизменной и частью DL, а так как DL не включает указание узладля X это просто не может быть.

Непостоянные неизменяемые структуры данных могут иметь некоторое применение, но, как правило, это плохо для большинства операций, поскольку их необходимо воссоздавать всякий раз, когда создается производная.

Теперь, есть незначительный вопрос создания взаимно ссылающихся строгих объектов, но это преодолимо.Можно использовать параметры по имени и ленивые значения, или можно сделать как Scala's List: фактически создать изменяемую коллекцию, а затем «заморозить» ее в неизменяемом состоянии (см. ListBuffer и его метод toList).

Answer 3

Поскольку логически невозможно создать взаимно (круговую) ссылочную структуру данных со строгой неизменностью.

Невозможно создать два узла, которые указывают друг на друга из-за простого приоритета экзистенциального упорядочения, в котором по крайней мереодин из узлов не будет существовать при создании другого.

Можно получить эту округлость с помощью уловок, включающих лень (что реализуется с помощью мутации), но тогда возникает реальный вопрос, почему вы захотите эту вещьна первом месте?

Answer 4

Как уже отмечали другие, не существует постоянной реализации двойного связанного списка. Вам понадобится какое-то дерево, чтобы приблизиться к желаемым характеристикам.

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

Смотри также:

• видео объяснение деревьев пальцев (разработчик деревьев пальцев в clojure.contrib)
• реализация пальчикового дерева в Scala (лично я не пользовался, но это самый популярный гугл-хит)

Answer 5

В дополнение к ответу @KimStebel я хотел бы добавить:
Если вы ищете структуру данных, подходящую для вопроса, который побудил вас задать этот вопрос, то вы можете взглянуть на Чрезвычайная сообразительность: функциональные структуры данных в Scala от @DanielSpiewak.