Concetti Chiave
- La struttura concatenata utilizza puntatori per collegare gli elementi, indicando la posizione del successore di ciascun elemento.
- Una lista è una successione di elementi dove ogni elemento, tranne il primo e l'ultimo, ha un solo successore e un solo predecessore.
- Le liste sono strutture dati lineari e dinamiche che permettono inserimenti e cancellazioni senza spostamenti fisici degli elementi.
- L'accesso agli elementi di una lista è strettamente sequenziale e non dipende dall'allocazione fisica della memoria.
- Una pila è un tipo di lista LIFO che consente operazioni solo da un estremo, utilizzando operazioni come push e pop.
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()
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
