Liste concatenate (a puntatori): semplice, circolare, con testa e coda, bidirezionale, multipla.
Lista semplice
Puntatore di testa e tre nodi con informazioni A-B-C
Lista con testa e coda
Puntatore di testa e puntatore di coda
Lista circolare
L’ultimo nodo punta alla testa
Il nodo iniziale è meglio che sia l’ultimo…
Lista bidirezionale
A doppi puntatori: nei nodi puntatori nelle due direzioni
Lista multipla
Una possibile combinazione è la seguente
- lista primaria con puntatore di testa e puntatore di coda, bidirezionale e con puntatori alle liste secondarie: A-B-C
- liste secondarie semplici: p, q-r-s
Operazioni
Le operazioni più comuni per qualsiasi tipo di lista
Aggiungere un nodo
- In testa / in coda / in ordine
- Prima di un certo nodo / dopo un certo nodo
Visitare la lista per
- Visualizzare il contenuto
- Calcolare minimo / massimo / totale / media …
- Contare quante volte compare una certa informazione
- Trovare la posizione di una certa informazione
- È ordinata?
Eliminare un nodo
- In testa / in coda
- Con un certo valore / con un certo puntatore
- Prima di un certo nodo / dopo un certo nodo
- Eliminare tutti i nodi
Date due liste
- Hanno la stessa lunghezza? / Hanno lo stesso contenuto?
- Appendere alla fine della prima una copia della seconda
- Concatenare l’inizio della seconda alla fine della prima
Ordinamento
- Ordinare due nodi rispetto al contenuto
- Ordinare la lista
- Date due liste ordinate fonderle in una terza ordinata
Puntatori
Aggiungendo gli opportuni campi per i puntatori…
