Liste Una istanza di classe può contenere, tra le sue variabili, anche un puntatore ad un oggetto della classe stessa. Questo consente di concatenare oggetti di una stessa classe, a formare strutture complesse quali liste o alberi. In particolare, una lista è ottenuta dalla concatenazione di nodi, ciascuno dei quali contiene un puntatore al nodo successivo, nonché un campo dati talvolta chiamato cargo. Attraversamento di una lista Nel codice Processing che segue viene creata una lista di tre nodi concatenati. Quindi tale lista viene visitata per attraversamento e il cargo di ogni nodo viene stampato. Si notino le seguenti cose: La classe Node ha due tipi di costruttore, uno senza parametri ed uno con parametri. Quest'ultimo consente la creazione con inizializzazione del cargo e del puntatore al nodo successivo. C'è un metodo toString che converte il cargo in una stringa stampabile ogni volta che viene invocata la funzione print sul nodo.

Così come gli array sono il supporto naturale dei cicli for e delle iterazioni sequenziali, così le liste sono il supporto naturale della algoritmica ricorsiva. Gli algoritmi ricorsivi sono definiti induttivamente stabilendo l'operazione per un elemento base (la base della ricorsione) e stabilendo come utilizzare il risultato dell'elaborazione sulla lista privata di tale elemento. Inoltre, bisogna assicurarsi che l'elaborazione così arrangiata in maniera "telescopica" raggiunga ad un certo punto una condizione di terminazione della ricorsione. Ciò non è sempre banale perché le catene di puntatori degli elementi di una lista potrebbero presentare dei loop, la cui visita procederebbe senza fine. Nell'esempio si può introdurre una funzione di stampa dall'ultimo elemento al primo:

Si può costruire una classe che incorpori l'intera lista e le operazioni che su di essa si intendono eseguire. Ad esempio, si può estendere con l'introduzione di una classe IntList che supporta stampe per attraversamento diretto e inverso (ricorsivo). Si noti l'uso di un doppio metodo printBackward, uno con e uno senza argomenti, per consentire l'invocazione del metodo sull'oggetto lista senza necessità di passare un puntatore alla testa della lista stessa.

Questo è un esempio di classe wrapper, cioè di confezionamento object-oriented di una struttura dati. Le classi wrapper esistono per tutti i tipi primitivi di Java (double, int, ecc.) e consentono di creare e manipolare oggetti che contengono valori primitivi. Ad esempio, la classe wrapper Integer può essere interrogata in relazione al più piccolo e più grande valore rappresentabile mediante Integer.MIN_VALUE e Integer.MAX_VALUE, rispettivamente. Il valore numerico di un oggetto della classe Integer si ottiene con il metodo intValue(). Anche gli array in Java sono accessibili mediante una classe wrapper. La classe Arrays, accessibile importando java.util.*, consente di fare operazioni di test di uguaglianza, di ricerca, e di ordinamento. Ad esempio, il semplice codice

esegue un test di uguaglianza tra due array di interi. Lettura Si legga il capitolo 14 di How to Think Like a Computer Scientist

Pile Lo stack, o pila, è una struttura dati di grande importanza. Ad esempio, essa è implicitamente coinvolta nell'esecuzione di codice ricorsivo, quale quello del metodo printBackward. In effetti, a runtime le chiamate a procedura sono sistemate, insieme ai loro parametri, una sopra all'altra nell'ordine in cui sono invocate. Nell'esempio, alla terza chiamata ricorsiva di printBackward ci si trova in cima allo stack una chiamata su una lista di un solo elemento. Ad uno stack si accede mediante due sole operazioni, la push (immissione) di un elemento in cima allo stack, e la pop (rimozione) di un elemento dalla cima dello stack. Una classe Stack è già disponibile in Java (e in Processing) dopo aver importato java.util.*. Essa funziona su oggetti della classe Object, che è la più generica delle classi Java, nonché superclasse di tutte. Attraversamento inverso di una lista La visita in ordine inverso, dalla coda alla testa, degli elementi di una lista si può ottenere per via ricorsiva, come già visto in . Alternativamente, si può usare uno stack come struttura dati di appoggio.

Si può notare che gli elementi della lista sono inseriti nella pila nel loro ordine naturale, essendo così estraibili da questa in ordine inverso, esiste un metodo isEmpty() della classe Stack che consente di verificare la condizione di pila vuota, è necessario fare un type casting sull'oggetto restituito dalla pop(). Questo è un generico Object in quanto la classe Stack non è in grado di conoscere il tipo dei suoi elementi. in generale è sempre possibile convertire un algoritmo ricorsivo in uno non ricorsivo facendo uso di uno stack. In questo esempio la pila viene usata in luogo del run-time stack.

