E se gli oggetti fossero collegati tra loro?

Passiamo alla prossima struttura dati, piuttosto interessante: la LinkedList.

Esaminiamo la sintassi e lo schema di funzionamento di LinkedList:

Come puoi vedere, la sintassi è assolutamente identica a quella per dichiarare un ArrayList. In generale, qualsiasi lista può essere dichiarata in questo modo.

Ma la parte interessante inizia quando cerchiamo di capire come funziona una LinkedList.

Com'è strutturato LinkedList?

All'interno, LinkedList funziona con i Nodes. Un Node è un oggetto che viene memorizzato all'interno di LinkedList. È implementato all'interno di LinkedList in questo modo:

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Analizziamo di cosa consiste questa classe. Per prima cosa, è necessario rispondere alla domanda principale che sorge: Cosa significa <E>? Questo è un generico.

In termini semplici, qui si lascia un segnaposto per il tipo di dato che verrà specificato durante l'inizializzazione. Si utilizza questo segnaposto nel codice, che verrà poi sostituito dal tipo di dato specificato dall'utente.

Questo può essere paragonato al sovraccarico.

Vediamo come funziona:

Quindi, invece di sovraccaricare questo metodo per ogni tipo di dato, si utilizza un generico in cui si inserisce il tipo di dato con cui il metodo lavorerà. La lettera E verrà semplicemente sostituita con il tipo di dato richiesto. Nel nostro caso, è Integer.

Successivamente, prestiamo attenzione al campo item E. Questo rappresenta il valore dell'oggetto che verrà memorizzato in questo Node. Quindi, se creiamo una lista come {0, 1, 2, 3}, il primo nodo memorizzerà l'elemento 0, il secondo nodo memorizzerà l'elemento 1 e così via.

Poi, si notano i riferimenti ad altri oggetti Node: Node<E> next e Node<E> prev. Questa è la caratteristica principale di una lista collegata. In un Node, è presente un riferimento al Node successivo e a quello precedente. Questo è il modo in cui si itera attraverso la lista. Esaminiamo più da vicino l'iterazione in una LinkedList.

Osservando uno schema di questo tipo, si può concludere che l'iterazione attraverso questa lista funziona in modo diverso.

In ArrayList<>(), internamente, il programma utilizza un array che raddoppia la sua dimensione quando il numero di elementi raggiunge i 3/4 della sua capacità.

In una LinkedList<>(), non è necessario ricreare un array perché non esiste un array in una LinkedList. Invece, quando si aggiunge un nuovo elemento, viene creato un nuovo oggetto Node e collegato tramite riferimenti all'ultimo elemento precedente.

Può sembrare e suonare un po' complicato, ma come programmatore non sarà necessario configurare tutto questo.

I metodi di LinkedList sono gli stessi di ArrayList perché entrambi ereditano dall'interfaccia List, che definisce i metodi che tutti i suoi discendenti devono implementare.

Complessità algoritmica

Nel framework Collection, esistono diverse strutture dati, ognuna con la propria complessità algoritmica.

La complessità algoritmica viene indicata utilizzando la notazione big O (ad esempio, O(n), O(n^2)), dove "O" sta per "big O" e indica un limite superiore alla crescita del tempo di esecuzione in funzione della dimensione dell'input.

Ecco i principali tipi di complessità algoritmica:

O(1) (tempo costante): la complessità temporale non dipende dalla dimensione dei dati di input. Ad esempio, accesso a un elemento in un array tramite indice;
O(log n) (tempo logaritmico): la complessità temporale cresce in modo logaritmico rispetto alla dimensione dei dati di input. Esempio: ricerca binaria in un array ordinato;
O(n) (tempo lineare): la complessità temporale cresce linearmente con la dimensione dei dati di input. Esempio: iterazione su tutti gli elementi in un ArrayList;
O(n^2) (tempo quadratico): la complessità temporale è proporzionale al quadrato della dimensione dei dati di input. Esempio: bubble sort.

Queste sono categorie di base, ma esistono molte altre tipologie di complessità algoritmica, come O(n log n), O(2^n), O(n!) e altre, che caratterizzano algoritmi più complessi. La scelta di un algoritmo efficiente, considerando la sua complessità, è un aspetto cruciale nello sviluppo software.

