List, Map, Queue e Set

In java, una collection è un insieme di oggetti contenuti all’interno di un singolo oggetto, il Java Collection Framework è un set di classi contenute nel package java.util che definisce 4 interfacce :

  • List – lista ordinata di oggetti che permette la presenza di duplicati, gli elementi sono accessibili per mezzo di un indice
  • Set – lista che non permette la presenza di duplicati
  • Queue – è una collection che ordina gli elementi in base al loro utilizzo, in genere si usa in FIFO, First In First Out, ma è possibile processarla in maniera differente
  • Map – è una collection che associa una chiave ad un elemento

Solo una precisazione, tutte queste interfacce estendono Collection tranne Map, Map fa parte del Java Collection Framework ma non implementa Collection

Metodi comuni dell’interfaccia Collection

add()

inserisce un elemento all’interno di una collection, e ritorna un boolean per indicare il successo o meno dell’operazione

boolean add(E element);

Notiamo che utilizza i generics e che il risultato, per alcuni tipi di collection sarà sempre true, mentre per altri potrebbe indicare false

vediamo un piccolo esempio :

List<String> lista = new ArrayList<>();
System.out.println(lista.add("ciao")); //true
System.out.println(lista.add("ciao")); //true

Set<String> set = new HashSet<>();
System.out.println(set.add("ciao")); //true
System.out.println(set.add("ciao")); //false

List permette duplicati, quindi restituirà sempre true, Set non permette duplicati, di fatto la seconda chiamata di add restituirà false poichè la stringa ciao è già presente

remove()

Serve per rimuovere un oggetto da una collection, restituisce un valore booleano per rappresentare il successo o meno dell’operazione

boolean remove(Object o);

vediamo un pratico utilizzo

List<String> lista = new ArrayList<>(); 
lista.add("ciao");
lista.add("ciao");
System.out.println(lista.remove("pippo")); // false
System.out.println(lista.remove("ciao")); // true
System.out.println(lista); // [ciao]

La prima chiamata di remove restituisce false poichè pippo non è presente nella lista, la seconda, restituisce true poichè trova la stringa ciao e rimuove la prima occorrenza

Facciamo attenzione che il metodo remove è overloadato, esiste un metodo remove(int i) che accetta un intero rappresentante l’indice dell’elemento da rimuovere

isEmpty() e size()

sono metodi che ci forniscono  informazioni sullo stato della nostra collection

boolean isEmpty()
int size();

Vediamo un esempio :

System.out.println(lista.isEmpty()); //true
System.out.println(lista.size()); //0
lista.add("ciao");
lista.add("ciao");
System.out.println(lista.isEmpty()); //false
System.out.println(lista.size()); //2

clear()

rimuove tutti gli elementi presenti nella collection

void clear()

Vediamo un esempio :

lista.add("ciao");
lista.add("ciao");
System.out.println(lista.isEmpty()); //false
System.out.println(lista.size()); //2
lista.clear();
System.out.println(lista.isEmpty()); //true
System.out.println(lista.size()); //0

Usare l’interfaccia List

Si utilizza una lista quando si vuole una collection ordinata di elementi dove è possibile la presenza di elementi duplicati.

Gli elementi sono disponibili sempre tutti e possono essere reperiti tramite un indice, vediamo ora le classi principali che implementano List

  • ArrayList – è un array autoincrementale, ogni elemento aggiunto fa aumentare la capacità, il suo vantaggio è che può cercare gli elementi in un tempo T sempre costante, ma di fatto è più lenta nell’inserimento o rimozione di un elemento, di fatto è consigliabile utilizzarla quando si ha la necessità di leggere molto spesso il contenuto e poco di modificarlo.
  • LinkedList – Implementa sia List che Queue, di fatto fornisce metodi di utilità per rimuovere o aggiungere elementi all’inizio o in coda , permette di leggere, aggiungere e rimuovere elementi all’inizio o alla fine della collection in un tempo T costante
  • Vector – Implementazione vecchia di java 1.2, rimpiazzato da ArrayList, fa le stesse cose di ArrayList ma in maniera molto più lenta poichè è thread-safe
  • Stack – Struttura per aggiungere o rimuovere elementi dalla testa alla coda, di fatto Stack estende Vector ed il suo utilizzo è sconsigliato, è stata sostituita da ArrayDeque

Metodi principali di List

Metodo Descrizione
boolean add(E element) aggiunge un elemento
void add(int intex, E element) aggiunge elemento a posizione index e sposta gli elementi a destra
E get(int index) restituisce E a posizione index
int indexOf(Object o) Restituisce indice del primo elemento trovato, -1 se non trovato
int lastIndexOf(Object o) Restituisce l’ultima occorrenza di o, -1 se non trovato
boolean remove(E element) Rimuove element e sposta i rimanenti a sinistra
E set(int index, E element) Sostituisce element alla posizione index

 

Vediamo un esempio pratico :

List<String> lista = new ArrayList<>();
lista.add("carlo");  // [carlo]
lista.add(0, "roma"); // [roma, carlo]
lista.set(1, "lazio"); // [roma, lazio]
lista.remove("roma"); // [lazio]
lista.remove(0); // []

