0.4 Liste, pile e code

Liste

Una istanza di classe puòcontenere, tra le sue variabili, anche un puntatore ad un oggetto della classe stessa. Questoconsente di concatenare oggetti di una stessa classe, a formare strutture complesse quali liste o alberi. Inparticolare, una listaèottenuta dalla concatenazione di nodi , ciascuno dei quali contiene un puntatore al nodo successivo, nonchéun campo dati talvolta chiamato cargo .

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. Glialgoritmi ricorsivi sono definiti induttivamente stabilendo l'operazione per un elemento base (la base della ricorsione) estabilendo come utilizzare il risultato dell'elaborazione sulla lista privata di tale elemento. Inoltre, bisognaassicurarsi che l'elaborazione cosìarrangiata in maniera "telescopica" raggiunga ad un certo punto una condizione diterminazione 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: void printBackward (Node list) { if (list == null) return; // terminazione della ricorsione Node head = list; Node tail = list.next; printBackward(tail); print(head); // base della ricorsione }

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). Sinoti l'uso di un doppio metodo printBackward , uno con e uno senza argomenti, per consentire l'invocazione delmetodo sull'oggetto lista senza necessitàdi passare un puntatore alla testa della lista stessa. IntList lista; void setup() { lista = new IntList(); lista.addFirst(3); lista.addFirst(2); lista.addFirst(1); lista.printList(); lista.printBackward(); } class IntList { int length; Node head; IntList() { length = 0; head = null; } void addFirst (int i) { Node node = new Node(i, head); head = node; length++; } void printList () { Node node = head; while (node != null) { print(node); node = node.next; } println(); } void printBackward() { printBackward(head); println(); } void printBackward (Node head) { if (head == null) return; // terminazione della ricorsione Node tail = head.next; printBackward(tail); print(head); // base della ricorsione } } class Node { int cargo; Node next; Node() { cargo = 0; next = null; } Node (int cargo, Node next) { this.cargo = cargo; this.next = next; } String toString() { //rende l'oggetto di classe Node stampabile return cargo + " "; } } Questoèun esempio di classe wrapper , cioèdi confezionamento object-oriented di una struttura dati. Le classi wrapper esistono per tutti i tipi primitivi diJava ( double , int , ecc.) e consentono di creare e manipolare oggetti che contengonovalori 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. Laclasse Arrays , accessibile importando java.util.* , consente di fare operazioni di test di uguaglianza, di ricerca, e di ordinamento. Ad esempio, ilsemplice codice import java.util.*; void setup() { int[] a = new int[10]; int[] b = new int[10]; for (int i=0; i<10; i++) { a[i] = i; b[i] = i; } println(Arrays.equals(a,b)); } esegue un test di uguaglianza tra due array di interi.