Valutazione di espressioni Lo stack è anche la struttura dati che con maggior naturalezza supporta la valutazione di espressioni. Per essere più precisi, data una stringa contenente operandi e operatori in notazione postfissa, una scansione lineare della stringa accompagnata dall'utilizzazione di uno stack di appoggio può consentire una facile valutazione della espressione. E' necessario inoltre individuare i token della stringa (operandi o operatori), separati da delimitatori che tipicamente sono caratteri di spaziatura. C'è una classe di java.util, chiamata StringTokenizer, che fa proprio questo. Ad esempio, la "tokenizzazione" di una espressione in notazione postfissa si può eseguire con:

dove gli argomenti di StringTokenizer(), oltre a comprendere la stringa da analizzare, comprendono la lista dei delimitatori e un parametro boolean che indica che i separatori devono essere considerati anch'essi come token. La valutazione di espressioni su stringhe è un esempio semplice di parsing. Si costruisca un valutatore di espressioni in notazione postfissa con operatori di somma e moltiplicazione su numeri interi. Nella soluzione che segue la stringa da analizzare è scritta in testa al codice. Si fa uso del metodo equals() della classe String e del metodo parseInt() della classe Integer. Si noti inoltre il matching di espressione regolare supportato dalla classe String. In questo caso l'espressione regolare rappresenta una qualsiasi sequenza di cifre.

Lo stack delle trasformazioni geometriche Un ambito di impiego molto importante della struttura dati a stack è la grafica interattiva. In particolare, le trasformazioni geometriche che si effettuano in OpenGL avvengono per moltiplicazione matrice-vettore, e le matrici sono memorizzate sullo stack delle trasformazioni. Ciò consente di costruire modelli gerarchici di oggetti nello spazio. Nel momento in cui si fa pushMatrix() la cima della pila contiene la matrice di trasformazione geometrica che si sta applicando ad un particolare oggetto, o in altri termini lo stato corrente del sistema. Le trasformazioni applicate successivamente alla pushMatrix() vengono "dimenticate" nel momento in cui si fa una popMatrix(), in questo modo ripristinando lo stato precedente a queste ultime trasformazioni. Geometria grafica costruttiva Un semplice esempio di modello gerarchico è un braccio meccanico costituito da tre parallelepipedi: una base, un omero, e un avanbraccio. La collocazione dell'omero è fissa rispetto alla base, e di questa deve seguirne gli spostamenti. Allo stesso modo, l'avanbraccio è vincolato geometricamente all'omero. Il codice seguente disegna il braccio meccanico che è spostabile nel suo complesso mediante il mouse. Grazie all'uso dello stack, l'omero può ruotare indipendentemente dalla base restando ad essa vincolato. L'avanbraccio può ruotare indipendentemente dall'omero restando a questo vincolato.

Lettura Si legga il capitolo 15 di How to Think Like a Computer Scientist

Code La struttura dati chiamata coda (queue) organizza una politica di accesso alle informazioni analoga a quella applicata idealmente quando si fa la fila presso uno sportello. Il primo cliente ad essere servito è il primo che si è presentato alla coda dello sportello. Una coda (e in realtà anche una pila) può essere realizzata mediante una lista concatenata, consentendo in questo modo di non porre limiti alla lunghezza della coda stessa. L'accesso alla lista che supporta la coda avviene mediante un puntatore di testa e uno di coda. Inserimento in coda ed estrazione dalla coda Si può realizzare una coda mediante concatenazione di nodi e preparazione di due punti di accesso. Questo garantisce che l'accesso in inserimento ed in estrazione sia efficiente e a tempo costante. Nella realizzazione qui riportata la classe Node è atta a realizzare nodi con cargo di tipo Object generico. La presenza del metodo toString() garantirà che il nodo è stampabile.

Spesso si preferisce, per ragioni di semplicità realizzativa ed efficienza, realizzare la coda usando un array come struttura di supporto. In questo caso la crescita della coda è limitata dalla lunghezza dell'array. Questa realizzazione si chiama buffer circolare ed è impiegato, ad esempio, per la realizzazione di ritardi variabili nell'elaborazione dei segnali. Lettura Si legga il capitolo 16 di How to Think Like a Computer Scientist