Scorri per mostrare il menu

E se gli oggetti fossero collegati tra loro?

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

Analisi della sintassi e dello schema operativo di LinkedList:

Come si può notare, la sintassi è assolutamente identica a quella della dichiarazione di un ArrayList. In generale, qualsiasi lista può essere dichiarata in questo modo.

La parte interessante inizia quando si cerca di comprendere il funzionamento di LinkedList.

Com'è strutturato LinkedList?

Internamente, 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 è composta questa classe. Per prima cosa, bisogna 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.

Successivamente, 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. Analizziamo 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 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.

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

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

Complessità algoritmica

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

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

D'altra parte, se si considera l'inserimento di un elemento, LinkedList presenta complessità costante, mentre ArrayList ha complessità lineare. Questo avviene perché per inserire un elemento in una LinkedList è sufficiente modificare i collegamenti nei nodi con quelli nuovi, inserendo l'elemento tra di 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, 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 mille 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 è risultata significativamente più veloce, come evidente dalla tabella. LinkedList presenta complessità algoritmica costante, mentre ArrayList ha complessità lineare.

Ecco perché sono necessari diversi tipi di liste. Se il progetto gestisce grandi quantità di dati dove l'ottimizzazione è fondamentale, vale la pena valutare quale tipo di lista permetta al programma di essere più efficiente 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 possiede 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. Approfondiremo le mappe, in particolare HashMap, nelle prossime sezioni.

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 6

Chieda ad AI

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

Sezione 1. Capitolo 6

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`?