Per poter capire come funziona una lista, e pure scritta in C, devi conoscere:
1) la sintassi del C
2) la differenza tra stack e heap
3) le funzioni di allocazione della memoria
4) il concetto di puntatore
5) il concetto di struttura dati
6) il concetto di collezione
7) il concetto di operazione su una collezione
8 ) il concetto di lista. Ed anche qui hai: lista semplice, lista doppiamente lincata, lista circolare
Ora, onestamente, per arrivare al concetto di lista, devi avere gia' compreso i concetti descritti dal punto 1 al punto 7. In prima aprossimazione sono l'equivalente di 7 lezioni. Oppure 7 capitoli di un libro.
Vediamo:
definizione 1)
una lista e' una struttura dati che puo' essere definita in modo ricorsivo come:
lista vuota: []
una struttura dati formata da una testa, contenete un valore, e una coda, rappresentata da una lista: [testa | coda]
definizione 2)
una lista e' un particolare tipo di collezione in cui le operazioni hanno la seguente complessita:
operazione di ricerca: O(n)
operazione di inserimento in testa: O(1)
operazione di rimozione dalla testa: O(1)
inserimento in mezzo/coda: O(n)
rimozione dal mezzo/dalla coda: O(n) (lista semplice), O(1) (lista doppiamente lincata)
Ci sono diverse possibili implementazioni, a seconda delle operazioni richieste e delle proprieta' desiderate
1) lista semplice: ogni nodo ha una struttura del tipo:
template<T>
struct NodeList {
T value;
NodeList *next;
}
2) lista doppiamente lincata e lista circolare: ogni nodo ha una struttura del tipo:
template<T>
struct NodeLinkedList {
T value;
NodeLinkedList *prev;
NodeLinkedList *next;
}
A seconda del tipo di lista, le operazioni vengono implementate in modo opportuno.
Esempio di programma che usa una lista (semplice) e alloca alcuni nodi:
typedef
struct NodeList {
int value;
NodeList *next;
} NodeList;
int main (int argc, char** argv)
{
NodeList *l = NULL;
NodeList *p;
p = (NodeList*)malloc(sizeof(NodeList));
p->value = 0;
p->next = NULL;
l = p;
p = (NodeList*)malloc(sizeof(NodeList));
p->value = 1;
p->next = NULL;
l->next = p;
for(p = l; p != NULL; p = p->next)
if (p->value == 1)
printf("Trovato 1\n");
}
E adesso?
Ti rendi conto che
non e' possibile spiegare il concetto di
lista senza avere chiaro tutto quello che ci sta' attorno?
Non stiamo parlando di una definizione adatta alla casalinga (la lista della spesa), ma per qualcuno
che deve saper come implementarla utilizzando un linguaggio di programmazione (in questo caso il C).
TE TOCCA STUDIA'