Il tipo di dati astratto Lista
Una lista è una struttura dati che permette di memorizzare dati in maniera sequenziale, e permette di accedere e cancellare dati in posizioni arbitrarie (cioè non solo il primo o l'ultimo inserito, come nel caso di pile e code).

Una lista è una sequenza di zero o più elementi
 

<A1 A2 ... An>

che rappresenteremo semplicemente elencando gli elementi tra una coppia di parentesi quadre:
 

 [A1 A2 ... An] 

Come per le pile e le code, non vi è completo accordo sull'insieme di operazioni che caratterizzano le liste. Si veda come esempio l'interfaccia List nelle API di Java, le cui implementazioni più comuni sono Vector e ArrayList, entrambe basate su array.

 

La struttura a lista concatenata

Purtroppo (per gli studenti), esiste un altro concetto, completamente diverso dal tipo di dato Lista che viene comunemente indicato con lo stesso nome ovvero la struttura a lista concatenata (in inglese Linked List), tale struttura viene talvolta detta sequenza lineare ad accesso sequenziale. È di quest'ultima che ci occuperemo in questo capitolo.


La struttura a lista concatenata
Il difetto principale della struttura array è dato dal fatto che essendo gli elementi memorizzati in posizione contigue, inserimenti e cancellazioni comportano un numero di spostamenti che nel caso peggiore può essere dell'ordine del numero degli elementi della struttura. La struttura a lista concatenata risolve completamente questo problema a spese di una maggiore occupazione di memoria e di una gestione decisamente più complessa.

Una lista concatenata è una sequenza lineare di nodi, ciascuno dei quali memorizza un valore e contiene un riferimento (puntatore) al nodo successivo nella sequenza. In questo modo è possibile aggiungere e cancellare nodi in qualunque posizione semplicemente aggiustando il sistema di puntatori senza operare sui nodi non interessati dalla aggiunta o dalla cancellazione.

 

 

Si può accedere all'informazione contenuta nel generico nodo di una lista, scandendo la lista, dato che l'accesso ad un elemento è possibile attraverso il puntatore contenuto nell'elemento precedente. A particolari elementi della lista si può anche accedere direttamente (se si ha un puntatore all'elemento).

Variazioni sul tema

Le liste viste finora si chiamano liste semplici o lineari, dato che il legame tra gli elementi si sviluppa linearmente. Modificando semplicemente lo schema, si possono costruire altri tipi di liste, ovvero le liste bidirezionali e le liste circolari.

Nelle prime, ogni elemento o nodo presenta un puntatore oltre che al nodo successivo, come nelle liste semplici, un puntatore all'elemento precedente. L'accesso alla lista può quindi avvenire a entrambi gli estremi e lo scorrimento può avvenire quindi in entrambe le direzioni.

Nelle liste circolari, il puntatore al successore nell'ultimo elemento della lista invece di puntare null, punta al primo elemento della lista. La scansione della lista può quindi avvenire in modo ciclico.


Liste concatenate in Java: la classe ListNode
La seguente classe implementa un nodo di una lista concatenata. 

/**  
 * Classe usata per descrivere il singolo nodo di una lista concatenata
 */
public class ListNode<E> {
    
    public E element ;
    public ListNode<E> next ;
        
/**
 * Costruttore nodo per liste unidirezionali
 */
    public ListNode (E element, ListNode<E> next) {
       this.element = element ;
       this.next = next ;
    }
}

Allo scopo di ottenere codice più efficiente, si è deciso di rendere pubbliche le variabili di istanza invece che di accedervi attraverso 4 metodi (per esempio getElement, setElement, getNext, SetNext).

Manipolazione di liste

