Liste concatenate
Un limite degli array è che hanno una dimensione predefinita. Questo limite rende poco flessibile la gestione di problemi in cui non è possibile sapere in anticipo quanti saranno gli elementi utilizzati effettivamente.
Questo comporta potenzialmente uno spreco di memoria (non tutti gli elementi dell’array sono effettivamente usati) o una mancanza di memoria a disposizione. Ad esempio se vogliamo caricare degli elementi da un file CSV, dovremmo già sapere in anticipo quanti elementi ci saranno prima di dimensionare l’array.
Per risolvere il problema è possibile usare le struct e i puntatori.
Ipotizziamo di voler creare una lista di numeri interi dinamica.
Prima di tutto definiamo una struct
struct node
{
int data;
struct node *next;
};Come si vede la struct contiene un puntatore ad un nodo successivo.
A questo punto definiamo una funzione di aggiunta:
node* add(node* current, int value) {
current->data = i;
current->next = new node;
cout << "Aggiunto nodo: " << current << endl;
return current->next;
}Con questa funzione possiamo inserire un valore all’attributo data e creare un nuovo nodo. Come si vede si usa la parola chiave new per allocare lo spazio per un nuovo nodo. In pratica l’istruzione new alloca lo spazio del nuovo nodo e restituisce il puntatore all’indirizzo del nodo appena creato.
A questo punto possiamo creare quanti nodi vogliamo.
Per farlo possiamo utilizzare un ciclo for come il seguente:
node *current = new node;
int num;
cout << "Indica quanti nodi vuoi inserire: ";
cin >> num;
for (int i=0; i<num; i++) {
current = add(current, i);
}Per gestire il nodo corrente (l’ultimo) aggiorniamo il suo puntatore all’ultimo nodo appena creato. Quindi se creiamo 5 nodi, avremo il nodo 0 che ha un puntatore al nodo 1, che ha un puntatore a nodo 2 e così via fino a 5. Tuttavia se aggiorniamo il valore di current al puntatore successivo perdiamo il riferimento al primo nodo della lista (non c’è modo di tornare indietro). Quindi ci serve un puntatore first che punta al primo nodo della lista e che non modifichiamo mai.
Qui lo stesso codice con questo accorgimento:
node *first = new node;
node *current = first;
int num;
cout << "Indica quanti nodi vuoi inserire: ";
cin >> num;
for (int i=0; i<num; i++) {
current = add(current, i);
}Questo sistema abbiamo due soli puntatori, first che punta al primo elemento, e current che punta all’ultimo elemento. La dimensione della lista non ha limiti, e per accedere ad un elemento qualsiasi ci basta questa funzione:
node* get(node *current, int index) {
if (index == 0) {
return current;
} else {
return get(current->next, index-1);
}
}
Per esempio se vogliamo il terzo elemento della lista scriveremo:
node *third = get(first, 3);In pratica get è una funzione ricorsiva che avanza nella lista fino al nodo desiderato.
E’ importante osservare che se si perde il riferimento a first non solo non si riesce ad accedere ai dati ma si genera un problema noto come memory leak, ovvero quando dei nodi sono allocati in memoria ma non sono raggiungibili in nessun modo.
Se vogliamo eliminare un nodo introduciamo la funzione remove che elimina l’ultimo nodo:
node* remove(node *current) {
node *temp = current->next->next;
delete current->next;
current->next = temp;
return current->next;
}Per capire come funziona vediamo come si richiama:
current = get(first, num-2);
current = remove(current);
num--;Prima di tutto si porta il puntatore current indietro di due nodi rispetto alla testa (l’ultimo è il futuro nodo – non contiene alcun valore – ed il penultimo è l’effettivo ultimo nodo con un valore ). A questo punto la funzione remove memorizza il nodo futuro in una variabile temporanea e poi cancella l’ultimo nodo popolato. Infine aggancia il futuro nodo al penultimo nodo.
Sembra complicato ma non lo è, e per capirlo vediamo un esempio di programma completo con quanto visto finora.
#include <iostream>
#include <string.h>
#include <cstdlib>
using namespace std;
struct node
{
int data;
struct node *next;
};
node* add(node* current, int value) {
current->data = value;
current->next = new node;
return current->next;
}
node* get(node *current, int index) {
if (index == 0) {
return current;
} else {
return get(current->next, index-1);
}
}
node* remove(node *current) {
node *temp = current->next->next;
delete current->next;
current->next = temp;
return current->next;
}
void print(node *first) {
node* current = first;
cout << "Ecco la lista dei nodi: " << endl;
while (current->next != NULL) {
cout << "Indirizzo: " << current << " - Valore:" << current->data << " -> Indirizzo (succ): " << current->next << endl;
current = current->next;
}
cout << "Indirizzo testa lista (vuoto): " << current << endl;
}
int main() {
node *first = new node;
node *current = first;
int num;
cout << "Indica quanti nodi vuoi inserire: ";
cin >> num;
for (int i=0; i<num; i++) {
current = add(current, i);
}
cout << "Inseriti " << num << " nodi" << endl;
print(first);
int action;
do {
cout << "Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: ";
cin >> action;
if (action==1) {
current = get(first, num-2);
current = remove(current);
num--;
print(first);
}
if (action == 2) {
current = add(current, num);
num++;
print(first);
}
} while (action != 0);
return 0;
}Il programma stampa gli indirizzi dei puntatori della lista e con questo output si dimostra il funzionamento:
Indica quanti nodi vuoi inserire: 1
Inseriti 1 nodi
Ecco la lista dei nodi:
Indirizzo: 0x6312153a12b0 - Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo testa lista (vuoto): 0x6312153a1af0
Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 2
Ecco la lista dei nodi:
Indirizzo: 0x6312153a12b0 - Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 - Valore:1 -> Indirizzo (succ): 0x6312153a1b10
Indirizzo testa lista (vuoto): 0x6312153a1b10
Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 2
Ecco la lista dei nodi:
Indirizzo: 0x6312153a12b0 - Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 - Valore:1 -> Indirizzo (succ): 0x6312153a1b10
Indirizzo: 0x6312153a1b10 - Valore:2 -> Indirizzo (succ): 0x6312153a1b30
Indirizzo testa lista (vuoto): 0x6312153a1b30
Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 2
Ecco la lista dei nodi:
Indirizzo: 0x6312153a12b0 - Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 - Valore:1 -> Indirizzo (succ): 0x6312153a1b10
Indirizzo: 0x6312153a1b10 - Valore:2 -> Indirizzo (succ): 0x6312153a1b30
Indirizzo: 0x6312153a1b30 - Valore:3 -> Indirizzo (succ): 0x6312153a1b50
Indirizzo testa lista (vuoto): 0x6312153a1b50
Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 1
Ecco la lista dei nodi:
Indirizzo: 0x6312153a12b0 - Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 - Valore:1 -> Indirizzo (succ): 0x6312153a1b10
Indirizzo: 0x6312153a1b10 - Valore:2 -> Indirizzo (succ): 0x6312153a1b50
Indirizzo testa lista (vuoto): 0x6312153a1b50
Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 1
Ecco la lista dei nodi:
Indirizzo: 0x6312153a12b0 - Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 - Valore:1 -> Indirizzo (succ): 0x6312153a1b50
Indirizzo testa lista (vuoto): 0x6312153a1b50
Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 0