Che cos'è una Linked List e quando usarla

Ciao a tutti e bentornati in questa lezione parte del corso preparatorio per affrontare un colloquio informatico. A seconda della posizione di lavoro a cui si fa domanda, potrebbero spuntare fuori domande teoretiche su concetti come strutture dati, system design, o analisi degli algoritmi. Con questo post cominciamo una serie di guide sulle strutture dati più comunemente usate nell'informatica. In particolare, cominciamo con la Linked List, Lista concatenata, o lista linkata.

Che cos'è una Linked List

Una Lista concatenata è una struttura dati che come un array viene usata per rappresentare una sequenza di nodi (o dati). Per esempio, si può usare per rappresentare una parola composta da lettere dove ogni lettera è presente in un nodo della lista. 

Questa è composta da una serie di nodi collegati tra di loro attraverso un puntatore ed un nodo speciale che indica l'inizio della lista (chiamato head). Per esempio, immaginate una fila di bambini che si tengono per mano: In questo esempio possiamo considerare ogni bambino come un "Nodo" e ogni braccio come il "Puntatore". All'inizio della fila vi è la Maestra (head). La maestra non comunica direttamente con tutti i bambini nella fila, ma solamente con il bambino direttamente dietro di lei. Se vuole contattare il quarto bambino nella fila deve farlo attraverso i tre bambini davanti a lui. 

Perché usare una Lista Linkata invece di un array?

La domanda che sorge spontanea è: Perché usare una Linked List invece di un array? In fondo con un array possiamo accedere all'elemento in posizione n tramite il suo indice in tempo costante (O(1)). Il vantaggio principale dell'utilizzo di una Linked List rispetto all'uso di un Array è dato dal fatto che la Lista concatenata può variare di dimensioni. Se vogliamo aggiungere un bambino alla fila, basta semplicemente che l'ultimo bambino in fila dia la mano al nuovo bambino ed è fatta. Gli array invece hanno dimensione fissa. Per esempio, se si vuole inserire un nuovo elemento all'interno di un array già pieno, bisogna o sostituire uno degli elementi o copiare gli elementi in un nuovo array con dimensioni più grandi.

Come implementare una Lista concatenata in Java

Abbiamo visto che una Linked List è composta da vari nodi e da un nodo speciale chiamato "head". Questo nodo indica l'inizio della lista. In basso vi viene mostrato il codice Java per implementare una Linked List.

class Node{
    public Node next;
    public int data;
    public Node(int data){
        this.data = data;
    }
}

Come abbiamo detto precedentemente una Linked List è formata da una serie di elementi (nodi) collegati tra loro tramite dei pointer. Possiamo modellare un nodo con una classe Java. Ogni nodo ha due elementi:

1) Il contenuto del nodo. In questo esempio usiamo la Lista Linkata per salvare numeri quindi usiamo int come tipo per data. 

2) Un puntatore che punta verso il prossimo elemento nella lista. Se il nodo è l'ultimo nella lista questo puntatore ha il valore di null.

Forse avete notato che precedentemente abbiamo detto che una Linked List è formata da un nodo speciale chiamato head. Quella che vedete in alto è una implementazione molto semplice di una Linked List dove non abbiamo una struttura dati in se chiamata Linked List ma utilizziamo il concetto di un nodo per ottenere la stessa cosa. Spieghiamo meglio:

Se vogliamo creare una Linked List usando questo codice, basta semplicemente istanziare la classe Node in una variabile. Chiamiamo questa variabile head (testa) perché rappresenterà il primo nodo nella lista. 

// Creiamo un nuovo nodo con il numero 1 al suo interno
Node head = new Node(1);

Come vedete abbiamo creato un nuovo nodo. Se ispezioniamo il codice del costruttore della classe vediamo che il numero 1 viene inserito all'interno del nodo e il puntatore al prossimo nodo (next) non viene inizializzato e quindi contiene un valore null.

Ora vediamo come aggiungere un nuovo elemento alla lista. In un array di fisse dimensioni possiamo semplicemente inserire l'elemento usando un indice, ma in questo caso non sappiamo quanto sia lunga la lista. Quindi per inserire un nuovo elemento bisogna iterare lungo la lista fino a raggiungere la fine. per fare ciò possiamo fare uso del puntatore next che restituisce il prossimo elemento nella lista.