Vediamo alcuni frammenti di codice che manipolano le liste. Si assumono le dichiarazioni 
     ListNode<E> l1;
     E                       A;   // l'informazione da inserire

  • Inserzione in testa, l1, (che può essere null), è la lista: 
        l1 = new ListNode<E>(A, l1);

  • Inserzione in coda, l1, (che non può essere null), è l'ultimo elemento della lista: 
        l1.next = new ListNode<E>(A, null);

  • Inserzione all'interno, l1, (che non può essere null), è l'elemento della lista precedente a quello in cui deve comparire il nuovo: 
        l1.next = new ListNode<E>(A, l1.next);

  • Rimozione in testa, l1, (che non può essere null), è la lista: 
        l1 = l1.next;

  • Rimozione all'interno, l1, (che non può essere null), è l'elemento della lista precedente a quello da rimuovere (che deve esistere): 
        l1.next = l1.next.next;

  • Rimozione in coda, l1, (che non può essere null), è il penultimo elemento della lista: 
        l1.next = null;

Esempi di uso di liste concatenate
Vediamo un metodo che crea una lista concatenata a partire da un ArrayList e un metodo che crea un ArrayList a partire da una lista concatenata. 

/**  
 * converte un ArrayList in una lista concatenata
 * @param v  l' ArrayList
 * @return la lista
 */
   public static<E> ListNode<E> vetToList(ArrayList<E> v) {
      if(v == null || v.size() == 0) return null;
      Iterator<E> itr = v.iterator();
      ListNode<E> l = new ListNode<E>(itr.next(), null), l0 = l;
      while (itr.hasNext()) {
         l.next = new ListNode<E>(itr.next(), null);
         l = l.next;
      }
      return l0;
   }

/**  
 * converte una lista concatenata in un ArrayList
 * @param l  la lista
 * @return il ArrayList
 */
    public static<E> ArrayList<E> listToVet(ListNode<E> l) {
      if(l == null) return null;
      ArrayList<E> v = new ArrayList<E>();
      do {
         v.add(l.element);
         l = l.next;
      } while (l != null);
      return v;
   }


Ricorsione ed iterazione

Molti algoritmi che visitano delle strutture dati lineari si possono scrivere sia in modo iterativo (cioè usando un while o un for), sia in modo ricorsivo. Ad esempio, supponiamo di voler cercare un oggetto in una lista concatenata.
 

Il seguente frammento di codice è iterativo e usa un while: 

  // Si assume che il primo elemento non sia null
      ListNode<E> h = n;
      while (h != null) { 
          if(x.equals(h.element)) return true;
          h = h.next; 
      }
      return false;

Alternativamente, si può sfruttare la definizione ricorsiva: 

Una lista concatenata è una struttura definita su un insieme di nodi che: 
  • non contiene nessun nodo (lista vuota), oppure
  • contiene un nodo (spesso denominato car, first, front), seguito da una lista concatenata (spesso denominato cdr, rest).

 Il seguente metodo è basato sulla definizione ricorsiva: 

  // Si assume che il primo argomento non sia null
  public static<E> boolean cercaRic(E x, ListNode<E> n){ 
      // Caso base
      if(n == null) return false;
      // Caso ricorsivo
      if (x.equals(n.element)) return true;
      return cercaRic(x, n.next); 
  }

Esercizi sull'uso delle liste concatenate
1) Si scriva un metodo di intestazione: 
      public static<E> void noDup1(ListNode<E> l)

che, data una lista concatenata, ne elimina le ripetizioni (modificando la lista passata per argomento)

2) Si scriva un metodo di intestazione: 
      public static<E extends Comparable<E>> void noDup2(ListNode<E> l)

che, data una lista concatenata ordinata, ne elimina le ripetizioni (modificando la lista passata per argomento)

SOLUZIONE

3) Si scriva un metodo di intestazione: 
      public static<E extends Comparable<E>> ListNode<E> copyNoDup(ListNode<E> l)

che, data una lista concatenata ordinata, restituisce una nuova lista senza ripetizioni (non modificando la lista passata per argomento)

SOLUZIONE

4) Si scriva un metodo di intestazione: 
      public static<E> ListNode<E> concatConModifiche(ListNode<E> l1, ListNode<E> l2)

che, data due liste concatenate, ne rende la concatenazione (modificando le liste passate per argomento)

SOLUZIONE

5) Si scriva un metodo di intestazione: 
      public static<E> ListNode<E> concatCopy(ListNode<E> l1, ListNode<E> l2)

che, data due liste concatenate, ne rende la concatenazione (non modificando le liste passate per argomento)

SOLUZIONE