Una lista concatenata in java

Una lista concatenata è una particolare struttura dati formata da una sequenza di nodi o elementi, che per definizione prende il nome di collezione. Ogni nodo della lista è caratterizzato da un campo che contiene un tipo di dato e uno o due campi che contengono un riferimento al nodo successivo o precedente. Questo particolare dipende dal tipo di lista concatenata che si vuole realizzare. Diversi sono i tipi di liste concatenate. Quella che vedremo in questo articolo è anche detta lista semplicemente concatenata (o slist). Abbiamo anche quella doppiamente concatenata e quella circolare. Ad esempio la java.util.LinkedList di java è una lista circolare doppiamente concatenata.

In questo articolo vedremo una lista concatenata di interi, con un singolo puntatore, quindi con un solo riferimento al nodo successivo. Ciò significa che la lista sarà percorribile solo ed esclusivamento partendo dal nodo iniziale. Il nodo è composto da una variabile che nel nostro caso è un intero ed un riferimento ad un altro nodo :

class Nodo {
	int value;
	Nodo next;
}

Vediamo graficamente come avviene la concatenazione dei nodi :

La classe che implementermo definisce i metodi essenziali per gestire una lista :

• add()
• remove()
• contains()
• iterator()

Vedremo dettagliatamente lo sviluppo dei metodi per capire meglio il meccanismo della concatenazione dei nodi e della gestione della lista in generale. Ecco la struttura della classe :

public class ListaConcatenata implements Iterable {

	Nodo start;
	int size;

	public ListaConcatenata() {
		size = 0;
		start = null;
	}

