Strutture dati: List, Set, Map

DOMANDA:

Che differenza c'è fra List, Set e Map? Quale devo usare?

RISPOSTA:

Un Data Structure è una struttura ottimizzata per collezionare dati. List e Set sono strutture dati che estendono Collection mentre Map vive indipendentemente. Una Collection è un contenitore di un insieme di valori, una sorta di array dinamico. A seconda dell'utilità, si possono usare diverse implementazioni dell'interfaccia Collection. Essa infine può essere tipizzata, ossia contenere solo dati di un certo tipo, tale tipo si indica attraverso i Generics (indicandolo fra parentesi angolari). Siccome il tipo è un oggetto, per esprimere primitivi come int bisogna usare i wrapper come Integer.

List

• Contiene dati ordinati.
• I duplicati sono permessi.
• Aggiunge un elemento: add(Object obj).
• Accede ad un elemento: get(int index).
• Rimuove un elemento: remove(Object obj) o remove(int index).

Le List servono nel caso in cui i dati possano essere duplicati. Due comportamenti analoghi di List sono Stack (pila) e Queue (coda) che implementano il paradigma LIFO (Last In First Out) e FIFO (First In First Out), in cui l'accesso ai dati è permesso soltanto sul primo elemento.

Esempio:

List<String> list = new ArrayList<String>();
list.add("ciao");
list.add("mondo");
list.add("ciao");
     
for(int i = 0; i < list.size(); i++)
     System.out.println(list.get(i));

Output:

ciao
mondo
ciao

Set

• Contiene dati non necessariamente ordinati.
• I duplicati non sono permessi.
• Aggiunge un elemento: add(Object obj).
• Accede ad un elemento con l'Iterator.
• Rimuove un elemento: remove(Object obj).

I Set si utilizzano nel caso in cui i dati non devono avere valori replicati. Benché i set non siano ordinati, esiste l'interfaccia SortedSet che estende Set in cui gli elementi sono ordinati. HashSet è una classe implementante.

Esempio:

Set<String> set = new HashSet<String>();
set.add("ciao");
set.add("mondo");
set.add("ciao");

for(String s : set)
    System.out.println(s);

Output:

mondo
ciao

Map

• I dati contenuti sono indicizzati tramite chiave e valore.
• Non contiene chiavi duplicate, ogni chiave ha al massimo un valore.
• Contiene dati non necessariamente ordinati.
• Aggiunge un elemento: put(Object key, Object value).
• Acccede ad un valore: get(Object key).
• Accede a tutti i valori: values().
• Accede a tutte le chiavi: keySet().
• Rimuove un elemento: remove(Object key).

La filosofia della Map è quella di salvare una coppia chiave - valore. L'informazione "importante" è il valore, mentre la possibilità di accesso a tale valore è la chiave. Benché i dati non siano ordinati nell'interfaccia Map, proprio come per i Set esiste SortedMap la cui implementazione è TreeMap in cui i valori sono ordinati per chiave.

La Map non è iterabile, ma si può accedere sia alla lista delle chiavi o alla lista dei valori per poterli iterare singolarmente.

Esempio:

Map<String, String> map = new TreeMap<String, String>();
map.put("Nome", "Mario");
map.put("Cognome", "Rossi");
map.put("Cognome", "Rossi");
map.put("Numero", "123456789");

for(String s : map.values())
    System.out.println(s);

System.out.println(map.get("Nome"));

Output:

Rossi
Mario
123456789
Mario

Da notare come la Map sia ordinata per chiave e non per valore, per cui nella stampa appare Cognome, Nome, Numero.