Elenco collegato Java

CIAO! Tutte le ultime lezioni sono state dedicate ad ArrayList . Questa struttura dati è molto comoda e utile. Può gestire molte attività. Ma Java ha molte altre strutture dati. Perché? Soprattutto perché la gamma di compiti è enorme e le strutture dati più efficienti sono diverse per compiti diversi. Oggi incontreremo una nuova struttura: Java LinkedList , una lista doppiamente collegata. Vediamo come è organizzato, perché si chiama double-linked, come si differenzia da ArrayList . Gli elementi in una Java LinkedList sono in realtà collegamenti in una singola catena. Oltre ai dati, ogni elemento memorizza i riferimenti agli elementi precedenti e successivi. Questi riferimenti consentono di passare da un elemento all'altro. Ecco come crearne uno:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Uscita: [Ciao mondo! Mi chiamo Earl, amo Java, vivo in Canada] Ecco come si presenta la nostra lista: Vediamo come aggiungere un nuovo elemento. Questo viene fatto usando il metodo add() .

earlBio.add(str2);

Nel punto del codice, la nostra lista è composta da un elemento: la stringa str1 . Vediamo cosa succede dopo nell'immagine: Di conseguenza, str2 e str1 vengono collegati tramite i collegamenti successivo e precedente memorizzati in questi nodi dell'elenco: Ora dovresti capire l'idea principale di un elenco doppiamente collegato. Questa catena di collegamenti è esattamente ciò che rende gli elementi LinkedList un unico elenco. A differenza di ArrayList , LinkedList non ha un array o qualcosa di simile a un array all'interno. Qualsiasi (beh, la maggior parte) lavoro con ArrayList si riduce a lavorare con l'array interno. Qualsiasi lavoro con Java LinkedListsi riduce a cambiare link. Questo può essere visto molto chiaramente aggiungendo un elemento al centro dell'elenco:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Come puoi vedere, il metodo add() in overload ti consente di specificare un indice specifico per un nuovo elemento. In questo caso, vogliamo aggiungere String str2 tra str1 e str3 . Questo è ciò che accadrà internamente: Dopo aver modificato i collegamenti interni, str2 è stato aggiunto con successo all'elenco: Ora tutti e 3 gli elementi sono collegati. Puoi spostarti tramite il collegamento successivo dal primo elemento della catena all'ultimo e viceversa. Quindi, siamo abbastanza a nostro agio con l'inserimento, ma per quanto riguarda la rimozione di elementi? Il principio è esattamente lo stesso. Aggiorniamo solo i collegamenti nei due elementi "a sinistra ea destra" dell'elemento rimosso:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

Ecco cosa succede se eliminiamo l'elemento con indice 1 (è al centro dell'elenco): Dopo aver aggiornato i collegamenti, otteniamo il risultato desiderato: A differenza dell'operazione di rimozione in ArrayList , qui non è necessario spostare gli elementi dell'array o fare niente del genere. Aggiorniamo solo i collegamenti per str1 e str3 . Ora puntano l'uno verso l'altro e str2 ha " abbandonato " la catena di collegamenti e non fa più parte dell'elenco.

Panoramica dei metodi

