Le strutture dati introdotte nel nostro corso:

(work in progress)
Strutture elementari

1. liste

   
   Una lista è una sequenza finita di oggetti di un qualche tipo. Le operazioni canoniche sulle liste sono l'inserimento, la ricerca e la cancellazione. Nell'implementazione canonica si usano liste concatenate (o doppiamente concatenate).
   Se la lista viene mantenuta ordinata l'inserimento costa O(n^2), la ricerca O(n), la cancellazione O(n). Se la lista
   non é ordinata l'inserimento in testa o in coda costa O(1), la ricerca e la cancellazione O(n). In entrambi i casi il costo della cancellazione è dovuto alla ricerca che deve rinvenire l'elemento da cancellare.
   
   

2. pile

   Una pila è una lista il cui accesso è limitato alll'inserimento ed all'estrazione in testa alla pila (lista). Le operazioni di push, pop prendono tempo O(1). E' possibile definire un'operazione head che legge in O(1) la testa della pila senza estrarne l'elemento.
   
   

3. code

   Anche le code possono essere realizzate come liste ad accesso limitato. In questo caso sono consentiti esclusivamente l'inserimento in coda (per l'appunto) e l'estrazione in testa, più eventualmente un'operazione di peek ("sbirciare" la testa) analoga alla precedente. enqueue, peek e dequeue prendono tempo O(1).

Strutture per la rappresentazione di insiemi (op. Union & Find)
Grafi
Alberi