nikpez di nikpez
Ominide 738 punti

Teoria liste

La struttura concatenata
Nella struttura concatenata l’ordine logico degli elementi è ricostruito tramite dei puntatori (link) che indicano, per ogni
elemento, la posizione del suo successore.

ADT Lista - Definizione
Una lista è una successione di elementi collegati in modo che ognuno, tranne il 1° e l’ultimo, abbia un solo successore ed un
solo predecessore.

ADT Lista – Proprietà/Caratteristiche
- Struttura dati lineare
- Struttura dati dinamica
- Può essere vuota: P0
- Accesso strettamente sequenziale (solo ricerca sequenziale)
- Sequenza logica indipendente da allocazione fisica: due elementi logicamente contigui possono occupare locazioni di memoria anche distanti tra loro.
- Inserimento e cancellazione di elementi non richiedono spostamenti fisici degli altri e possono avvenire in qualunque punto della struttura.

- Adatta a gestire sequenze con frequenti inserimenti e cancellazioni, ma poche ricerche.

Esempi di liste
- Un testo è una sequenza (lista) di parole.
- Un parola è una sequenza (lista) di caratteri.
- L’elenco delle località “toccate” da un treno nel suo percorso è una sequenza (lista).

ADT Pila (Stack) - definizione
Una pila è una lista nella quale è possibile effettuare solo le operazioni di inserimento (push) ed estrazione (pop) da un unico estremo, detto cima della pila (top).

Struttura dati LIFO (Last In First Out)
Operazioni:
- isEmpty()
- isFull()
- pop()
- push()
- top()

Registrati via email