Caso di utilizzo per LinkedList

Question

Questo post tratta solo di scala.collection.mutable.LinkedList. Altre implementazioni non sono l'argomento di questa discussione.

La mia domanda è: qual è il caso d'uso di questa classe? Trovo che abbia i problemi di entrambi i tipi di strutture mutevoli e immutabili mentre produce i benefici di nessuno. Lo dico perché:

• l'API guarda a me come se si trattasse di un API immutabili (filter, map, drop, take ecc tutti restituire un nuovo LinkedList invece di fare modifiche in-place)
• tutto il benefici della lista collegata immutabili sono, almeno credo, non presente, vale a dire la massima condivisione tra strutture, dal momento che questi sono ancora mutevoli (attraverso var elem e var next.

Quindi fondamentalmente abbiamo un tempo di accesso lineare, ap lineari tempo pendolare, spazio lineare ecc. e nulla da mostrare per esso nella complessità dello spazio o nella capacità di ragionare sul codice (tranne forse il prefisso O (1) ma è ancora il caso con elenchi immutabili).

Non riesco a vedere un vantaggio importante di questo tipo di struttura? Sto cercando misure oggettive e/o casi d'uso applicabili a questa classe.

Answer 1

Direi che il motivo è la complessità: la classe elenco collegato consente di mantenere un riferimento a un nodo nel mezzo dell'elenco e utilizzare insert o update in quel nodo, invece di passare attraverso il capo del elenco.

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

In un'applicazione in cui so esattamente dove un cambiamento di qualche sequenza accadrà (myReference sopra), costa molto meno di modificare quella posizione che copiare tutto ciò fino a quella posizione, come sarebbe il caso con immutable.List (cioè inserisco appena un nuovo nodo dopo myReference).

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

Un esempio di tale applicazione - un L-system dove si espande parti di una stringa. È molto più economico inserire nuovi nodi sul posto, piuttosto che copiare l'intera stringa ogni volta che deve essere espansa.

Un altro motivo è la completezza - dal DoubleLinkedList e LinkedListLike condividono un sacco di un'infrastruttura comune, fornendo un ulteriore LinkedList classe è venuto come un basso costo per la dimensione libreria standard.