Ora, torniamo alle strutture dati in Java. Ogni struttura dati presenta la propria complessità temporale algoritmica a seconda dell'operazione da eseguire. Esaminiamo la tabella:

Si può notare che la ricerca di un elemento tramite indice in ArrayList ha complessità costante poiché si accede direttamente all'indice nell'array.

Invece, in LinkedList, la ricerca tramite indice richiede molto più tempo perché è necessario percorrere tutti i nodi per trovare l'oggetto desiderato tramite indice.

D'altra parte, osservando l'inserimento di un elemento, LinkedList presenta complessità costante, mentre ArrayList ha complessità lineare. Questo accade perché per inserire un elemento in una LinkedList basta modificare i collegamenti tra i nodi, inserendo il nuovo elemento tra essi. Per ArrayList, invece, è necessario ricreare l'array con il nuovo elemento, il che comporta la copia dell'array precedente e l'inserimento dell'elemento, richiedendo molto più tempo.

Vediamo un esempio:

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

Abbiamo creato due liste: una è un ArrayList e l'altra è una LinkedList. Successivamente, le abbiamo popolate con 1.000.000 di numeri interi casuali. Le liste hanno lo stesso contenuto, ciascuna contenente un milione di numeri da 1 a 100.

Successivamente, abbiamo misurato il tempo necessario per aggiungere un elemento all'indice millesimo con valore 50. Abbiamo utilizzato il metodo System.nanoTime() per misurare il tempo, che mostra l'ora corrente in nanosecondi. Poi, per ciascuna lista, abbiamo sottratto il tempo di inizio da quello di fine, determinando così quanto tempo è stato impiegato per aggiungere un elemento al centro della lista.

Si può notare che la LinkedList ha avuto prestazioni significativamente più rapide, come evidenziato nella tabella. LinkedList presenta una complessità algoritmica costante, mentre ArrayList ha una complessità lineare.

Ecco perché sono necessari diversi tipi di liste. Se il tuo progetto gestisce grandi quantità di dati dove l'ottimizzazione è fondamentale, vale la pena considerare quale tipo di lista permetterà al programma di essere più veloce in determinati casi. Ma ti svelo un segreto: io uso quasi sempre ArrayList.

SinglyLinkedList

Esiste un'altra struttura dati non divulgata chiamata SinglyLinkedList. Come suggerisce il nome, questa struttura dati utilizza l'iterazione in una sola direzione. Mentre la classe LinkedList di Node ha i campi: item, next e prev, la classe SinglyLinkedList di Node ha solo 2 campi: item e next.

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

Questa struttura dati viene utilizzata in strutture come le mappe, dove l'iterazione è necessaria in una sola direzione. Studieremo le mappe, in particolare HashMap, nelle sezioni successive.

Nel prossimo capitolo, scriveremo un'implementazione di SinglyLinkedList per comprendere meglio il funzionamento di questa interessante struttura dati.

1. Quale struttura dati offre prestazioni migliori se si desidera trovare un elemento tramite indice?

2. Quale struttura dati offre prestazioni migliori durante un'operazione di eliminazione?

3. In che modo la classe `Node` partecipa al funzionamento di `LinkedList`?

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 5

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Scorri per mostrare il menu

E se gli oggetti fossero collegati tra loro?

Passiamo alla prossima struttura dati, piuttosto interessante: la LinkedList.

Esaminiamo la sintassi e lo schema di funzionamento di LinkedList:

Come puoi vedere, la sintassi è assolutamente identica a quella per dichiarare un ArrayList. In generale, qualsiasi lista può essere dichiarata in questo modo.

Ma la parte interessante inizia quando cerchiamo di capire come funziona una LinkedList.

Com'è strutturato LinkedList?

All'interno, LinkedList funziona con i Nodes. Un Node è un oggetto che viene memorizzato all'interno di LinkedList. È implementato all'interno di LinkedList in questo modo:

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Analizziamo di cosa consiste questa classe. Per prima cosa, è necessario rispondere alla domanda principale che sorge: Cosa significa <E>? Questo è un generico.

Questo può essere paragonato al sovraccarico.

Vediamo come funziona:

Osservando uno schema di questo tipo, si può concludere che l'iterazione attraverso questa lista funziona in modo diverso.

In ArrayList<>(), internamente, il programma utilizza un array che raddoppia la sua dimensione quando il numero di elementi raggiunge i 3/4 della sua capacità.

Può sembrare e suonare un po' complicato, ma come programmatore non sarà necessario configurare tutto questo.

I metodi di LinkedList sono gli stessi di ArrayList perché entrambi ereditano dall'interfaccia List, che definisce i metodi che tutti i suoi discendenti devono implementare.

Complessità algoritmica

Nel framework Collection, esistono diverse strutture dati, ognuna con la propria complessità algoritmica.

Ecco i principali tipi di complessità algoritmica:

O(1) (tempo costante): la complessità temporale non dipende dalla dimensione dei dati di input. Ad esempio, accesso a un elemento in un array tramite indice;
O(log n) (tempo logaritmico): la complessità temporale cresce in modo logaritmico rispetto alla dimensione dei dati di input. Esempio: ricerca binaria in un array ordinato;
O(n) (tempo lineare): la complessità temporale cresce linearmente con la dimensione dei dati di input. Esempio: iterazione su tutti gli elementi in un ArrayList;
O(n^2) (tempo quadratico): la complessità temporale è proporzionale al quadrato della dimensione dei dati di input. Esempio: bubble sort.

Ora, torniamo alle strutture dati in Java. Ogni struttura dati presenta la propria complessità temporale algoritmica a seconda dell'operazione da eseguire. Esaminiamo la tabella:

Si può notare che la ricerca di un elemento tramite indice in ArrayList ha complessità costante poiché si accede direttamente all'indice nell'array.

Invece, in LinkedList, la ricerca tramite indice richiede molto più tempo perché è necessario percorrere tutti i nodi per trovare l'oggetto desiderato tramite indice.

Vediamo un esempio:

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

SinglyLinkedList

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

Nel prossimo capitolo, scriveremo un'implementazione di SinglyLinkedList per comprendere meglio il funzionamento di questa interessante struttura dati.

1. Quale struttura dati offre prestazioni migliori se si desidera trovare un elemento tramite indice?

2. Quale struttura dati offre prestazioni migliori durante un'operazione di eliminazione?

3. In che modo la classe `Node` partecipa al funzionamento di `LinkedList`?

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 5

Lista Collegata in Java

E se gli oggetti fossero collegati tra loro?

Com'è strutturato LinkedList?

Complessità algoritmica

SinglyLinkedList

1. Quale struttura dati offre prestazioni migliori se si desidera trovare un elemento tramite indice?

2. Quale struttura dati offre prestazioni migliori durante un'operazione di eliminazione?

3. In che modo la classe `Node` partecipa al funzionamento di `LinkedList`?

Lista Collegata in Java

E se gli oggetti fossero collegati tra loro?

Com'è strutturato LinkedList?

Complessità algoritmica

SinglyLinkedList

1. Quale struttura dati offre prestazioni migliori se si desidera trovare un elemento tramite indice?

2. Quale struttura dati offre prestazioni migliori durante un'operazione di eliminazione?

3. In che modo la classe `Node` partecipa al funzionamento di `LinkedList`?

Lista Collegata in Java

E se gli oggetti fossero collegati tra loro?

Com'è strutturato LinkedList?

Complessità algoritmica

SinglyLinkedList

1. Quale struttura dati offre prestazioni migliori se si desidera trovare un elemento tramite indice?

2. Quale struttura dati offre prestazioni migliori durante un'operazione di eliminazione?

3. In che modo la classe Node partecipa al funzionamento di LinkedList?

Lista Collegata in Java

E se gli oggetti fossero collegati tra loro?

Com'è strutturato LinkedList?

Complessità algoritmica

SinglyLinkedList

1. Quale struttura dati offre prestazioni migliori se si desidera trovare un elemento tramite indice?

2. Quale struttura dati offre prestazioni migliori durante un'operazione di eliminazione?

3. In che modo la classe Node partecipa al funzionamento di LinkedList?

3. In che modo la classe `Node` partecipa al funzionamento di `LinkedList`?

3. In che modo la classe `Node` partecipa al funzionamento di `LinkedList`?