Seguendo l’esempio su come realizzare una lista doppiamente linkata in C, vediamo come implementare una lista dello stesso tipo utilizzando il linguaggio C++ e la programmazione object-oriented.

Ricordiamo che una lista doppiamente linkata (detta anche lista doppiamente concatenata o lista bidirezionale) è una struttura dati dinamica composta da un insieme di elementi detti “nodi” collegati linearmente tra loro. Ogni nodo non è altro che un contenitore di dati.

All’interno di una lista doppiamente linkata, ogni nodo contiene un riferimento al nodo precedente (prev) e a quello successivo (next), mentre la lista terrà solo un riferimento al primo e all’ultimo nodo (che chiamiamo rispettivamente head e tail).

Lista Doppiamente Linkata
 

Sia i nodi che la stessa lista sono dunque rappresentati tramite oggetti. Questa volta il dato contenuto all’interno di ogni nodo potrà essere di qualsiasi tipo, cioè sarà possibile deciderlo al momento della creazione di nuovi oggetti lista e nodi, grazie all’utilizzo dei template (tipi generici). Verrà illustrato anche un esempio sull’utilizzo dell’overloading degli operatori, nel nostro caso per aggiungere/rimuovere nodi alla lista direttamente con gli operatori “+=” e “-=“.

E’ possibile vedere e scaricare tutto il codice dell’esempio direttamente da qui:

dlist.h download
dlist.cpp download

Partiamo dalla dichiarazione degli oggetti DNode e DList:

Dichiarazione classe DNode

template <class T>
class DNode
{
    T data;
    DNode *next, *prev;

public:
    DNode(T data);

    T getData()        { return data; }
    DNode* getNext()    { return next; }
    DNode* getPrev()    { return prev; }

    void setData(T d)        { data = d; }
    void setNext(DNode *n)    { next = n; }
    void setPrev(DNode *p)    { prev = p; }
};

template <class T>
ostream &operator<<(ostream &out, DNode<T> &n);

Quest’ultima funzione dichiarata servirà a poter stampare l’oggetto DNode, direttamente ridefinendo l’operatore “<<“.

Dichiarazione classe DList

template <class T>
class DList
{
    DNode<T> *head, *tail;
    int size;

public:
    DList();

    DNode<T>* getHead()    { return head; }
    DNode<T>* getTail()    { return tail; }
    int getSize()        { return size; }

    void insert(DNode<T> *n);    // aggiunge il nodo n alla lista
    void insert(T &value);        // crea un nuovo nodo contenente value e lo aggiunge alla lista
    DNode<T> *search(T &value);    // restituisce il primo nodo della lista contenente value
    void delnode(DNode<T> *n);    // rimuove il nodo puntato da n
    int delvalue(T &value);        // rimuove tutti i nodi che contengono value, restituisce il numero di nodi eliminati

    DList &operator+=(DNode<T> &n);
    DList &operator+=(T &value);
    DList &operator-=(DNode<T> &n);
    DList &operator-=(T &value);
};

template <class T>
ostream &operator<<(ostream &out, DList<T> &l);

Anche per la lista ridefiniremo l’operatore “<<” per poter stampare l’intera lista.


Implementazione di metodi e funzioni di supporto

Per quanto riguarda il DNode, ci serve solo l’implementazione del costruttore e la ridefinizione dell’operatore “<<“:

template <class T>
DNode<T>::DNode(T data)
{
    this->data = data;
    next = prev = NULL;
}

template <class T>
ostream &operator<<(ostream &out, DNode<T> &n)
{
    out << n.getData();
    return out;
}

Per quanto riguarda l’oggetto-lista DList dobbiamo implementare diversi metodi, partiamo dal costruttore della class:

template <class T>
DList<T>::DList()
{
head = tail = NULL;
size = 0;
}

Per quanto riguarda i metodi di inserimento, ne abbiamo due: il primo prende come parametro un riferimento a dato di tipo generico T, il secondo prende in input direttamente un puntatore a noto. Com’è facile intuire dal codice, il primo non fa altro che creare un nuovo DNode con il dato che prende in input e passarlo al secondo, che lo aggiunge alla lista. In questo modo abbiamo due modi per poter aggiungere nuovi dati alla lista:

template <class T>
void DList<T>::insert(T &value)
{
    DNode<T> *newnode = new DNode<T>(value);
    insert(newnode);
}

template <class T>
void DList<T>::insert(DNode<T> *n)
{
    if (size == 0)
        head = tail = n;
    else
    {
        tail->setNext(n);
        n->setPrev(tail);
        tail = n;
    }

    size++;
}

Abbiamo inoltre bisogno di un metodo che prende in input un dato T e  scorre tutti i nodi della lista e restituisce il primo contenente tale dato:

template <class T>
DNode<T> *DList<T>::search(T &value)
{
    DNode<T> *c = head;

    while (c != NULL)
    {
        if (c->getData() == value)
            return c;

        c = c->getNext();
    }

    return NULL;
}

Anche per cancellare elementi dalla lista abbiamo due metodi: delnode() e delvalue(). Il primo prende in input un puntatore a un nodo e rimuove tale nodo dalla lista. Il secondo prende in input un dato T e, servendosi sia del search() che di delnode(), rimuove dalla lista TUTTI i nodi che contengono quel dato T:

template <class T>
void DList<T>::delnode(DNode<T> *n)
{
    if (n != NULL)
    {
        if (head == n)
            head = tail = NULL;
        else
        {
            n->getPrev()->setNext(n->getNext());
            n->getNext()->setPrev(n->getPrev());

            if (tail == n)
                tail = NULL;
        }

        delete n;
        size--;
    }
}

template <class T>
int DList<T>::delvalue(T &value)
{
    int count = 0;
    DNode<T> *tmp;

    while ((tmp = search(value)) != NULL)
    {
        count++;
        delnode(tmp);
    }

    return count;    
}

Infine abbiamo tutti i metodi/funzioni che ridefiniscono gli operatori per poter stampare la lista (tramite l’operatore “<<“) e per poter aggiungere/rimuovere nuovi nodi alla lista (utilizzando direttamente una sintassi del tipo “Lista += NodoDaAggiungere“oppure “Lista -= NodoDaRimuovere“):

template <class T>
DList<T> &DList<T>::operator+=(DNode<T> &n)
{
    insert(&n);
    return *this;
}

template <class T>
DList<T> &DList<T>::operator+=(T &value)
{
    insert(value);
    return *this;
}

template <class T>
DList<T> &DList<T>::operator-=(DNode<T> &n)
{
    delnode(&n);
    return *this;
}

template <class T>
DList<T> &DList<T>::operator-=(T &value)
{
    delvalue(value);
    return *this;
}

template <class T>
ostream &operator<<(ostream &out, DList<T> &l)
{
    DNode<T> *tmp = l.getHead();

    while (tmp != NULL)
    {
        out << *tmp << " ";
        tmp = tmp->getNext();
    }

    return out;
}

About OpenProgrammers

Programmatore per passione. Mi piace condividere qualsiasi idea o informazione utile, per questo motivo ho realizzato il blog.