Caso de uso para LinkedList

Question

Esta publicación solo trata sobre scala.collection.mutable.LinkedList. Otras implementaciones no son el tema de este hilo.

Mi pregunta es: ¿cuál es el caso de uso de esta clase? Encuentro que tiene los problemas de ambos tipos de estructuras, mutables e inmutables, al mismo tiempo que produce los beneficios de ninguna. Lo digo porque:

• la API me parece como si se tratara de una API inmutable (filter, map, drop, take etc todo devolver una nueva LinkedList en lugar de hacer modificaciones en el lugar)
• toda la beneficios de la lista enlazada son inmutables, al menos, supongo, no está presente, es decir, el máximo intercambio entre las estructuras, ya que esos son todavía mutable (a través de var elem y var next.

Así que básicamente tenemos un tiempo de acceso lineal, lineal ap tiempo de espera, espacio lineal, etc. y nada que mostrar en complejidad del espacio o en la capacidad de razonar sobre el código (excepto tal vez el preajuste O (1) pero sigue siendo el caso con las listas inmutables).

¿No veo un beneficio importante de este tipo de estructura? Estoy buscando medidas objetivas y/o casos de uso aplicables a esta clase.

Answer 1

Diría que la razón es la complejidad: la clase de la lista enlazada le permite mantener una referencia a un nodo en el medio de la lista, y usar insert o update en ese nodo, en lugar de pasar por el encabezado lista.

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

En una aplicación en la que sé exactamente donde un cambio en alguna secuencia ocurrirá (myReference arriba), que cuesta mucho menos que modificar ese lugar de copiar todo lo que hasta ese lugar, como sería el caso de immutable.List (es decir, simplemente inserto un nuevo nodo después de myReference).

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

Un ejemplo de tal aplicación - un L-system, donde se expande partes de una cadena. Es mucho más económico insertar nuevos nodos en el lugar, que copiar la cadena completa cada vez que necesita expandirse.

Otra razón es completo - desde DoubleLinkedList y LinkedListLike comparten una gran cantidad de infraestructura común, proporcionando una clase extra LinkedList vino como un bajo costo para el tamaño de la biblioteca estándar.