Consideriamo il caso in cui abbiamo un solo nodo (il nodo head). Per inserire un nuovo elemento con valore 2 dopo il nodo head, basta semplicemente assegnare il nuovo nodo al puntatore di head: head.next = new Node(2);

Se ora vogliamo inserire un terzo elemento? Non possiamo semplicemente fare head.next = new Node(3); Perché il terzo nodo sostituirebbe il posto del secondo nodo ed il secondo nodo verrebbe perso per sempre. Quello che invece viene fatto per inserire il terzo elemento è iterare la lista fino ad ottenere l'ultimo elemento in lista. Quando abbiamo questo ultimo elemento (chiamiamolo tail come coda) possiamo fare tail.next = new Node(3);

Manualmente questo processo sarebbe cosi:

Node head = new Node(1);
head.next = new Node(2);
// Ora che abbiamo due elementi nella lista come inserire il terzo?
// Manualmente possiamo fare così (ovviamente questo non è il metodo migliore)
// Otteniamo il secondo node
Node secondo = head.next;
// Settiamo il puntatore del secondo nodo
secondo.next = new Node(3) ;
// Usando una sola riga di codice possiamo anche fare
head.next.next = New Node(3);

Ovviamente questo metodo non è efficiente. Immaginiamo se abbiamo una lista con molti elementi, diventa impossibile fare: head.next.next.next.next... 
Quindi andiamo ad inserire una funzione all'interno della classe del Nodo che restituisce l'ultimo elemento nella lista iterando la lista finché non si incontra un nodo il quale valore di next sia null. Quando questo ultimo elemento viene trovato, possiamo semplicemente assegnare il nuovo nodo al puntatore next dell'ultimo nodo.

class Node{
    public Node next;
    public int data;
    public Node(int data){
        this.data = data;
    }
    public void add(int data){
        Node end = new Node(data);
        Node n = this;
        while(n.next != null){
            n = n.next;
        }
        n.next = end;
    }
}

Quello che vedete in alto è un codice molto semplice per implementare una linked list senza far uso di una struttura dati chiamata LinkedList.

Se proprio volete far uso di una struttura dati di tipo wrapper potete creare una classe chiamata LinkedList con una variabile chiamata di tipo Node chiamata head. 

Eliminare un nodo da un a Linked List è molto semplice; Ci sono due casi: Se l'elemento che volgiamo rimuovere è il primo della lista (head), basta semplicemente creare un nuovo nodo head con il valore head.next. Se invece il nodo da eliminare si trova in qualsiasi altra posizione nella lista, basta "scavalcare" il nodo da eliminare. Questo può essere fatto, cambiando il valore del puntatore (next) del nodo precedente dal nodo al nodo.next. Questo concetto è più difficile da spiegare che da implementare. La foto in basso mostra meglio cosa significa eliminare un nodo da una lista concatenata. 


Vediamo come eliminare un nodo con Java:

Node eliminaNodo(Node head, int data){
    Node n = head;
    if(n.data == data){
        // se si trova nella prima posizione
        return head.next;
    }
    // iteriamo fino alla fine della lista
    while(n.next!=null){
        if(n.next.data == data){
            // puntiamo il nodo precedente verso il nodo successivo
            n.next = n.next.next;
            return head;
        }
        n = n.next;
    }
    return head;
}

Questo metodo restituisce il nuovo nodo head, quindi va chiamato cosi: head = EliminaNodo(head,x). 
Abbiamo visto come implementare una semplice Linked List in Java. Implementare questa in qualsiasi altro linguaggio come Python o javascript è molto semplice e praticamente uguale. 

Abbiamo visto che le Linked List sono utili da utilizzare quando abbiamo una lista che varia di dimensioni. Come potete vedere aggiungere un nuovo elemento alla lista può essere fatto velocemente soprattutto se si mantiene un puntatore all'ultimo elemento della lista. Inserire un elemento in un array di fisse dimensioni è più veloce ma solo nel caso in cui l'array non sia pieno. Se abbiamo un array pieno e volgiamo inserire un nuovo elemento bisogna creare un nuovo array. Questo richiede molto tempo se l'array è grande. 

Uno degli utilizzi più comuni della Lista concatenata è la costruzione di: Stack e Queues. Vedremo questi concetti nelle prossime parti del corso.