Informatica I - L'ADT Vettore

Liste posizionali e liste con rango (vettori)

Vettore

Vettore: è una lista con rango. Le operazioni più generali che vogliamo effettuare su una lista riguardano l’inserimento e l’eliminazione di un nuovo elemento in una posizione qualsiasi. La posizione di un elemento nella lista può essere indicata:

• In modo relativo attraverso un iteratore
• In modo assoluto attraverso il rango di un elemento

Rango

Rango: è un indice che possiamo definire ricorsivamente

• Ha valore 0 per il primo elemento della lista
• Ha valore i+1 per l’elemento che segue l’elemento di rango i

Il tipo di dato astratto “vettore” e il tipo di dato astratto “lista” hanno astrazioni diverse. Un vettore è una sequenza ordinata di dati, ciascuno accessibile mediante un indice intero (il rango). Un vettore consente quindi l’accesso casuale a tutti gli elementi tramite l’uso di indici. Una lista è una sequenza ordinata di dati, accessibili in sequenza mediante un iteratore. Una lista consente solamente accesso sequenziale ai propri elementi.

L'ADT vettore

L'ADT vettore è una generalizzazione/astrazione del concetto di array:

• Ha una lunghezza variabile
• È possibile aggiungere e togliere elementi in qualsiasi posizione del vettore
• È possibile accedere (in lettura e scrittura) al valore di un elemento noto il suo rango

Un modo naturale per realizzare l'ADT vettore è quello di utilizzare un array riempito solo in parte. In java.util esiste la classe ArrayList, che realizza una lista con rango e con una ricca dotazione di funzionalità.

Vettori e liste: efficienza operazioni

L'efficienza delle operazioni fondamentali cambia se la posizione è specificata tramite rango o iteratore:

• Con rango: l'accesso richiede tempo costante, ma inserimenti e rimozioni comportano in media lo spostamento di n/2 elementi, cioè tempo O(n).
• Con iteratore: l'accesso richiede tempo lineare O(n) (bisogna scorrere la lista dall'inizio), ma inserimenti e rimozioni comportano un numero costante di operazioni.