Lista collegata in Java

Ciao! Tutte le lezioni recenti sono state dedicate allo studio dell'elenco ArrayList . Questa struttura dati è molto comoda e consente di risolvere molti problemi. Tuttavia, Java ha molte altre strutture dati. Perché? Innanzitutto perché la gamma dei compiti esistenti è molto ampia e per compiti diversi sono più efficaci strutture dati diverse . Oggi faremo conoscenza con una nuova struttura: una lista doppiamente collegata LinkedList . Scopriamo come funziona, perché si chiama doppiamente connesso e in cosa differisce da ArrayList . In una LinkedList, gli elementi sono in realtà i collegamenti di una catena. Ogni elemento, oltre ai dati che memorizza, ha un collegamento all'elemento precedente e successivo . Questi collegamenti ti consentono di passare da un elemento all'altro. È creato così:

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Conclusione:

[Hello World! My name is Earl, I love Java, I live in Moscow]

Ecco come apparirà la struttura della nostra lista: Vediamo come viene aggiunto un nuovo elemento. Questo viene fatto utilizzando il file add().

earlBio.add(str2);

Al momento di questa riga di codice, la nostra lista è composta da un elemento: la stringa str1. Vediamo cosa succede dopo nell'immagine: Di conseguenza str2, e str1si connette tramite i collegamenti memorizzati in essi nexte previous: Ora dovresti comprendere l'idea principale di una lista doppiamente collegata. Gli elementi LinkedListcostituiscono un unico elenco proprio grazie a questa catena di maglie. Non c'è alcun array all'interno LinkedList, come in ArrayList, o qualcosa di simile. Tutto il lavoro con ArrayList (in generale) si riduce a lavorare con l'array interno. Tutto il lavoro LinkedListsi riduce alla modifica dei collegamenti. Ciò si vede molto chiaramente aggiungendo un elemento al centro dell'elenco:

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Come puoi vedere, il metodo sovraccaricato add()ti consente di specificare un indice specifico per il nuovo elemento. In questo caso, vogliamo aggiungere una linea str2tra str1e str3. Questo è ciò che accadrà all'interno: E come risultato della modifica dei collegamenti interni, l'elemento str2viene aggiunto con successo all'elenco: Ora tutti e 3 gli elementi sono collegati. Dal primo elemento lungo la catena nextsi può passare all'ultimo e viceversa. Abbiamo più o meno capito l'inserimento, ma per quanto riguarda la cancellazione degli elementi? Il principio di funzionamento è lo stesso. Ridefiniamo semplicemente i collegamenti dei due elementi “ai lati” di quello da eliminare:

public class Main {

   public static void main(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 Moscow");

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

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

Questo è ciò che accadrà se eliminiamo l'elemento con indice 1 (è al centro dell'elenco): Dopo aver ridefinito i collegamenti, otteniamo il risultato desiderato: a differenza dell'eliminazione, ArrayListnon ci sono spostamenti di elementi dell'array e simili. Ridefiniamo semplicemente i riferimenti degli elementi str1e str3. Ora puntano l'uno verso l'altro e l'oggetto str2è “abbandonato” da questa catena di collegamenti e non fa più parte dell'elenco.

Panoramica dei metodi

Ha LinkedListmolte somiglianze con ArrayListi metodi. Ad esempio, metodi come add(), remove(), indexOf(), clear(), contains()(è l'elemento contenuto nella lista), set()(inserimento di un elemento con sostituzione) size()sono presenti in entrambe le classi. Sebbene (come abbiamo scoperto nell'esempio add()e remove()) molti di essi funzionino in modo diverso internamente, ma alla fine fanno la stessa cosa. Tuttavia, LinkedListha metodi separati per lavorare con l'inizio e la fine dell'elenco, che non sono presenti in ArrayList:

• addFirst(), addLast(): 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 + '\'' +
               '}';
   }
}

Conclusione:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

Di conseguenza, la Ford finì in cima alla lista e la Fiat alla fine.

• peekFirst(), peekLast(): restituisce il primo/ultimo elemento della lista. Ritorna nullse 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());
}

Conclusione:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): restituisce il primo/ultimo elemento della lista e lo rimuove dalla lista . Ritorna nullse 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 left on the list?");
   System.out.println(cars);
}

Conclusione:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): restituisce un array di elementi della lista

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));
}

Conclusione:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Ora sappiamo come funziona LinkedListe in cosa differisce da ArrayList. Quali sono i vantaggi del suo utilizzo LinkedList? Prima di tutto, lavorando con la metà della lista . Inserire ed eliminare nel mezzo LinkedListè molto più semplice che in ArrayList. Ridefiniamo semplicemente i collegamenti degli elementi vicini e l'elemento non necessario “cade” dalla catena di collegamenti. Mentre in ArrayListnoi:

• controlla se c'è abbastanza spazio (durante l'inserimento)
• se non è sufficiente, crea un nuovo array e copia lì i dati (quando incolli)
• eliminare/inserire un elemento e spostare tutti gli altri elementi a destra/sinistra (a seconda del tipo di operazione). Inoltre, la complessità di questo processo dipende in gran parte dalla dimensione dell'elenco. Una cosa è copiare/spostare 10 elementi, un'altra è fare lo stesso con un milione di elementi.

Cioè, se nel tuo programma le operazioni di inserimento/eliminazione avvengono più spesso con la metà dell'elenco, LinkedListdovrebbe 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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Conclusione:

Время работы для LinkedList (в мorсекундах) = 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 to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Conclusione:

Время работы для ArrayList (в миллисекундах) = 181

All'improvviso! Sembrerebbe che stiamo eseguendo un'operazione che LinkedListavrebbe dovuto essere molto più efficiente: inserire 100 elementi al centro della lista. E la nostra lista è enorme: 5.000.000 di elementi: ArrayListdovevamo spostare un paio di milioni di elementi ogni volta che li inserivamo! Qual è il motivo della sua vittoria? Innanzitutto, si accede a un elemento in ArrayListun periodo di tempo fisso. Quando indichi:

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

quindi nel caso di ArrayList[2_000_000] questo è un indirizzo specifico in memoria, perché ha un array al suo interno. Mentre l' LinkedListarray no. Cercherà l'elemento numero 2_000_000 lungo la catena di collegamenti. Per lui non si tratta di un indirizzo nella memoria, ma di un collegamento ancora da raggiungere:

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, ad ogni inserimento (cancellazione) al centro dell'elenco, ArrayListconosce già l'indirizzo esatto in memoria a cui dovrebbe accedere, ma LinkedListdeve comunque “scoprirlo” nel posto giusto. In secondo luogo , la questione è nella struttura ArrayListstessa dell'oggetto. L'espansione dell'array interno, la copia di tutti gli elementi e lo spostamento degli elementi vengono eseguiti da una speciale funzione interna - System.arrayCopy(). Funziona molto rapidamente perché è appositamente ottimizzato per questo lavoro. Ma in situazioni in cui non è necessario "calpestare" l'indice desiderato, LinkedListsi mostra davvero meglio. Ad esempio, se l'inserimento avviene 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("Result in milliseconds: " + msDelay);
       return msDelay;

   }

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

}

Conclusione:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

Un risultato completamente diverso! Ci sono voluti più di 43 secondi per inserire un milione di elementi all'inizio dell'elenco ArrayList, mentre LinkedListè stato completato in 0,1 secondi! Era proprio il fatto che in questa situazione LinkedListnon dovevamo “correre” ogni volta attraverso la catena di collegamenti fino al centro dell'elenco. Ha subito trovato l'indice richiesto all'inizio dell'elenco, e lì la differenza nei principi di funzionamento era già dalla sua parte :) In effetti, la discussione “ ArrayListcontro LinkedList” è molto diffusa, e per ora non la approfondiremo livello. La cosa principale che devi ricordare:

• Non tutti i vantaggi di una particolare collezione “su carta” funzioneranno nella realtà (lo abbiamo visto utilizzando l'esempio al centro dell'elenco)
• Non bisogna andare agli estremi nella scelta di una collezione (“ ArrayListè sempre più veloce, usala e non sbagli. LinkedListNessuno la usa da molto tempo”).

Anche se LinkedListlo dice anche il creatore Joshua Bloch :) Tuttavia, questo punto di vista è lungi dall'essere corretto al 100% e ne siamo convinti. Nel nostro esempio precedente LinkedListha funzionato 400 (!) volte più velocemente. Un'altra cosa è che ci sono davvero poche situazioni in cui LinkedListsarebbe la scelta migliore. Ma esistono e al momento giusto LinkedListpossono aiutarti seriamente. Non dimenticare ciò di cui abbiamo parlato all'inizio della lezione: strutture dati diverse sono più efficaci per compiti diversi. È impossibile dire con il 100% di sicurezza quale struttura dei dati sarà migliore finché non saranno note tutte le condizioni del problema. Più tardi saprai di più su queste collezioni e sarà più facile fare una scelta. Ma l'opzione più semplice ed efficace è sempre la stessa: testarli entrambi sui dati reali del tuo programma. Quindi potrai vedere con i tuoi occhi i risultati di entrambe le liste e sicuramente non sbaglierai :)