Java Collections – Parte I

In questa prima parte del tutorial sulle collection Java dopo una breve introduzione parleremo di Array e liste di oggetti. Vedremo le varie classi che implementano l’interfaccia Java List con vari esempi che ne spiegano l’utilizzo.

Nel tutorial Oracle una collection è definita come:

A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data. Typically, they represent data items that form a natural group, such as a poker hand (a collection of cards), a mail folder (a collection of letters), or a telephone directory (a mapping of names to phone numbers).

In Java il framework che permette di gestire le collection mette a disposizione:

interfacce

definizioni di interfacce che permettono di manipolare collezioni di oggetti indipendentemente dai dettagli implementativi

implementazioni

classi concrete che implementano le varie interfacce

algoritmi

funzionalità riusabili per eseguire operazioni comune (per esempio la ricerca o l’ordinamento)

Array

Gli Array non sono contenuti nel framework delle collection, ma a volte possono essere utilizzati al posto di una collection. Gli Array sono oggetti ma non contengono metodi utili a parte il campo in sola lettura length. Di solito vengono usati quando si conosce il numero massimo degli oggetti contenuti, infatti sono a dimensione fissa: se si cerca di accedere una posizione errata viene generata una ArrayIndexOutOfBoundException.

Gli Array sono tipati ma ci possono essere comunque dei problemi runtime:

Object[] objectArray = new Long[1];
objectArray[0] = "I don't fit in"; // Throws ArrayStoreException

In ambito mobile (per esempio su Android) viene fatto un largo uso degli Array per questioni di performance. Solitamente utilizzando gli Array si scrive codice più performante e che occupa meno memoria rispetto allo stesso codice scritto usando le collection.

Un esempio di utilizzo degli Array è il seguente (da notare che possono essere creati sia Array di tipi primitivi che di oggetti):

int[] arrayInt = new int[10];
arrayInt[5] = 12345;
System.out.println(arrayInt.length);
for (int i = 0; i < arrayInt.length; i++) {
    System.out.println(arrayInt[i]);
}
Persona[] arrayPersone = new Persona[10];
System.out.println(arrayPersone.length);
for (int i = 0; i < arrayPersone.length; i++) {
    System.out.println(arrayPersone[i]);
}
for (int i = 0; i < 10; i++) {
    arrayPersone[i] = new Persona(i, "nome" + i, "cognome" + i);
}
for (int i = 0; i < arrayPersone.length; i++) {
    System.out.println(arrayPersone[i]);
}

Interfacce principali

Le principali interfacce sono Collection, List, Set e Map. Le interfacce List e Set estendono Collection:

Per scrivere codice indipendente dall’implementazione e aumentare la riusabilità è sempre buona norma utilizzare l’interfaccia più generica possibile per definire variabili, campi e parametri di metodi.

Prendiamo per esempio il seguente metodo:

public boolean isBig(ArrayList<?> l) {
	return l.size() > 100;
}

Il parametro è definito come ArrayList, ma in realtà usa solo un metodo definito nell’interfaccia Collection. Definendo il parametro come di tipo Collection il metodo può essere usato non solo con un ArrayList ma anche con tutte le altre implementazioni di Collection.

Stesso discorso può essere fatto per i metodi get di una classe: ritornare una interfaccia generica permette di cambiare l’implementazione utilizzata in un secondo momento senza impatti sulle classi che utilizzano la classe modificata.

Collection

Collection è l’interfaccia più generica, non definisce nè l’ordine in cui sono memorizzati gli elementi nè se ci possono essere elementi duplicati.

A differenza degli Array tutte le collection non possono contenere tipi primitivi ma solamente oggetti, per inserire tipi primitivi è necessario usare un oggetto wrapper (per esempio Integer al posto di int):

public void test(Collection<Integer> c) {
	c.add(new Integer(1));
	c.add(new Integer(5));
	c.add(new Integer(7));
	c.remove(new Integer(5));
	System.out.println(c.size() == 2);
}

A partire da Java 1.5 c’è la conversione automatica (auto boxing e unboxing) dei wrapper in tipi primitivi che semplifica la scrittura del codice:

public void test(Collection<Integer> c) {
	c.add(1);
	c.add(5);
	c.add(7);
	c.remove(5);
	System.out.println(c.size() == 2);
}

List