LinkedList ha molti metodi in comune con ArrayList . Ad esempio, entrambe le classi hanno metodi come add() , remove() , indexOf() , clear() , contains() (indica se un elemento è nell'elenco), set() (sostituisce un elemento esistente) e dimensione() . Sebbene molti di essi funzionino internamente in modo diverso (come abbiamo riscontrato con add() e remove() ), il risultato finale è lo stesso. Tuttavia, LinkedList ha metodi separati per lavorare con l'inizio e la fine dell'elenco, che ArrayList non ha:

• addFirst() , addLast() : Questi metodi per aggiungere un elemento all'inizio/fine dell'elenco

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Output: [Auto{model='Ferrari 360 Spider'}, Auto{model='Bugatti Veyron'}, Auto{model='Lamborghini Diablo'}] [Auto{model='Ford Mondeo'}, Auto{model=' Ferrari 360 Spider'}, Auto{model='Bugatti Veyron'}, Auto{model='Lamborghini Diablo'}, Auto{model='Fiat Ducato'}] Finiamo con "Ford" in cima alla lista , e "Fiat" alla fine.

• peekFirst() , peekLast() : i metodi restituiscono il primo/ultimo elemento nell'elenco. Restituiscono null se l'elenco è vuoto.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Output: Auto{model='Ferrari 360 Spider'} Auto{model='Lamborghini Diablo'}

• pollFirst() , pollLast() : questi metodi restituiscono il primo/ultimo elemento nell'elenco e lo rimuovono dall'elenco. Restituiscono null se l'elenco è vuoto

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

Output: Auto{model='Ferrari 360 Spider'} Auto{model='Lamborghini Diablo'} Cosa resta della lista? [Auto{model='Bugatti Veyron'}]

• toArray() : questo metodo restituisce un array contenente gli elementi dell'elenco

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Output: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Ora sappiamo come funziona LinkedList e in che modo la sua organizzazione differisce da ArrayList . Quali sono i vantaggi dell'utilizzo di LinkedList ? Soprattutto, traiamo vantaggio quando lavoriamo nel mezzo della lista. Le operazioni di inserimento e rimozione nel mezzo di un LinkedList sono molto più semplici che in un ArrayList . Aggiorniamo semplicemente i collegamenti degli elementi vicini e l'elemento indesiderato "abbandona" la catena di collegamenti. Ma in un ArrayList , dobbiamo

• controlla se c'è abbastanza spazio (durante l'inserimento)
• in caso contrario, creiamo un nuovo array e copiamo i dati lì (durante l'inserimento)
• togliamo/inseriamo l'elemento, e spostiamo a destra/sinistra tutti gli altri elementi (a seconda del tipo di operazione). E la complessità di questo processo dipende fortemente dalla dimensione dell'elenco. Una cosa è copiare/spostare 10 elementi e un'altra è fare lo stesso con un milione di elementi.

In altre parole, se le operazioni di inserimento/rimozione nel mezzo dell'elenco sono più comuni nel tuo programma, LinkedList dovrebbe essere più veloce di ArrayList .

In teoria

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Output: tempo impiegato da LinkedList (in millisecondi) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Output: Tempo impiegato da ArrayList (in millisecondi) = 181 Era inaspettato! Abbiamo eseguito un'operazione in cui LinkedList dovrebbe essere molto più efficiente: inserire 100 elementi nel mezzo di un elenco. E la nostra lista è enorme: 5.000.000 di elementi. ArrayList ha dovuto spostare un paio di milioni di elementi ad ogni inserimento! Come ha vinto? Innanzitutto, il tempo necessario ad ArrayList per accedere agli elementi è fisso (costante). Quando scrivi

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

quindi ArrayList [2_000_000] è un indirizzo di memoria specifico (dopo tutto, l'elenco ha un array interno). Ma un LinkedList non ha un array. Cercherà l'elemento numero 2_000_000 lungo la catena di maglie. Per LinkedList, questo non è un indirizzo di memoria, ma un collegamento che deve ancora essere raggiunto: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… Di conseguenza, durante ogni inserimento (rimozione) al centro della lista , ArrayList conosce già l'esatto indirizzo di memoria a cui accedere, ma LinkedList deve ancora "arrivarci". In secondo luogo, c'è la struttura dell'ArrayListsi. Una funzione interna speciale ( System.arrayCopy() ) espande l'array interno e copia e sposta tutti gli elementi. È molto veloce, perché è ottimizzato per questo lavoro specifico. Ma quando non devi "arrivare a" un particolare indice, LinkedList è il vincitore. Supponiamo di inserire all'inizio dell'elenco. Proviamo a inserire un milione di elementi lì:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Output: Il risultato in millisecondi: 43448 Il risultato in millisecondi: 107 Ora otteniamo un risultato completamente diverso! ArrayList ha impiegato più di 43 secondi per inserire un milione di elementi all'inizio dell'elenco, mentre LinkedList è riuscito a farlo in 0,1 secondi! LinkedList ha beneficiato qui, perché non doveva scorrere ogni volta la catena di collegamenti fino al centro dell'elenco. Trova immediatamente l'indice necessario all'inizio dell'elenco, quindi il diverso algoritmo è già un vantaggio. :) In effetti, la discussione " ArrayList contro LinkedList " è molto diffusa e non ci immergeremo in profondità al livello attuale. La cosa principale che devi ricordare è questa:

• Non tutti i vantaggi teorici di una particolare raccolta funzionano sempre nella realtà (lo abbiamo visto con l'esempio che coinvolge il centro dell'elenco)
• Non adottare una posizione estrema quando si tratta di scegliere una raccolta (" ArrayList è sempre più veloce. Usalo e non puoi sbagliare. Nessuno usa LinkedList da molto tempo").

Anche se anche l'autore di LinkedList , Joshua Bloch, afferma che è così. :) Tuttavia, questa prospettiva è tutt'altro che corretta al 100% e ne siamo convinti. Nel nostro esempio precedente, LinkedList era 400 (!) volte più veloce. Un'altra cosa è che ci sono davvero poche situazioni in cui LinkedList è la scelta migliore. Ma esistono, e al momento giusto LinkedListpuò ricompensarti profumatamente. Non dimenticare ciò che abbiamo detto all'inizio della lezione: le strutture dati più efficienti sono diverse per compiti diversi. È impossibile essere sicuri al 100% quale struttura di dati sarà la migliore finché non si conoscono tutte le condizioni del proprio compito. Ne saprai di più su queste collezioni in seguito, il che faciliterà la scelta. Ma l'opzione più semplice ed efficace è sempre la stessa: prova entrambe sui dati effettivamente utilizzati nel tuo programma. Quindi sarai in grado di vedere di persona come si comportano entrambi i tipi di elenchi e sicuramente non sbaglierai. :) Per rafforzare ciò che hai imparato, ti suggeriamo di guardare una lezione video dal nostro corso Java