1. Tipi di strutture dati fondamentali.

Struttura Dati	Descrizione / Uso principale	Implementazione tipica	Esempio concettuale
Array / Liste	Collezione di elementi dello stesso tipo, accesso per indice	Array statici o liste dinamiche	lista = [1,2,3,4]
Stack (Pila)	LIFO – “Last In, First Out”: l’ultimo elemento inserito è il primo ad uscire	Array o lista collegata	stack.append(x); stack.pop()
Queue (Coda)	FIFO – “First In, First Out”: il primo elemento inserito è il primo ad uscire	Array circolare o lista collegata	queue.append(x); queue.pop(0)
Deque (Doppia coda)	Inserimento/rimozione da entrambe le estremità	Lista doppiamente collegata	deque.appendleft(x) / deque.pop()
Lista collegata	Sequenza di nodi collegati da puntatori	Nodo (valore + puntatore)	head -> node1 -> node2 -> None
Set / Insiemi	Collezione di elementi unici	Hash table o alberi bilanciati	set([1,2,2,3]) → {1,2,3}
Map / Dizionario	Collezione chiave → valore	Hash table	diz = {“a”: 1, “b”: 2}
Albero (Tree)	Struttura gerarchica, utile per ricerche e ordinamenti	Nodi con riferimenti a figli	root -> left + right
Albero binario di ricerca (BST)	Albero ordinato per ricerche efficienti	Nodi con figlio sinistro/destro	inserisci(x) mantiene ordine
Heap / Coda prioritaria	Accesso rapido all’elemento massimo/minimo	Array con regole di heap	heapq in Python
Grafo	Collezione di nodi connessi da archi	Liste di adiacenza o matrici di adiacenza	graph = {1:[2,3], 2:[3]}

2. Concetti chiave da conoscere.

1. Operazioni base: inserimento, cancellazione, ricerca, aggiornamento.
2. Efficienza: capire il tempo di esecuzione (complessità O(n), O(log n), ecc.).
3. Implementazione: sapere come una struttura dati viene rappresentata in memoria (array vs lista collegata, hash table, ecc.).
4. Applicazioni tipiche:
   • Stack → gestione chiamate funzioni, undo/redo.
   • Queue → code in processi, BFS nei grafi.
   • Heap → algoritmi di ordinamento (heap sort), code prioritarie.
   • Grafi → reti, percorsi, algoritmi di ricerca (DFS, BFS).

Spesso gli esercizi chiedono di scegliere la struttura dati più adatta al problema e di implementarla almeno in maniera semplice. Avere schemi e piccoli esempi di codice aiuta moltissimo.