Questo esempio è molto semplice, vediamo come l’arraylist si adatta alle dimensioni in base alle nostre operazioni, vediamo un esempio più completo :

lista.add("roma"); // [roma]
lista.add("milano"); // [roma, milano]
lista.add("venezia"); // [roma, milano, venezia]
String citta = lista.get(0); //roma
int index = lista.indexOf("venezia"); // 2

Questi esempio possono essere modificati utilizzando LinkedList, Vector e Stack

Utilizzare l’interfaccia Set

Set si utilizza quando abbiamo la necessità di avere una lista ordinata dove non ci siano elementi duplicati, ricordiamo che il test di eguaglianza viene effettuato invocando i metodi hashCode e equals, notiamo bene che se la nostra classe non implementa correttamente hashCode il metodo equals non verrà invocato, ripassiamo quindi le regole per overridare hashCode e equals !

Queste sono le implementazioni più comuni di Set

  • HashSet – memorizza gli elementi in una HashTable, significa che utilizza il metodo hashCode per individuare più velocemente gli elementi. L’aggiunta e la ricerca di elementi avviene in un tempo T costante, l’unico svantaggio è che si perde l’ordine di inserimento degli elementi.
  • TreeSet – memorizza gli elementi in una struttura ad albero, ha il vantaggio di mantenere la collection ordinata, l’aggiunta e la ricerca di elementi avviene in un tempo T(log n), TreeSet implementa l’interfaccia NavigableSet

Metodi principali di Set

Vediamo un esempio per capire le differenze di Set con List

Set<Integer> set = new HashSet<>();
boolean b1 = set.add(66); //true
boolean b2 = set.add(10); //true
boolean b3 = set.add(66); //false
boolean b4 = set.add(8); //true
for (Integer i : set) 
  System.out.print(i + " ");  // 66 10 8

L’unica differenza sta nel fatto che la seconda add(66) restituisce false, poichè l’integer 66 è già presente nel Set

Come detto prima, viene utilizzato hashCode e equals per stabilire l’eguaglianza, se hashCode restituisce un valore differente, equals non verrà invocato

Vediamo ora un esempio con TreeSet

Set<Integer> set = new TreeSet<>();
boolean b1 = set.add(66); //true
boolean b2 = set.add(10); //true
boolean b3 = set.add(66); //false
boolean b4 = set.add(8);
for (Integer i : set) 
  System.out.println(i + " "); // 8 10 66

Notiamo che ora, gli elementi sono stampati secondo l’ordine naturale, Integer implementa l’interfaccia Comparable che Java utilizza per il sort

Abbiamo detto che TreeSet implementa anche NavigableSet, vediamo alcuni metodi interessanti :

E lower(E e) Ritorna l’elemento più grande che è < di e, null se non c’è
E floor(E e) Ritorna l’elemento più grande che è <= di e, null se non c’è
E ceiling(E e) Ritorna l’elemento più piccolo che è >= di e, null se non c’è
E higher(E e) Ritorna l’elemento più piccolo che è > di e, null se non c’è

Vediamo un esempio per capire meglio :

NavigableSet<Integer> set = new TreeSet<>();
for (int i=1 ; i <= 20 ; i++) 
  set.add(i);
System.out.println(set.lower(10)); // 9
System.out.println(set.floor(10)); // 10
System.out.println(set.ceiling(20)); // 20
System.out.println(set.higher(20)); //null

Utilizzo dell’interfaccia Queue

Si utilizza una coda quando gli elementi sono aggiunti o rimossi secondo un ben preciso ordine, tipicamente sono utilizzate per elementi che debbono essere processati in fila, nella vita reale è come una fila di persone.

La classe che implementa l’interfaccia Queue è ArrayDeque, che è un pura coda a doppia fine, è molto più efficiente di LinkedList (che implementa sia List che Queue)

Metodi principali di Queue

Contiene molti metodi, è bene memorizzare ed imparare ad utilizzare questi metodi :

Metodo Descrizione Per Queue Per Stack
boolean add(E element) Aggiunge un elemento in coda e ritorna true o un Exception Si No
E element() ritorna il prossimo elemento o una Exception se la coda è vuota Si No
boolean offer(E e) Aggiunge e in coda Si No
E remove() Rimuove e ritorna il prossimo elemento, Exception se la coda è vuota Si No
void push(E e) aggiunge E in testa alla coda No Si
E poll() Rimuove e ritorna il prossimo elemento, null se la lista è vuota Si No
E peek() Ritorna il prossimo elemento, null se la lista è vuota Si No
E pop() Rimuove e ritorna il prossimo elemento, null se la coda è vuota No Si

 

Tranne push e pop, tutti questi metodi sono di Queue, notiamo che alcuni lanciano exception se non ci sono elementi, altri restituiscono null

Vediamo un esempio di utilizzo di Queue :

