Struttura dati

Struttura dati

todo

Una struttura dati è un modo di strutturare i dati. In una sequenza lineare, si hanno gli elementi disposti consecutivamente, e sono associati alla loro posizione in questa struttura. La sequenza lineare può essere ad:

• accesso diretto: le celle utilizzate in memoria sono contigue, e si può accedere ad un elemento direttamente tramite l’indice, come ad esempio in un array. È anche detta sequenza statica. Per accedere ad un determinato elemento tramite l’indice costa $O(1)$. Per eliminare un elemento anche in testa costa $O(n)$ perché bisogna riscrivere tutto l’array.
• accesso sequenziale: le celle non sono contigue, e gli elementi tengono una referenza all’elemento successivo, come ad esempio una lista. È anche detta sequenza dinamica. Per accedere ad un determinato elemento con indice $i$ costa $O(i)$. Per eliminare un elemento anche in testa costa $O(1)$.

Liste Stack

asd_16