Liste

La ADT List

Nel linguaggio informatico una lista è una struttura dati che permette l’accesso agli elementi spostandosi tra elementi adiacenti (successivo e precedente). La lista assomiglia ad una sequenza di oggetti non numerati per cui l’unico modo per accedere all’elemento numero i è partire dall’inizio e contarne uno dopo l’altro fino a raggiungere l’i-esimo. Un esempio concreto può essere un mazzo di carte: per sapere, ad esempio, la decima carta, dobbiamo partire dall’inizio (che va opportunamente definito) scartare le prime 9 carte e quindi ottenere la decima.

A differenza del mazzo di carte, tuttavia, la lista non permette di scegliere una “carta” (elemento della lista) a caso, bensì permette solo l’accesso diretto ad elementi ben definiti quali l’inizio (testa, head) o la fine (coda o tail) della lista.

Alcune operazioni sono estremamente semplici da eseguire su una lista:

• l’inserimento e l’eliminazione in testa o in coda;
• lo split (chiamato anche splice) della lista su un elemento ben preciso.

Alcune operazioni sono semplici a patto che sia disponibile un elemento (posizione) ben specifico:

• eliminazione dell’elemento;
• inserimento prima o dopo l’elemento;
• split rispetto all’elemento.

Infine ci sono operazioni che richiedono diverse istruzioni su una lista:

• accesso all’elemento di indice i (specialmente se i non è “vicino” all’inizio o alla fine);
• ricerca di un elemento.

1 -> 2 -> 3 -> 4 -> 5

2 -> 4 -> 0 -> 2 -> 3 -> 3

Il concetto di posizione nella lista

Come visto sopra, le operazioni su una lista possono essere basate su uno specifico elemento della lista, parlare di elementi è troppo generico e rischio di confondersi con il contenuto, per questo è meglio parlare di posizione nella lista.

Cerchiamo di capire meglio il concetto di posizione con qualche esempio.

10 -> -2 -> 120 -> 0 -> 123 -> 0 -> 11

Nelle liste come negli array, le posizioni possono anche essere associate a degli indici, ad esempio la prima posizione ha indice 0, la seconda ha indice 1 e così via. In effetti gli array sono strutture dati in cui le posizioni vengono indicate da indici.

Posizione in Java

Il concetto di posizione nella lista sopra definito può essere espresso in una interfaccia Java nel seguente modo

public interface IListPosition {
    Object value();
    IListPosition next();
    public void setNext(IListPosition newNext);
    IListPosition prev();
    public void setPrev(IListPosition newPrev);
}

Si noti che:

• il valore (value) è di tipo Object per poter indicare qualsiasi tipo,
• ogni posizione permette di accedere al successore mediante next() ed al predecessore mediante prev(),
• i metodi prev e next restituiscono a loro volta una posizione.

Liste singolarmente concatenate

Una lista singolarmente concatenata è una lista in cui ogni posizione è collegata alla successiva, ma non alla precedente.

Liste doppiamente concatenate

Una lista doppiamente concatenata è una lista in cui ogni posizione è collegata sia alla successiva sia alla precedente.

Operazioni su liste

La struttura dati lista può, ovviamente, essere utilizzata per tutte le usuali operazioni di accesso e manipolazione dei dati. Inoltre le liste, a differenza degli array, permettono di eseguire alcune operazione, come il merge e lo split (chiamato splicing), in maniera molto efficiente.

In questa lezione vedremo il codice Java per alcune operazioni utilizzando l’interfaccia IListPosition discussa sopra. Per rappresentare una lista useremo una semplice classe contenente:

• un riferimento, chiamato head, che punti alla testa della lista;
• un intero n che conta gli elementi attualmente memorizzati nella lista;
• un riferimento, chiamato tail, che punti alla coda della lista, solo nel caso di liste doppiamente concatenate.

// SinglyLinkedList.java
public class SinglyLinkedList {
    private IListPosition head;
    private int n;
    public SinglyLinkedList() {
        head = null;
        n = 0;
    }
}
 

// DoublyLinkedList.java
public class DoublyLinkedList {
    private IListPosition head;
    private IListPosition tail;
    private int n;
    public DoublyLinkedList() {
        head = tail = null;
        n = 0;
    }
}

Nel codice sotto, inoltre, faremo uso della classe concreta ListPosition che implementa l’interfaccia IListPosition e che prevede il seguente costruttore per inizializzare tutti i tre parametri content, next e prev (per evitare confusione con i nomi dei metodi i campi per next e prev sono chiamati predecessor e successor, rispettivamente).

public class ListPosition implements IListPosition {
    private Object content;
    private IListPosition successor;
    private IListPosition predecessor;

    public ListPosition(Object c, IListPosition n, IListPosition p) {
        content = c;
        successor = n;
        predecessor = p;
    }
    // Implementazione (ovvia) di IListPosition
    // ...
}

Inserimento e cancellazione

Vediamo quattro tipi di operazione di inserimento/cancellazione

1. inserimento/cancellazione in testa
2. inserimento/cancellazione in coda (solo doubly linked)
3. inserimento/cancellazione dopo una data posizione
4. inserimento/cancellazione prima di una data posizione (solo doubly linked)

Inserimento in testa

L’inserimento in testa è possibile sia per le singly che per le doubly linked list, tuttavia bisogna fare attenzione al caso di liste vuote (e doppia attenzione nel caso di doubly linked list).