	public void add(int n) {//..}
	public boolean remove(int n, boolean all) {//..}
	public boolean contains(int n) {//..}
	public void printList() {//..}
	public String toString() {//..}
	public Iterator iterator() {//..}

}

Il nodo start rappresenta il nostro punto di riferimento, cioè punterà sempre al primo elemento della lista. Inizialmente è impostato a null poichè la lista risulta vuota. Tutte le operazioni che effettueremo sulla nostra lista si focalizzeranno su questo nodo.

Inserimento di un nodo

Per l' inserimento di un nodo bisogna distinguere diversi casi. Immaginiamo di richiamare il metodo add(int value), la prima cosa che facciamo e ottenere un ' istanza di Nodo e settare il valore :

....
public void add(int value) {

	Nodo newNodo = new Nodo();
	newNodo.value = value;
	....

}
....

Adesso analizziamo i diversi casi o stati in cui si trova la lista e vediamo le operazioni da effettuare rispettivamente :

• Se la lista è vuota, start==null ,allora il nostro nodo start punterà direttamente al nodo inserito
• Se la lista contiene un solo nodo, start.next == null,allora agganciamo direttamente il nodo start al nodo inserito
• Per ultimo, se la lista contiene più di un nodo, start.next!=null ,allora iteriamo la lista fino all' ultimo nodo e lo agganciamo al nodo che vogliamo inserire

L 'iterazione della lista si può effettuare in diversi modi. La cosa più semplice è utilizzare un ciclo for in questo modo :

Nodo iter = null;
for(iter=start.next; iter.next != null; iter = iter.next);

Alla fine del ciclo il nodo iter punterà all' ultimo nodo della lista poichè iter.next == null (condizione del for). Quindi l' unica operazione che ci rimane da fare e agganciare iter a newNodo nel seguente modo :

iter.next = newNodo;

Ecco il codice completo del metodo :

public void add(int n) {
        Nodo newNodo = new Nodo();
        newNodo.value = n;
        if (start==null) {//1' Caso
           start = newNodo;
           start.next = null;
        } else if (start.next==null) { //2' caso
           start.next = newNodo;
        } else { // 3' Caso
            Nodo iter = null;
            for(iter=start.next; iter.next != null; iter = iter.next);
            iter.next = newNodo;
        }
        size++;
    }

Ricerca di un nodo

La ricerca è un operazione molto semplice, infatti basta una unica iterazione, usando un ciclo for, non appena il valore corrisponde a quello che cerchiamo allora ritorniamo direttamente true altrimenti alla fine del ciclo ritorniamo false :

public boolean contains(int value) {
	for(Nodo iter = start; iter!=null; iter = iter.next) {
		if (iter.value==n) return true;
	}
	return false;
}

Cancellazione di un nodo

Anche per la cancellazione di un nodo bisogna distinguere diversi casi che dipendono dallo stato in cui si trova la lista e dalla posizione in cui si trova il nodo che vogliamo eliminare. Il metodo implementato in questa classe oltre al valore riceve anche un boolean per specificare se vogliamo eliminare solo la prima corrispondenza del valore oppure tutte le corrispondenze. Allora adesso analiziamo i casi tendendo presente ciò che ho appena detto :

1. Se la lista è vuota allora il metodo si interrompe
2. Se il valore che voglio rimuovere si trova nel primo nodo, allora basta settare il nodo start a quello successivo, se esiste, altrimenti lo settiamo direttamente a null. E se abbiamo settato all a true, cioè vogliamo eliminare tutte le corrispondenze, ed il nodo successivo è ancora uguale al valore che vogliamo eliminare? Ci troviamo ancora nella condizione di eliminare il primo nodo. Allora questo caso si può raccogliere in un ciclo while nel seguente modo :

   .....
   public void remove(int value, boolean all) {
   	while(start!=null && start.value==value) {
   		start = start.next;
   		size--;
   		if (!all || start==null) return;
   	}
   	....
   }
   

   Questo ciclo 'consuma' le corrispondenze consecutive che si trovano all' inizio della lista, come in quest' esempio se vogliamo eliminare il valore 1:

       {1,1,5,3} ---> {5,3}
   

3. Se infine il valore si trova dopo il primo nodo allora ci serviremo di due nodi che puntano rispettivamente al primo ed al secondo nodo della lista :

   Nodo current = start.next;
   Nodo previous = start;
   		

   Con un ciclo for iteriamo la lista ed incrementiamo via via i due nodi. In questo modo un nodo 'insegue' l' altro, e non appena si trova una corrispondenza, il nodo previuous punterà al successivo di current :

   previous.next = current.next;

   Quindi con questa operazione il nodo che vogliamo eliminare viene 'saltato', non è più referenziato e quindi lo diamo in 'pasto' al Garbage Collector di java.

Questo è il codice del metodo completo che abbiamo analizzato :

 public void remove(int value, boolean all) {
        while(start!=null && start.value==value) {
            start = start.next;
            size--;
            if (!all || start==null) return;
        }
        Nodo current = start.next;
        Nodo previous = start;
        for(; current!=null; current=current.next) {
            if(current.value == value) {
                previous.next = current.next;
                current = previous;
                size--;
                if(!all) return;
            } else {
                previous = previous.next;
            }
        }
    }

Iterable e Iterator

Fino a questo momento abbiamo visto come iterare tutta la lista all' interno della nostra classe semplicemente con un ciclo for. In genere, caratteristica essenziale delle lista, è quella di implementare un iteratore, fornire esternamente la possibilità di scandire la lista in maniera sequenziale. Come avviene ad esempio per tutte le Collections di java, che sono di tipo Iterable cioè dispongono di un iteratore. Infatti questa interfaccia contiene un solo metodo :

	public Iterator iterator();

L' interfaccia Iterator fornisce tramite i metodi next(), hasNext() e remove(), un normale meccanismo di iterazione. Nel nostro caso l' iteratore è stato implementato nella classe IteratorLista :

class IteratoreLista implements Iterator {

    private ListaConcatenata lista;

    Nodo cursor = null;

    public IteratoreLista(ListaConcatenata lista) {
        this.lista = lista;
        cursor = lista.start;
    }

    public boolean hasNext() {
        return cursor!=null;
    }

    public Object next() {
        int value = cursor.value;
        cursor = cursor.next;
        return value;
    }

    public void remove() {
        throw new UnsupportedOperationException("Not supported yet.");
    }

}

Quindi abbiamo fornito anche alla nostra lista un iteratore. Vediamo l' implementazione del metodo dell' interfaccia Iterable :

 public Iterator iterator() {
 	return new IteratoreLista(this);
 }

L' importanza dell' interfaccia Iterable sta nel fatto che alcuni costrutti come il 'foreach' di java ne utilizzano direttamente il metodo senza preoccuparsi dei dettagli implementativi dell' iterazione, ad esempio :

ListaConcatenata lista = new ListaConcatenata();
for(Object element:lista)
	System.out.println(element);

Questo è il codice completo della lista che abbiamo costruito :

public class ListaConcatenata implements Iterable {

    Nodo start;
    int size;

    public ListaConcatenata() {
        size = 0;
        start = null;
    }

    public void add(int n) {
        Nodo nuovo = new Nodo();
        nuovo.value = n;
        if (start==null) {
           start = nuovo;
           start.next = null;
        } else if (start.next==null) {
           start.next = nuovo;
        } else {
            Nodo iter = null;
            for(iter=start.next; iter.next != null; iter = iter.next);
            iter.next = nuovo;
        }
        size++;
    }

    public void remove(int value, boolean all) {
        while(start!=null && start.value==value) {
            start = start.next;
            size--;
            if (!all || start==null) return;
        }
        Nodo current = start.next;
        Nodo previous = start;
        for(; current!=null; current=current.next) {
            if(current.value == value) {
                previous.next = current.next;
                current = previous;
                size--;
                if(!all) return;
            } else {
                previous = previous.next;
            }
        }
    }

    public boolean isEmpty() {
        return size==0;
    }

    public String toString() {
        String str = "{";
        for(Object element:this)
            str+=element+",";
        str += "}";
        return str;

    }

    public int size() {
        return size;
    }

    public boolean contains(int n) {
        for(Nodo iter = start; iter!=null; iter = iter.next)
            if (iter.value==n) return true;
        return false;
    }

    public Iterator iterator() {
        return new IteratoreLista(this);
    }

}