Riassunto esame Programmazione orientata agli oggetti, Prof. Nigro Libero, libro consigliato Programmazione orientata agli oggetti , Libero Nigro

APPROFONDIMENTO

Abbiamo osservato precedentemente come sia importante l’uso di una Linked List (anche nota

come Lista Concatenata) in Java.

A differenza di un banale Array, la LinkedList consente di ottenere enormi vantaggi prestazionali

sacrificando i criteri di ordinamento.

E’ cosa nota che gli Array salvino i propri elementi in memoria in modo sequenziale ed è dunque

più semplice garantire un criterio di ordinamento.

Quest’operazione, però, necessita di molto lavoro in background e dunque le prestazioni

potrebbero essere più scadenti.

La LinkedList, invece, ignora l’ordinamento in memoria e definisce ogni elemento contenuto in

essa come una coppia Informazione (nonchè dato effettivo) e Riferimento in Memoria (nonchè

Puntatore all’elemento suo successivo, anche noto come Nodo).

Tramite tale coppia di informazioni è possibile non gestire l’ordinamento in memoria ma garantire

comunque l’accesso a quei dati quando richiesto poichè si è a conoscenza della loro posizione.

Ecco qui di seguito un esempio della struttura di dati della LinkedList a confronto col banale Array:

9

7 5

3 9

Array 5

7

Array in Memoria 3

9

First 7 5

3 9

LinkedList ...

...

... Null

...

Null 5

...

7

LinkedList in

Memoria ...

3

84

13.10.1 Approfondimento sulle Linked List: Concetto di Nodo

APPROFONDIMENTO

Abbiamo dunque introdotto il Concetto di Nodo ma, cosa rappresenta effettivamente un Nodo?

Un Nodo è un “Record Allocato in Memoria” al quale è legato un Indicatore di Posizione (o

Riferimento in Memoria) e che contiene una o più informazioni (Nel nostro caso due: Dato e

Riferimento al Nodo Successivo della LinkedList corrente).

Queste informazioni, da un punto di vista sintattico della programmazione vengono definite

attraverso l’introduzione di una nuova Classe di Supporto (o Ausiliare) definita come segue:

Talvolta potremmo voler modificare la Linked List.

In quel caso è utile riprendere un concetto grafico già affrontato precedentemente che mostra cosa

succede all’elemento rimosso o comunque dopo le eventuali modifiche della lista.

Si ricordi inoltre, che tutte le operazioni interne per la modifica della LinkedList si basano sul

semplice concetto di spostamento del puntatore. Java, con il GC (Garbage Collector) farà tutto il

resto! 85

13.10.2 Approfondimento sulle Linked List: Tipica Struttura di una Linked List

APPROFONDIMENTO

La LinkedList è una Classe definita dalla struttura che segue e da tutti i suoi metodi:

13.10.3 Approfondimento sulle Linked List: Tipici Metodi → Add()

APPROFONDIMENTO

Introduciamo il metodo Add() affermando che esso sia il metodo al quale vengono delegate le

operazioni necessarie per aggiungere un valore alla Lista.

Esso distingue 4 casi specifici:

1) Inserimento in Lista Vuota

2) Inserimento Prima del Primo Elemento (Inserimento In Testa)

3) Inserimento in un Punto Intermedio Specifico

4) Inserimento Dopo dell’Ultimo Elemento (Inserimento In Coda)

13.10.4 Approfondimento sulle Linked List: Tipici Metodi → Remove()

APPROFONDIMENTO

Il metodo Remove() introduce la rimozione dell’elemento dalla lista come spiegato nei grafici

sovrastanti.

Il concetto è che il puntatore dell’elemento precedente a quello da eliminare sarà aggiornato con

l’indirizzo in memoria all’elemento successivo a quello che si voglia eliminare.

Viene dunque isolato, a questo punto, il Nodo da eliminare che sarà, poi, gestito dal Garbage