public void insertAtHead(Object o) {
    // crea IListPosition per l'oggetto da inserire
    // Il suo 'next' sarà quello che è adesso in testa
    // Funziona anche se la lista è vuota, perché?
    ListPosition newPosition = new ListPosition(o, head, null);
    // Inserisco la 'posizione' appena creata come nuova testa
    head = newPosition;
    // aggiorno il conteggio degli elementi
    n++;
} 

Lo stesso metodo nelle doubly linked list va modificato per tenere conto:

• del riferimento alla coda tail (solo se la lista è vuota prima dell’inserimento) e
• del puntatore prev della vecchia testa (se la lista non è vuota).

public void insertAtHead(Object o) {
    ListPosition newPosition = new ListPosition(o, head, null);
    head = newPosition;
    if(tail == null) { // la lista era vuota (tail -> null)
        tail = newPosition;
    } else { // esisteva una head e quindi aggiorno il suo prev
        newPosition.next().setPrev(newPosition); // !!!
    }
    n++;
} 

La seguente riga

newPosition.next().setPrev(newPosition);

non fa altro che accedere alla vecchia testa (che adesso è il successore della nuova testa) e modificare il suo prev in modo da puntare alla nuova testa.

Inserimento in coda

Inserimento dopo

Un’altra possibilità per l’inserimento in una lista è indicare la posizione del nuovo elemento rispetto ad un elemento già esistente. Il caso più semplice è l’inserimento dopo la posizione pos.

public void insertAfter(Object o, IListPosition pos) {
    IListPosition newPos = new ListPosition(o, pos.next(), null);
    pos.setNext(newPos);
    n++;
}

public void insertAfter(Object o, IListPosition pos);

Inserimento prima

Data una posizione all’interno della lista, si può immaginare all’inserimento di un nuovo elemento nella posizione precedente. Nel caso si liste singolarmente concatenate questa operazione è lievemente più complessa di insertAfter poiché manca il riferimento prev che indica la posizione precedente (è comunque possibile tale operazione , vedi esercizio sotto).

public void insertBefore(Object o, IListPosition pos);

public void insertBefore(Object o, IListPosition pos);

Cancellazione in testa

Dagli esempi sopra si può vedere come l’inserimento sia un operazione “semplice” nelle liste, anche la cancellazione, come vederemo, richiede poche istruzioni.

Iniziamo vedendo la cancellazione dell’elemento che si trova nelle testa della lista. In questo caso per cancellazione si intende che la posizione viene rimossa dalla lista e che l’elemento che seguiva quello rimosso, diventa la nuova testa della lista.

Il codice Java qui sotto mostra la rimozione in testa per una singly linked list.

public Object removeAtHead() {
    if (head == null) {
        return null; // Rimozione da una lista vuota, errore?
    }
    IListPosition removed = head;
    head = head.next();
    n--;
    return removed.value();
}

Si noti che il codice restituisce anche il valore dell’elemento eliminato, senza questa restituzione il contenuto verrebbe perso a meno che non fosse stato precedentemente memorizzato.

Nel caso di doubly linked list è necessario aggiustare anche i riferimenti prev ed eventualmente la coda.

public Object removeAtHead();

Ricerca

Come già visto negli array, anche nelle liste è possibile cercare uno specifico valore all’interno di una lista. A differenza degli array in cui l’accesso avviene mediante indicizzazione (cioè con la posizione), nelle liste l’accesso è sequenziale, utilizzando i riferimenti next e prev.

Per cercare all’interno di un lista, si usa il concetto di iteratore che rappresenta un “puntatore” all’elemento attuale della lista, durante la ricerca l’iteratore viene spostato in avanti ad ogni ciclo, fino a raggiungere la fine della lista.

public IListPosition search(Object o) {
    IListPosition iterator = head;
    while(iterator != null) {
        if(iterator.value().equals(o)) {
            return iterator;
        }
        iterator = iterator.next();
    }
    return null;
}

Splicing

Una operazione molto semplice da eseguire su una lista è la sua divisione in due o più sottoliste. Questa operazione viene definita splicing (o split) della lista, ovviamente per effettuare lo splicing dobbiamo sapere in quale posizione dovrà avvenire lo spezzamento.

public SinglyLinkedList splice(IListPosition splicePosition) {
    SinglyLinkedList tailList = new SinglyLinkedList();
    tailList.head = splicePosition.next();
    splicePosition.setNext(null);
    IListPosition iterator = tailList.head;
    while(iterator != null) {
        tailList.n++;
        iterator = iterator.next();
    }
    n -= tailList.n;
    return tailList;
}

Merge

Oltre a spezzare una lista, è possibile anche unire due o più liste utilizzando l’operazione di merge (fusione) di due liste.

Il seguente codice Java aggiunge alla fine della lista corrente una lista other restituendo la nuova lista.

public SinglyLinkedList merge(SinglyLinkedList other) {
    // current list is empty
    if (head == null) {
        head = other.head;
        n = other.n;
        return this;
    }
    // Finds the tail of the current list
    IListPosition last = head;
    while(last.next() != null) {
        last = last.next();
    }
    last.setNext(other.head);
    n+= other.n;
    return this;
}

Esercizi su liste

Ricerca e indicizzazione

public IListPosition positionAtIndex(int i); 

Inserimento, Merge e split

public void insertAllAt(SinglyLinkedList other, IListPosition pos);

1 -> 2 -> 5 ->

3 -> 4 ->

1 -> 2 -> 3 -> 4 -> 5 ->