Definizione di Lista in informatica con implementazione in C

Definizione di Lista in informatica con implementazione in C

In informatica, con il termine lista si indica un insieme finito di  dati nel quale è  definita una  legge di ordinamento, ossia un insieme per il quale è stabilita una corrispondenza biunivoca tra i suoi elementi e l’insieme dei primi numeri naturali. In  base a  questa legge, è possibile stabilire quale è il  primo elemento di  questo insieme e  quale l’ultimo ed è inoltre possibile stabilire quale, tra due elementi qualsiasi dell’insieme, precede l’altro e quale segue. La caratteristica principale di una lista è nell’accesso ai suoi elementi: infatti, l’accesso ad un elemento qualsiasi di una lista avviene tramite  una ricerca sequenziale a  partire dal primo elemento della lista  per finire all’elemento considerato. Come vedremo, altre strutture  dati  come  la “pila” o la “matrice” presentano un metodo di accesso   diverso.

Esempio semplicissimo di lista è un normale testo letterario: in questo caso, gli elementi che costituiscono l’insieme sono le singole parole e i segni di  interpunzione, mentre l’ordinamento è definito dalla posizione fisica che gli elementi occupano nel testo. Un tipo particolare di lista è proprio la stringa: si tratta di una lista i cui elementi componenti sono caratteri di un determinato alfabeto. Gli elementi di una lista possono essere indicati con una notazione del tipo A1, A2, …, Ai-1, Ai, Ai+1, …, An-1, An che mette in rilievo la loro sequenzialità. Tuttavia questo tipo di notazione non deve indurre a pensare che l’accesso all’elemento Ai avvenga in base all’indice, ma, come detto prima, esso avviene in modo sequenziale a partire dall’elemento A1.

Se il numero dei dati che compongono una lista  rimane  costante  nel  tempo, allora si parla di lista a lunghezza fissa; se invece il numero di dati cambia (a seguito di operazioni di inserimento o di cancellazione), allora si parla di lista a lunghezza variabile. Le liste a  lunghezza variabile sono quelle più usate e  più interessanti dal punto  di vista applicativo: questa loro caratteristica fa sì che le liste vengano considerate strutture di dati di tipo dinamico (in seguito si tornerà su questa   definizione).

Su di una lista possono essere eseguite  due  diverse categorie di  operazioni: ci sono operazioni globali che interessano tutti gli elementi della lista e operazioni locali che interessano invece i singoli elementi della lista stessa. Tra le operazioni globali c’è per esempio la completa fusione di due liste in una sola, oppure la suddivisione di una lista in più parti o anche l’ordinamento degli elementi della lista secondo un ordine differente da quello iniziale e così   via.

Tra le operazioni locali, distinguiamo inviamo le seguenti operazioni fondamentali:

  • l’accesso ad un elemento per determinarne il “valore” oppure per modificarlo;
  • l’inserimento di un nuovo elemento tra altri due elementi, oppure all’inizio o alla fine della lista;
  • l’eliminazione di un elemento, magari quello iniziale o quello finale.

Infine, si vuole ricordare che la nozione di lista può essere ulteriormente generalizzata: si possono infatti considerare liste i cui elementi sono a loro volta liste con elementi e così via.

Definizione di Lista in informatica
Lista informatica

Implementazione in C

Presto disponibile…

Precedente La memoria virtuale con esercizio di rilocazione paginata Successivo Definizione delle strutture dati in informatica

Lascia un commento

*