COLLEZIONI E GENERICITalk 2

COLLEZIONI

LE COLLEZIONI SONO STRUTTURE DATI

• Programmare non è più solo scrivere algoritmi ma permettere a strutture dati diverse di interagire tra loro.

• Una struttura dati è un modo di organizzare informazioni per permetterne un uso efficiente (Wikipedia).

ORGANIZZARE INFORMAZIONI

• Singnifica dare ai miei dati una struttura. Dipende da come sono fatti.

• Dipende da cosa devo farci!

• Insiemi lineari: per un accesso casuale a dati omogenei.

• Mappe: per creare associazioni tra chiavi e valori.

• Alberi: per gestire strutture ricorsive.

• Code: first-in, first-out.

• Stack: last-in, first-out.

STRUTTURE DATI NELLA VITA VERA

• L’elenco del telefono è un dizionario.

• Il vocabolario è un dizionario.

• Gli indici delle Pagine Gialle formano un albero.

• Il cestone dei giochi è uno stack.

• Al semaforo c’è la coda.

COLLEZIONI

Insieme Lista Mappa Stack Queue

DIGRESSIONE: LA NOTAZIONE O(...)

f(x) è O(g(x)) se esistono c > 0 e un x0 tali che f(x) < c g(x) per x > x0

1000000n^2 + 1000000n + 1000 è O(n^2)

INSIEMI - SET

• Una collezione non ordinata di elementi omogenei.

• Non ha senso la ricerca per indice.

• Non contiene duplicati.

• Inserimenti e rimozioni lenti O(log n), ricerche veloci O(log n).

LISTE

• Collezione ordinata di elementi omogenei.

• Permette la ricerca per indice.

• Supporta elementi vuoti e duplicati.

LISTE BASATE SU ARRAY

• Aggiunte velocissime O(1) a meno che non sia necessario ingrandire la lista (richiede la duplicazione dell’array).

• Inserimenti e rimozioni lentissimi (richiede la duplicazione dell’array).

• Ricerche lentissime O(n).

• Ricerche per indice velocissime O(1).

LISTE CONCATENATE

• Aggiunte velocissime O(1) e costanti.

• Inserimenti e rimozioni lenti O(n).

• Ricerche lente O(n).

• Ricerche per indice lente O(n).

MAPPE

• È un insieme di coppie chiave-valore.

• Ricerca per chiave veloce O(log n).

• Ricerca per valore impossibile.

• Non permette chiavi vuote o duplicate.

• Permette valori vuoti o duplicati.

STACK

• Variante della lista.

• Realizza LIFO: push() e pop().

• Ambedue le operazioni sono O(1).

QUEUE

• Variante della lista.

• Realizza FIFO: add() e remove().

• Ambedue le operazioni sono O(1).

ABBIAMO VISTO

• Complessità computazionale.

• Varie collezioni.

GENERICISyntactic sugar

PROBLEMAclass List {! public void add(Object obj) {! ...! }! public Object get(int index) {! ...! }!}!!//==============================!List list = new List();!list.add(new Pippo());!!Pippo pippo = list.get(0);

Pippo pippo = (Pippo) list.get(0);

IL PROBLEMA CRESCE

List list = new List();!list.add(new Pippo());!Pippo pippo = (Pippo) list.get(0);!!//===================================!list.add(new Pluto());!Pippo pippo = (Pippo) list.get(1);

SOLUZIONE

class List<T> {! public void add(T obj) {! ...! }! public T get(int index) {! ...! }!}

SOLUZIONE

List<Pippo> list = new List<Pippo>();!list.add(new Pippo());!Pippo pippo = list.get(0);

list.add(new Pluto());

List<Pluto> list2 = new List<Pluto>();!list2.add(new Pluto());!Pluto pluto = list2.get(0);

ESERCIZIO

• Implementate una lista concatenata generica. Adesso.

DOMANDE?

Prossima puntata: Iterazione e ricorsione. Stay tuned!