Introduzione alla raccolta LinkedList

1. Storia diLinkedList

Java ha un'altra classe di raccolta Java ereditata dal linguaggio C++. Questa è la LinkedListclasse, che implementa una "lista collegata".

Esternamente, a LinkedListsembra essere uguale a un ArrayList. La LinkedListclasse ha tutti gli stessi metodi della ArrayListclasse. In linea di principio, puoi sempre usare a LinkedListinvece di an ArrayListe tutto funzionerà.

Allora perché abbiamo bisogno di un'altra classe di elenchi?

La risposta ha tutto a che fare con la struttura interna della LinkedListclasse. Invece di un array, utilizza un elenco doppiamente collegato . Spiegheremo di cosa si tratta un po' più tardi.

La LinkedListdiversa struttura interna della classe rende più veloce l'inserimento di elementi al centro dell'elenco.

Su Internet, puoi spesso trovare confronti tra ArrayListe LinkedListclassi:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Tutto sembra abbastanza chiaro: se hai bisogno di inserire spesso elementi nella lista, usa LinkedList; se raramente, usa ArrayList. Ma la realtà è un po' diversa.

2. Nessuno usaLinkedList

Nessuno usa LinkedList.

Anche l'autore della LinkedListclasse ha recentemente twittato: "Qualcuno lo usa davvero LinkedList? L'ho scritto e non lo uso mai".

Allora qual è il problema?

In primo luogo, la ArrayListclasse ha iniziato a essere in grado di inserire molto rapidamente gli elementi al centro dell'elenco. Quando si inserisce un elemento al centro dell'elenco, è necessario spostare tutti gli elementi dopo il punto di inserimento di 1 verso la fine dell'elenco. Questo richiedeva tempo.

Ma ora tutto è cambiato. Tutti gli elementi di un array sono vicini tra loro nello stesso blocco di memoria, quindi l'operazione di spostamento degli elementi viene eseguita da un comando di basso livello molto veloce: .System.arraycopy()

Inoltre, i processori odierni dispongono di una cache di grandi dimensioni che di solito può contenere l'intero array, il che consente di spostare gli elementi dell'array all'interno della cache anziché in memoria. Un milione di elementi possono essere facilmente spostati in un solo millisecondo.

In secondo luogo, la LinkedListclasse può inserire rapidamente elementi se li inserisci utilizzando un iteratore. Se usi un iteratore per passare attraverso a LinkedListe inserire costantemente nuovi elementi (o rimuovere quelli esistenti), l'operazione è super veloce.

Se aggiungi semplicemente elementi a un LinkedListoggetto all'interno di un ciclo, ogni operazione di inserimento veloce è accompagnata da una lenta operazione di "ottenere elemento".

La realtà è molto più vicina a questa:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Perché ottenere un elemento da LinkedListun'operazione così lenta?

Puoi rispondere a questa domanda dopo aver familiarizzato un po' con come LinkedListè strutturato.

3. Com'è LinkedListstrutturato

LinkedListha una struttura interna diversa da ArrayList. Non ha un array interno per la memorizzazione di elementi. Invece, utilizza una struttura di dati chiamata lista doppiamente inchiostrata .

Ogni elemento di una lista doppiamente collegata memorizza un riferimento all'elemento precedente e all'elemento successivo. Questo è un po' come una fila in un negozio, dove ogni persona ricorda la persona in piedi di fronte a loro così come la persona in piedi dietro di loro.

Ecco come appare un elenco di questo tipo in memoria:

La testa e la coda (celle con sfondo grigio) sono le variabili firste last, che memorizzano i riferimenti agli Nodeoggetti.

Nel mezzo, hai una catena di Nodeoggetti (oggetti, non variabili). Ciascuno di essi è composto da tre campi:

• prev— memorizza un riferimento (collegamento) all'oggetto precedente Node(celle con sfondo giallo).
• value— memorizza il valore di questo elemento dell'elenco (celle con sfondo verde).
• next— memorizza un riferimento (collegamento) all'oggetto successivo Node(celle con sfondo blu)

Il secondo oggetto (indirizzo F24) è il successivo ( next) per il primo oggetto e il precedente ( prev) per il terzo oggetto. Il campo giallo del terzo oggetto contiene l'indirizzo F24 e il campo blu del primo oggetto contiene l'indirizzo F24.

Le frecce del primo e del terzo oggetto puntano allo stesso secondo oggetto. Quindi sarebbe più corretto disegnare le frecce in questo modo.

4. Inserire un elemento in un elenco collegato

Per aggiungere qualcuno alla fila in questo modo, devi solo ottenere il permesso di due persone in piedi una accanto all'altra. La prima persona ricorda il nuovo arrivato come "la persona dietro di me", e la seconda persona lo ricorda come "la persona davanti a me".

Tutto quello che devi fare è cambiare i riferimenti dei due oggetti vicini:

Abbiamo aggiunto un nuovo elemento alla nostra lista modificando i riferimenti del secondo e del terzo oggetto. Il nuovo oggetto è il successivo per il vecchio secondo oggetto e il precedente per il vecchio terzo oggetto. E, naturalmente, il nuovo oggetto stesso deve memorizzare i riferimenti corretti: il suo oggetto precedente è il vecchio secondo oggetto e il suo oggetto successivo è il vecchio terzo oggetto.

Rimuovere un elemento è ancora più semplice: se vogliamo rimuovere, diciamo, il centesimo oggetto dall'elenco, dobbiamo solo cambiare il campo nextper il 99esimo oggetto in modo che punti al 101esimo oggetto e cambiare il prevcampo per il 101esimo oggetto in modo che punti al 99esimo. Questo è tutto.

Ma ottenere il centesimo oggetto non è così facile.

5. Rimuovere un elemento da un elenco

Per ottenere il centesimo elemento di un elenco collegato, devi:

Ottieni il primo oggetto: lo fai usando la firstvariabile nell'oggetto LinkedList. Il nextcampo del primo oggetto memorizza un riferimento al secondo oggetto. Ecco come otteniamo il secondo oggetto. Il secondo oggetto ha un riferimento al terzo e così via.

Se dobbiamo ottenere un riferimento al centesimo oggetto, dobbiamo spostarci in sequenza attraverso tutti gli oggetti dal primo al centesimo. E se abbiamo bisogno del milionesimo elemento in un elenco, dobbiamo iterare oltre un milione di oggetti uno dopo l'altro!

E se questi oggetti sono stati aggiunti all'elenco in momenti diversi, si troveranno in parti diverse della memoria ed è improbabile che finiscano contemporaneamente nella cache del processore. Ciò significa che l'iterazione sugli elementi di un elenco collegato non è solo lenta, ma molto lenta.

Questo è ciò con cui abbiamo a che fare.

Allora perché ti stiamo insegnando come LinkedListfunziona questo rallentamento?

Bene, durante i colloqui di lavoro ti verrà chiesto in cosa LinkedListdifferisce daArrayList . Decisamente.