Concetti Chiave
- La struttura concatenata utilizza puntatori per mantenere l'ordine logico degli elementi, permettendo di collegare ogni elemento al suo successore.
- È una struttura dati lineare e dinamica, che può essere vuota e consente un accesso sequenziale per la ricerca degli elementi.
- Gli elementi possono occupare locazioni di memoria distanti, rendendo la sequenza logica indipendente dall'allocazione fisica.
- Le operazioni di inserimento e cancellazione non richiedono spostamenti fisici, rendendola adatta per sequenze con frequenti modifiche.
- Una pila, un sottotipo di lista, consente operazioni di inserimento ed estrazione solo da un'estremità, identificata come cima della pila.
Concetto di 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.
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.
- 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.
- 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).
Funzionalità delle pile
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).
Operazioni:
- isEmpty()
- isFull()
- pop()
- push()
- top()
Domande da interrogazione
- Qual è la principale caratteristica della struttura concatenata?
- Quali sono i vantaggi dell'utilizzo di una lista concatenata?
- Quali operazioni sono consentite in una pila?
La struttura concatenata utilizza puntatori per collegare gli elementi, permettendo di ricostruire l'ordine logico senza necessità di una allocazione fisica contigua in memoria.
Le liste concatenate permettono inserimenti e cancellazioni efficienti in qualsiasi punto della struttura senza spostamenti fisici degli altri elementi, rendendole adatte per sequenze con frequenti modifiche.
In una pila, è possibile effettuare solo operazioni di inserimento (push) ed estrazione (pop) da un unico estremo, noto come cima della pila, insieme a funzioni di controllo come isEmpty() e isFull().
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
