La lista concatenata o lista concatenata singolarmente è una struttura dati elementare che consiste in una sequenza di nodi, ciascuno dei quali contiene un elemento data e un puntatore all’elemento successivo della lista. La presenza del puntatore ci consente di scorrere la lista, un po’ come in una caccia al tesoro. Si inizia con un indizio che ci conduce in un luogo in cui si trova un altro indizio che ci porta a un altro luogo e così via, finché non si raggiunge il tesoro finale. Nel caso delle liste concatenate, teniamo traccia del primo elemento della lista (detto elemento di testa) e iteriamo grazie al puntatore per spostarci lungo la lista. L’ultimo elemento della lista punta a nullptr, che in C++ (il linguaggio che useremo in questo post) ha valore 0.
Una nota riguardo nullptr
Nelle vecchie versioni di C++ (precedenti allo standard C++11) la parola chiave nullptr non esisteva. Al suo posto si usava la macro NULL, definita come
#define NULL 0
Questa implementazione, tuttavia, era problematica perché NULL non viene risolto dai compilatori come un puntatore, ma come un intero. Prendiamo queste due funzioni:
void f(char *a); void f(int i);
La chiamata di f(NULL) veniva interpretata come una chiamata alla versione che prende int come parametro.
Per questo motivo è stata inserita la parola chiave nullptr, che viene risolta univocamente come un puntatore. Per poter compilare il codice mostrato in questo post è necessario usare l’opzione -std=c++11 quando si compila su riga di comando (MinGW su Windows lo fa automaticamente, mentre su Linux è necessario specificarlo).
Il listato seguente mostra un’implementazione standard di un nodo per lista concatenata singolarmente.
template <typename T>
class Node {
public:
Node(T d, Node *n = nullptr) {
data = d;
next = n;
}
T get_data() { return data; }
Node<T> * get_next() { return next; }
void set_data(T d) { data = d; }
void set_next(Node<T> *n) { next = n; }
private:
T data;
Node<T> *next;
};
In questo snippet di codice non c’è niente di particolarmente interessante: abbiamo un costruttore che prende come parametro un oggetto di tipo T da assegnare alla variabile data e opzionalmente il puntatore all’elemento successivo. Abbiamo poi dei metodi getter e setter per modificare i valori.
Possiamo usare questa classe Node all’interno di una lista concatenata implementata così:
template <typename T>
class SLList {
public:
SLList() { head = nullptr; }
~SLList() {
Node<T> *current = head;
while (current) {
Node<T> *next = current->get_next();
delete current;
current = next;
}
}
T begin() {
if (begin_ptr())
return begin_ptr()->get_data();
}
T end() {
if (end_ptr())
return end_ptr()->get_data();
}
void prepend(T data) { head = new Node<T>(data, head); }
void append(T data) { end_ptr()->set_next(new Node<T>(data)); }
void insert(T data, unsigned pos) {
if (size() == 0 && pos == 0)
return prepend(data);
if (pos == size())
return append(data);
if (pos > size())
return;
Node<T> *before = element(pos), *after = element(pos + 1),
*n = new Node<T>(data, after);
before->set_next(n);
}
void remove_front() {
Node<T> *d = head;
head = head->get_next();
delete d;
}
void remove_back() {
Node<T> *t = head;
while (t->get_next())
t = t->get_next();
Node<T> *d = end_ptr();
t->set_next(nullptr);
delete d;
}
void remove(unsigned pos) {
if (size() == 0)
return;
if (pos == 0 || pos >= size())
return remove_front();
if (pos == size() - 1)
return remove_back();
Node<T> *before = element(pos - 1);
Node<T> *after = element(pos + 1);
delete element(pos);
before->set_next(after);
}
T get(unsigned pos) {
if (element(pos))
return element(pos)->get_data();
}
unsigned size() {
int s = 0;
for (Node<T> *n = head; n; n = n->get_next())
s++;
return s;
}
bool is_empty() { return head == nullptr; }
protected:
Node<T> * begin_ptr() { return head; }
Node<T> * end_ptr() {
Node<T> *it = head;
while (it->get_next())
it = it->get_next();
return it;
}
Node<T> * element(unsigned pos) {
Node<T> *it = head;
int i = 0;
while (it && i < pos) {
it = it->get_next();
i++;
}
if (i == pos)
return it;
else
return nullptr;
}
Node<T> *head;
};
Di nuovo, questa è un’implementazione standard di una lista concatenata singolarmente in linguaggio C++. Abbiamo un costruttore che inizializza il puntatore alla testa a nullptr, un distruttore che si occupa di liberare la memoria occupata dai nodi, dei metodi di inserimento e di cancellazione degli elementi e qualche altro metodo accessorio.
E’ chiaro che, rispetto all’allocazione dinamica di un array, la lista concatenata ha il vantaggio di poter crescere in tempo costante (in caso di inserimento in testa), lineare (nel caso di inserimento in coda, ma è possibile ottenere inserimento in coda in tempo costante tenendo traccia anche della coda) o lineare ammortizzato (nel caso di inserimento in una posizione qualsiasi, mentre per far crescere un array abbiamo bisogno di allocare nuova memoria, copiare tutti gli elementi dell’array e cancellare l’array originale, un’operazione che richiede sempre tempo lineare.
Tuttavia, questa implementazione ha lo svantaggio di non consentire di assegnare dei valori a un certo elemento di una lista. Possiamo accedere agli elementi di una lista usando i metodi begin(), end() o get(pos), ma questa soluzione non è particolarmente elegante, visto che il C++ consente di eseguire il sovraccaricamento degli operatori.
Idealmente, vogliamo poter accedere agli elementi della lista usando l’operatore parentesi quadre per usare la lista come se si trattasse di un array. Il metodo più immediato sarebbe scrivere un metodo di questo tipo:
template <typename T>
T SLList<T>::operator[](unsigned pos) {
return get(pos);
}
Questo metodo ci spinge però in un pozzo senza fondo: possiamo sì accedere all’elemento in una certa posizione (anzi, più precisamente, a una copia di quell’elemento), ma non è possibile sostituire il dato contenuto nel nodo. Un metodo più desiderabile è quindi restituire un riferimento al nodo che ci interessa.
template <typename T>
Node<T> & SLList<T>::operator[](int pos) {
return *element(pos);
}
Di primo acchito sembrerebbe che restituire un riferimento a un oggetto Node all’interno di un metodo pubblico costituisce un’infrazione dell’incapsulamento, ma in realtà ciò non è vero: al contrario, ciò ci consente di scrivere dei metodi che ci permetteranno di usare gli oggetti di tipo Node come se fossero oggetti primitivi del C++.
Notare come stiamo restituendo un riferimento al nodo anziché il nodo in sè: ciò ci consente di migliorare leggermente le prestazioni perché ci risparmia un’operazione di copia.
L’asterisco prima di element(pos) indica che stiamo dereferenziando il puntatore, cioè non stiamo restituendo il puntatore in sé ma il riferimento all’oggetto puntato.
Come sostituire il valore di data in un nodo
La prima operazione che intendo implementare è la sostituzione del valore di data all’interno di un nodo. Torniamo alla classe Node ed eseguiamo l’overloading dell’operatore di assegnamento:
template <typename T>
T& SLList<T>::operator=(T d) {
data = d;
return data;
}
La riga return data; è indispensabile perché l’operatore di assegnazione restituisce sempre dei riferimenti. E’ per questo motivo che è possibile concatenare vari assegnamenti sulla stessa riga.
In questo modo possiamo usare la lista come segue:
SLList<int> l; l.prepend(5); l[0] = 1;
Proviamo a scrivere qualcosa di un po’ più complesso:
SLList<int> l; l.prepend(5); l.append(10); std::cout << l.get(0) << " " << l.get(1) << "\n"; l[0] = l[1]; std::cout << l.get(0) << " " << l.get(1);
Vediamo l’output:
Oops… Non è affatto quello che volevamo. Il problema è che il metodo che abbiamo scritto per sovraccaricare l’operatore di assegnamento prende come parametro un oggetto di tipo T, mentre in questo caso abbiamo passato un oggetto di tipo Node<T> all’assegnamento. Non abbiamo ricevuto un errore di compilazione perché il C++ fornisce automaticamente un operatore di assegnamento di copia che esegue una copia banale membro a membro. In pratica non abbiamo fatto altro che spostare il nodo che si trova in posizione 1 alla posizione 0.
Per ovviare al problema dobbiamo definire un nostro operatore di assegnamento di copia di questo tipo:
template <typename T>
T& SLList<T>::operator=(const Node &n) {
this->data = n.data;
return data;
}
Così facendo, abbiamo modificato il valore di data senza toccare il puntatore all’elemento successivo. Molto utile, non c’è che dire.
Però non abbiamo ancora risolto tutto: per esempio, non possiamo eseguire operazioni matematiche tra i nodi o fare comparazioni. Nel prossimo articolo ci occuperemo quindi fare l’overloading degli operatori matematici e di quelli relazionali, ma il post è già diventato un po’ lunghetto, quindi ce ne occuperemo in una seconda parte.