Collector. 86

13.10.5 Approfondimento sulle Linked List: Tipici Metodi →

APPROFONDIMENTO Costruttore di Copia

Il Costruttore di Copia segue la struttura qui proposta:

13.10.6 Approfondimento sulle Linked List: L’uso in un banale Main

APPROFONDIMENTO

Il costrutto per l’uso in un Main segue quanto studiato sino ad oggi pedissequamente!

13.10.7 Approfondimento sulle Linked List: L’Eccezione NullPointerException

APPROFONDIMENTO

Ritornando brevemente sul concetto di Eccezione è importante sottolineare una ricorrente

Eccezione che spesso viene sollevata lavorando con LinkedList.

Quest’Eccezione è proprio la NullPointerException ed è esattamente il corrispettivo di

IndexOutOfBoundsException per gli Array.

Essa indica che si sta cercando di lavorare su un elemento che non esiste poichè si è raggiunta e

superata la coda (parte finale) della Lista!

Bisogna dunque fare molta attenzione a questa casistica cercando di prevenirla con un controllo di

esistenza del valore richiesto prima di eseguire operazioni su di esso.

Esempio Sto iterando sugli elementi (x) della LinkedList e ad ogni giro eseguo l’operazione (x+1).

Prima di eseguire x+1 dovrei accertarmi che x esista e dunque eseguire l’operazione solo all’interno di

una condizione del tipo x != null! 87

13.10.8 Approfondimento sulle Linked List: Caso di OrderedLinkedList

APPROFONDIMENTO

Analizziamo molto brevemente l’Ipotetico caso di una OrderedLinkedList (nonché una LinkedList

Ordinata).

In tal caso sarà necessario introdurre metodi quali: get(x) per ricercare ed ottenere l’elemento su cui

lavorare per l’ordinamento.

Ma anche altri metodi ausiliari, necessari in caso diversi oltre all’ordinamento, come:

- boolean isEmpty() → verifica che la lsita sia vuota

- boolean isFull() → Verifica che la Lista sia Satura/Piena

- void clear() → Per ripulire la lista rendendola vuota (svuotarla)

- ...

13.10.9 Approfondimento sulle Linked List: Analisi dello Stack ADT

APPROFONDIMENTO

Analizziamo brevemente lo Stack ricordando che anche esso sia dotato di una vera e propria Testa

(Cima o anche Top) e che, nello specifico, proprio in testa avvengano le operazioni sugli elementi,

rispettando un criterio d’esecuzione denominato LIFO (Last In First Out) che specifica, come in

una pila di documenti, che l’ultimo elemento posto in essa (in cima) verrà analizzato come

prossimo e dunque prima degli altri pur essendo già presenti da più tempo.

Per la gestione di un ipotetico Stack si adottano metodi quali:

- push(element) → Inserisce l’elemento in cima allo Stack e solleva un’eccezione se lo Stack ha

dimensione limitata e risulta saturo al momento dell’operazione di push.

- T pop() → Rimuove e Restituisce l’elemento in cima (Top) alla Lista. Solleva eccezione se lo Stack

risulta essere vuoto (Empty).

- T top() → Ritorna (senza rimuoverlo) l’elemento in cima allo Stack. Solleva eccezione se lo Stack

risulta essere vuoto (Empty).

13.10.10 Approfondimento sulle Linked List: Analisi della Coda ADT

APPROFONDIMENTO

Analizziamo brevemente la Coda (Queue) ricordando che anche essa sia dotata di Testa (anche nota

come Cima oppure Top) e una Coda (Fine della Lista) rispettando un criterio d’esecuzione noto

come FIFO (First In First Out) il quale denota, così come avviene per un tubo in cui passa una

porzione d’acqua, che il primo elemento posto in essa (primo ad entrare) sarà anche il primo ad

essere analizzato (primo ad uscire).

Per la gestione di un ipotetica Coda si adottano metodi come:

- put(element) → Inserisce l’elemento in fondo alla Coda e solleva un’eccezione se essa ha

dimensione limitata e risulta satura al momento dell’operazione di put.

- T get() → Estrae (Rimuove) e Restituisce l’elemento in cima (Top) alla Lista. Solleva eccezione se la

Coda risulta essere vuota (Empty).

- T peek() → Ritorna (senza rimuoverlo) l’elemento in cima alla Coda. Solleva eccezione se la Coda

risulta essere vuota (Empty).

ATTENZIONE: I nomi dei metodi analizzati NON seguono uno Standard, potremmo trovarli con nomi differenti!

88

13.10.11 Approfondimento sulle Linked List: Uso di un Buffer

APPROFONDIMENTO

Abbiamo visto come talvolta potrebbe essere problematico incorrere in LinkedList Sature.

Per evitare problemi di questo prevenendoli piuttosto che curandoli è possibile introdurre l’uso di un

Buffer a Capienza Identica alla Dimensione della LinkedList.

In questo modo, pensandoci bene, avremo risolto il problema!

Ma come dovrà comportarsi il Buffer?

Beh, esso sarà utilizzato come una sorta di memoria temporanea in cui verranno salvati massimo

n elementi e, una volta raggiunta tale dimensione, nonchè limite fisico o, superato un certo lasso

di tempo, nonchè criterio di limite temporale.

Saranno inseriti questi valori nella LinkedList per poi, eventualmente, gestire la dimensione della

Lista aggiornandola con espansione.

13.10.12 Approfondimento sulle Linked List: Caso di una BothSideLinkedList

APPROFONDIMENTO

Il grande vantaggio di una LinkedList è che, se necessario, è possibile implementarne una versione a

due puntatori con un Nodo definito con la struttura che segue, in cui vengono salvati elementi quali:

- Dato Effettivo

- Indirizzo In Memoria del Nodo Precedente

- Indirizzo in Memoria del Nodo Successivo

In tal modo è possibile scorrere la Lista verso sinistra o verso destra così da muoverci più

velocemente e a seconda della convenienza.

In questo modo è possibile anche eseguire vere e proprie scansioni ad iterazione naturale o a verso

( o in senso) contrario. 89

CAPITOLO 14

Espressioni Regolari

14.0 Introduzione alle Espressioni Regolari

(Introducing Regular Expressions)

Le Regex (o Regular Expression) sono delle Regole del Linguaggio che definiscono l’identificazione

(al fine di Ricerca ed Interazione) dei Caratteri all’interno di una Stringa e consentono di eseguire

interazioni molto rapide ed efficaci.

Esse vengano impiegate per la ricerca di parole chiave, la verifica dei contenuti e delle condizioni

o talvolta per la modifica veloce di parti specifiche interne ad una stringa.

In java, il criterio di ricerca viene definito da un pattern (o schema) che si occuperà di definire le

regole della ricerca stessa per poi verificare che la stringa rispetti le condizioni imposte dallo

schema o meno.

14.1 Alcuni Esempi di Regex

(Some Regex Example)

[013] indica le singole cifre 0, 1 e 3.

[0-9] indica tutti i valori da 0 a 9.

[0-9][0-9] indica tutte le coppie valore da 00 a 99.

A[0-4]B[05] indica una stringa che inizia per A, è seguita da un valore compreso tra 0 e 4 e termina

con 0 oppure 5.

[0-9&&[ˆ4567]] indica un qualsiasi valore compreso fra 0 e 9 escludendo i valori 4,5,6 e 7.

[a-z][A-Z] indica una coppia di lettere in cui il primo carattere sarà una minuscola compresa tra a e z.

Il secondo carattere deve essere compreso tra A e Z.

[ˆabc] indica un qualsiasi carattere eccetto a, b oppure c.

[a-z&&[ˆaeiou]] indica una consonante minuscola poiché escludiam