Случай использования для LinkedList

В этом сообщении обсуждается scala.collection.mutable.LinkedList. Другие реализации не являются темой этого потока.

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

  • API выглядит так, как если бы это был неизменяемый API (filter, map, drop, take и т.д., все возвращают новый LinkedList вместо выполнения изменений на месте)
  • все преимущества неизменяемого связанного списка, по крайней мере, я думаю, нет, т.е. максимальный общий доступ между структурами, поскольку они все еще изменяемы (через var elem и var next.

Итак, мы имеем линейное время доступа, линейное время добавления, линейное пространство и т.д., и ничего не показывать для него в сложности пространства или в способности рассуждать о коде (за исключением, может быть, O (1) preend, но это все еще имеет место с неизменяемые списки).

Неужели я не вижу важного преимущества такого типа структуры? Я ищу объективные меры и/или варианты использования, применимые к этому классу.

Ответы

Ответ 1

Я бы сказал, что причина кроется в сложности - класс связанного списка позволяет удерживать ссылку на node в середине списка и использовать insert или update в этом node, вместо этого прохождение главы списка.

[] --> [] --> ... --> [] --> ... --> [] --|
^                     ^
head                  myReference

В приложении, где я точно знаю, где будет происходить изменение в какой-либо последовательности (myReference выше), гораздо дешевле изменить это местоположение, чем копировать все до этого местоположения, как это было бы в случае с immutable.List ( т.е. я просто вставляю новый node после myReference).

                             myNewNode
                             v
[] --> [] --> ... --> [] --> [] ---> ... --> [] --|
^                     ^
head                  myReference

Пример такого приложения - L-system, где вы расширяете части строки. Намного дешевле вставлять новые узлы на место, чем копировать всю строку каждый раз, когда ее нужно развернуть.

Еще одна причина - полнота - поскольку DoubleLinkedList и LinkedListLike разделяют много общей инфраструктуры, предоставление дополнительного класса LinkedList объясняется низкой стоимостью стандартного размера библиотеки.