Lista
lista.png

Le liste sono una struttura dati che non presentano le limitazioni degli array. In particolare, ogni elemento è contenuto in una porzione di memoria indipendente, e si mantiene un puntatore (o riferimento) all'elemento successivo. Per questo motivo possono essere inseriti o eliminati un qualunque numero di elementi, senza sprecare memoria o soffrire di limitazioni.

Questi vantaggi sono compensati dalla lentezza delle operazioni di ricerca, poiché non è possibile un accesso diretto ad un elemento della lista. A differenza degli array, dove la contiguità delle locazioni di memoria permette di conoscere in anticipo la locazione dell'elemento i-esimo, nelle liste non sono note le locazioni a priori, tranne quella del primo elemento. Per cercare un elemento è quindi necessario esaminare il primo elemento, e passare al successivo, fino alla fine della lista. Nel caso peggiore questa ricerca comporta una complessità O(n).

L'aggiunta di un elemento in fondo alla lista è una operazione molto veloce, purché si mantenga un puntatore alla coda della lista. L'inserimento di un elemento è anch'esso veloce, escludendo tuttavia il tempo per cercare l'elemento dopo il quale si deve inserire il nuovo elemento.

Implementazione

In una implementazione semplice, un elemento della lista viene rappresentato da un oggetto di tipo Node. Esso contiene un riferimento al nodo successivo e un oggetto che memorizza i dati. In questo esempio viene utilizzata una stringa per memorizzare i dati; in altre parole, si vuole memorizzare nella lista un insieme di stringhe.

class Node
{
    Node next;
    string data;
 
    public Node Next
    {
        get
        {
            return next;
        }
        set
        {
            next = value;
        }
    }
 
    public string Data
    {
        get
        {
            return data;
        }
    }
 
    public Node(Node nodenext, string nodedata)
    {
        next = nodenext;
        data = nodedata;   
    }
}

La classe che implementa la lista contiene un puntatore (o riferimento) al primo elemento, che inizialmente è null, poiché la lista è vuota.

Quando viene inserito il primo elemento, esso diventa il primo ed ultimo nodo della lista. L'ultimo nodo della lista ha un riferimento null, perché non ci sono altri elementi successivi.

L'inserimento di un nodo tra altri due nodi avviene modificando il riferimento del nodo che precede verso il nuovo nodo, e il riferimento del nuovo nodo al nodo che segue. Con la semplice modifica di due riferimenti è quindi possibile inserire un nuovo elemento nella collezione. Il problema principale consiste nel raggiungere il nodo dopo il quale viene inserito quello nuovo.
inserimento di un nuovo nodo

Nell'implementazione della funzione che inserisce un nuovo nodo si hanno come argomenti il nodo prima del quale viene inserito il nuovo nodo e un oggetto che è il contenuto del nuovo nodo. Si utilizzano due riferimenti p ed n, che indicano il nodo precedente e il nodo attuale, durante il ciclo while che "scansiona" la lista.

Se viene trovato il nodo prima del quale deve essere inserito il nuovo elemento, ovvero il ciclo di ricerca non termina con null, in fondo alla lista, allora si crea il nuovo nodo facendolo puntare a n e si modifica il nodo precedente che è puntato da p. Se invece è stata raggiunta la fine della lista allora viene visualizzato un errore.

public void InsertNode(Node nd, object x)
{
    Node n = first;
    Node p = null;
 
    while(n != null)
    {
        if(n == nd)
            break;
        p = n;
        n = n.Next;
    }
 
    if (n != null && n != first)
    {
        Node newnode = new Node(n, x);
        p.Next = newnode;
    }
    else if(n != null)
    {
        Node newnode = new Node(n, x);
        first = newnode;
    }
    else
        Console.Out.WriteLine("La lista non contiene il nodo indicato");
}

Se il nodo è il primo è necessario aggiornare il riferimento al primo nodo. Alternativamente si potrebbe cercare il contenuto di un nodo, specificando l'oggetto che contiene. In questo caso si può modificare leggermente il codice del ciclo while in questo modo:

while(n != null)
{
    if(n.Data == obj)
        break;
    p = n;
    n = n.Next;
}

Si può notare che il confronto tra due oggetti potrebbe essere effettuato in modo personalizzato se i nodi della lista contenessero degli oggetti di classi che implementano IComparable. In questo caso si può utilizzare il metodo CompareTo per poter confrontare i due oggetti.

L'aggiunta di un nodo in fondo alla lista è un caso particolare dell'inserimento. In questo caso si deve distinguere l'aggiunta di un nodo quando la lista è vuota e l'aggiunta di un nodo in fondo ad una lista che contiene almeno un elemento. Nel primo caso la procedura è semplicissima, e consiste solo nel creare il nodo e nell'aggiornare il puntatore a first

L'eliminazione di un nodo è altrettanto semplice. Una volta individuato il nodo precedente a quello da eliminare, si modifica il riferimento Next dell'oggetto precedente verso quello successivo rispetto a quello da eliminare. In questo modo si "salta" il nodo da eliminare. A questo punto nessun riferimento punta al nodo che viene saltato, ed è quindi successivamente segnalato automaticamente per essere eliminato tramite il garbage collector.

Nell'implementazione si utilizzano anche in questo caso due riferimenti n e p, che puntano rispettivamente all'oggetto da eliminare e all'oggetto precedente. Il ciclo while è lo stesso nel caso dell'inserimento.

public void RemoveNode(Node nd, object x)
{
    Node n = first;
    Node p = null;
 
    while(n != null)
    {
        if(n == nd)
            break;
        p = n;
        n = n.Next;
    }
 
    if (n != null && n != first)
        p.Next = n.Next;
    else if(n != null)
        first = n.Next;
    else
        Console.Out.WriteLine("La lista non contiene il nodo indicato");
}

In questo caso è sufficiente una sola istruzione per cancellare un nodo. Se il nodo da cancellare è il primo si modifica semplicemente il puntatore first facendolo puntare al secondo nodo.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License