Un oggetto List contiene oggetti ordinati in base all’ordine di inserimento, può contenere duplicati e permette di inserire e ottenere gli elementi in base all’indice. E’ la versione “evoluta” di un Array in quanto non contiene la limitazione della dimensione massima prefissata.

public void test(List<String> c) {
	c.add("aaa");
	c.add("bbb");
	c.add(1, "ccc");
	c.remove("aaa");
	System.out.println(c.get(1).equals("bbb"));
}

ArrayList

ArrayList è l’implementazione di List che memorizza gli elementi in un Array, si occupa della gestione della dimensione dell’Array in modo trasparente per lo sviluppatore. Ogni volta che l’Array è pieno viene invocato il metodo ensureCapacity che crea un nuovo Array di dimensione (old *3) / 2 +1 in cui vengono copiati tutti gli elementi presenti usando il metodo Arrays.copyOf.

Per evitare ridimensionamenti se si conosce già la dimensione massima può essere specificata nel costruttore.

Visto che i dati sono memorizzati in un Array l’accesso all’i-esimo elemento è veloce. Per lo stesso motivo l’operazione di rimozione di un elemento è lenta, tutti gli elementi successivi all’elemento da eliminare devono essere spostati di una posizione.

LinkedList

LinkeList è l’implementazione di List che usa una lista linkata bidirezionale, permette di scorrere gli elementi partendo sia dall’inizio che dalla fine.
Accedere all’i-esimo elemento è un’operazione lenta, infatti devono essere percorsi tutti gli elementi precedenti; l’operazione di rimozione è invece veloce, in quanto non devono essere spostati oggetti, ma prevede solo il cambiamento di alcuni collegamenti fra i nodi della lista.

Vector

Vector è una implementazione di List ormai obsoleta (risale al jdk 1.0), è simile ad ArrayList ma sincronizzata (può essere usata da più thread paralleli senza problemi di concorrenza). Anche il JavaDoc di Vector ne sconsigla l’utilizzo:

Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector

Anche nel caso si voglia manipolare una collection da thread diversi può essere usata una qualsiasi Collection che può essere resa sincronizzata usando il metodo Collections.synchronizedCollection.

Iterator

La classe Iterator è il modo standard per scorrere gli elementi di una qualunque Collection. Contiene 3 metodi:

hasNext

ritorna true se ci sono ancora elementi da scorrere

next

ritorna il successivo elemento

remove

rimuove dalla collection l’ultimo elemento ritornato. Questo metodo deve essere usato quando si vuole rimuovere un oggetto da una Collection durante un ciclo sugli elementi. Infatti in questi casi chiamare il metodo remove di Collection causa una ConcurrentModificationException al successivo accesso alla lista

Senza iterator una lista potrebbe essere visitata così:

public static int sumLessThen(List<Integer> l, int max) {
	int tot = 0;
	for (int i = 0; i < l.size(); i++) {
		Integer tmp = l.get(i);
		if (tmp != null && tmp.intValue() < max) {
			tot += tmp;
		}
	}
	return tot;
}

Se la lista passata è una LinkedList questo metodo è poco efficiente (per ogni elemento il metodo get riparte dall’inizio). Usando un iterator il metodo può essere riscritto come:

public static int sumLessThen(List<Integer> l, int max) {
	int tot = 0;
	for (Iterator iterator = l.iterator(); iterator.hasNext();) {
		Integer tmp = iterator.next();
		if (tmp != null && tmp.intValue() < max) {
			tot += tmp;
		}
	}
	return tot;
}

Da Java 1.5 è stato introdotto un nuovo costrutto for, denominato foreach, che può essere usato con tutti gli oggetti che implementano l’interfaccia Iterable e con gli Array:

List<Integer> l = Arrays.asList(4, 8, 15, 16, 23, 42);
int tot = 0;
for (Integer i : l) {
	tot += i;
}
Integer[] a = new Integer[6];
a[0] = 4;
a[1] = 8;
a[2] = 15;
a[3] = 16;
a[4] = 23;
a[5] = 42;
tot = 0;
for (Integer i : a) {
	tot += i;
}

Conclusioni

Finisce qui la prima parte di questo tutorial sulle collection in Java; nella seconda parte vedremo nel dettaglio i Set e le Map con vari esempi di utilizzo.