Queue<Integer> queue = new ArrayDeque<>();
System.out.println(queue.offer(10)); //true, mette 10 in coda
System.out.println(queue.offer(4)); //true, mette 4 in coda
System.out.println(queue.peek()); //10, torna il primo elemento senza rimoverlo
System.out.println(queue.poll()); //10, torna il primo elemento e lo rimuove
System.out.println(queue.poll()); //4, torna il primo elemento e lo rimuove
System.out.println(queue.peek()); //null, l'istruzione di prima ha svuotato la coda
System.out.println(queue.element()); //Exception !

Ricordiamo solamente che ArrayDeque è una coda a doppio senso, si possono aggiungere elementi in testa o in coda, si può invocate push per aggiungere un elemento in testa

Quando si parla di stack si parla di solito di LIFO (Last In First Out) e si usano i metodi : push/poll/peek

Quando si parla di code si parla di solito di FIFO (First In First Out) e si usano i metodi : offer/poll/peek

Riscriviamo l’esempio usando ArrayDeque come uno stack :

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(10); //mette 10
stack.push(4);  //mette 4 davanti a 10
System.out.println(stack.peek()); // 4 - da il primo elemento senza rimuoverlo
System.out.println(stack.poll()); // 4 - da il primo elemento e lo rimuove
System.out.println(stack.pool()); // 10 - da il primo elemento e lo rimuove
System.out.println(stack.peek()); // null, lo stack è vuoto

Map

Si usa una mappa quando un elemento è identificato da una chiave, le Map non implementano Collection e hanno un set di metodi differenti per aggiungere / rimuovere e settare elementi

  • HashMap – memorizza le chiavi in un hashtable, utilizza quindi hashCode per accedere alle chiavi in maniera efficiente, può aggiungere e ritornare valori in un tempo T costante, ma si perde l’ordinamento sull’inserimento degli oggetti
  • TreeMap – memorizza le chiavi in una struttura ordinata, come contro ha il fatto che il reperimento e inserimento è T(log n)
  • LinkedHashMap –
  • Hashtable – vecchia implementazione, thread safe

Metodi di Map

Molti metodi di Map utilizzano chiave / valore (K, V)

void clear() rimuove tutte le chiavi e i valori
boolean isEmpty() Ritorna true se la mappa è vuota
int size() ritorna il numero di occorrenze
V get(Object key) Ritorna il valore sotto la chiave key, null se non presente
V put(K key, V value) Aggiunge o Sostituisce l’elemento V alla chiave K
V remove(K key) Rimuove l’oggetto con chiave k, null se non c’è
boolean containsKey(Object key) Ritorna true se è presente la chiave key
boolean containsValue(Object v) Ritorna true se è presente l’oggetto v
Set<K> keySet Ritorna un Set delle chiavi
Collection<V> values() Ritorna una collection dei valori

 

Vediamo un pò di esempi :

Map<String, String> map = new HashMap<>();
map.put("koala","bamboo");
map.put("leone","carne");
map.put("giraffa","foglie");
String cibo = map.get("giraffa"); //foglie
for (String key : map.keySet()) 
  System.out.println(key + ","); //koala,giraffa,leone

Vediamo un utilizzo di TreeMap che tiene le chiavi ordinate, utilizzando al solito hashCode

Map<String, String> map = new TreeMap<>();
map.put("carlo","bamboo");
map.put("andrea","carne");
map.put("mario","foglie");
String cibo = map.get("mario"); //foglie
for (String key : map.keySet()) 
 System.out.println(key + ","); //andrea, carlo, mario

Facciamo attenzione a non farci fregare ! se vediamo una cosa del genere :

if (map.contains("pippo"))

Questo è un errore di compilazione ! Map non implementa collection e non ha un metodo contains ma bensi containsKey o containsValue

Riepilogo e confronto

Vediamo una tabella riassuntiva e comparativa delle interfacce collection di Java

Tipo Duplicati ammessi ? Elementi Ordinati ? Chiave / Valore ? Si deve aggiungere/rimuove in ordine specifico ?
List Si Si (dall’indice) No No
Map Si (solo per i valori) No Si No
Queue Si Si (ordine specifico) No Si
Set No No No No

 

Vediamo una tabella riassuntiva e comparativa delle classi più utilizzate

Tipo Interfaccia Ordinato ? Chiama hashCode Chiama compareTo
ArrayList List No No No
ArrayDeque Queue No No No
HashMap Map No Si No
HashSet Set No Si No
Hashtable Map No Si No
LinkedList List, Queue No No No
Stack List No No No
TreeMap Map Si No Si
TreeSet Set Si No Si
Vector List No No No

 

Ricordiamo che alcune strutture dati permettono la restituzione di null, altre no, ma il perchè di questo ha una spiegazione logica, tutte le collection che permettono l’ordinamento non possono contenere valori null !

Inoltre, ArrayDeque non può contenere null poichè null è un valore di ritorno per i metodi come poll() 

Questo è il  riepilogo :

  • TreeMap – No null
  • Hashtable . No chiavi null o valori
  • TreeSet – No valori null
  • ArrayDeque – No valori null