Listas Doblementes Enlazadas Yoandy Pérez Villazón (2004-11-06)

El ejemplo que muestro a continuación es una lista doblemente enlazada realizada en C++ , usando 2 clases, una clase CNodo para crear la estructura de dato y una clase CListaDE para manipular de alguna forma el trabajo con estos nodos. Es un ejemplo que incluye los métodos básicos de trabajo, es decir:

  • Adicionar un elemento a la lista .-
  • Eliminar un elemento de la lista .-
  • Obtener un elemento a la lista .-
  • Ver la lonngitud de la lista .-
  • Insertar un elemento a la lista .-

De forma general esto es lo que se muestra en el codigo

template <class T>
class CNodo {
    private :
        T dato ;
        CNodo<T> *siguiente ;
        CNodo<T> *anterior ;
    public :
        CNodo(T adato , CNodo<T> *sig = 0,CNodo<T> *ant = 0 )
        {
            dato = adato ;
            siguiente = sig ;
            anterior = ant ;
        }
        void SetSiguiente(CNodo<T> *sig)
        {
            siguiente = sig ;
        }
        void SetAnterior(CNodo<T> *ant)
        {
            anterior = ant ;
        }
        T Getdato()
        {
            return dato;
        }
        CNodo<T> *GetSiguiente()
        {
            return siguiente ;
        }
        CNodo<T> *GetAnterior()
        {
            return anterior ;
        }
};

//Clase Lista
template <class T>
class CListaDE {
    private :
        CNodo<T> * ptr_cabeza ;

    public :
        CListaDE()
        {
            ptr_cabeza = 0 ;
        }
        void Adicionar(T elem)
        {
            CNodo<T> *nodo = new CNodo<T>(elem, 0);
            if(EstaVacia()) {
                ptr_cabeza = nodo ;
            }
            else {
                CNodo<T> *cursor = ptr_cabeza ;
                while(cursor->GetSiguiente() != 0)
                    cursor = cursor->GetSiguiente();
                nodo->SetAnterior(cursor);
                cursor->SetSiguiente(nodo);
            }
        }
        bool EstaVacia()
        {
            return ptr_cabeza == 0 ;
        }
        T Obtener(int pos)
        {
            if(pos>0 && pos <= Longitud())
            {
                CNodo<T> *cursor = ptr_cabeza ;
                int pos_cursor = 0 ;
                while(cursor->GetSiguiente() != 0 &&  pos_cursor+1 != pos)
                {
                    cursor = cursor->GetSiguiente();
                    pos_cursor++;
                }
                return  cursor->Getdato();
            }
            else
            throw CErrorPosicionExceptions();
        }
        int Longitud()
        {
            if(EstaVacia()) return 0 ;
            else {
                CNodo<T> *cursor = ptr_cabeza ;
                int cantidad = 0 ;
                while(cursor != 0)
                {
                    cantidad++;
                    cursor = cursor->GetSiguiente();
                }
                return  cantidad ;
            }
        }
        void Insertar(T data , int pos)
        {
            if(pos > 0 && pos <= Longitud())
            {
                if(EstaVacia()) Adicionar(data);
                else
                {
                    CNodo<T> *nodo = new CNodo<T>(data, 0 , 0);
                    if(pos == 1)
                    {
                        nodo->SetSiguiente(ptr_cabeza);
                        ptr_cabeza->GetSiguiente()->SetAnterior(nodo);
                        ptr_cabeza  = nodo ;
                    }
                    else
                    {
                        CNodo<T> *cursor = ptr_cabeza ;
                        int pos_cursor = 1 ;
                        while(cursor->GetSiguiente() != 0 && pos_cursor + 1 != pos)
                        {
                            cursor = cursor->GetSiguiente();
                            pos_cursor++ ;
                        }
                        nodo->SetSiguiente(cursor->GetSiguiente());
                        nodo->SetAnterior(cursor);
                        cursor->GetSiguiente()->SetAnterior(nodo);
                        cursor->SetSiguiente(nodo);
                    }
                }
            }
            else
                throw CErrorPosicionExceptions();
        }
        void Eliminar(int pos)
        {
            if(pos>0 && pos<= Longitud())
            {
                if(Longitud() == 1) delete [] ptr_cabeza ;
                else
                    if(pos == 1)
                    {
                        CNodo<T> *temp = ptr_cabeza->GetSiguiente();
                        delete[]ptr_cabeza ;
                        ptr_cabeza = temp ;
                        ptr_cabeza->SetAnterior(0);
                    }
                    else
                    {
                        CNodo<T> *cursor = ptr_cabeza ;
                        int pos_cursor = 1 ;
                        while(cursor->GetSiguiente()!= 0 && pos_cursor+1 != pos)
                        {
                            cursor = cursor->GetSiguiente();
                            pos_cursor++ ;
                        }
                        CNodo<T> *temp = cursor->GetSiguiente();
                        cursor->SetSiguiente(temp->GetSiguiente());
                        cursor->GetSiguiente()->SetAnterior(cursor);
                        delete []temp;
                    }
            }
            else
                throw CErrorPosicionExceptions();
        }
        bool Buscar(T elem)
        {
            if(!EstaVacia())
            {
                CNodo<T> *cursor = ptr_cabeza ;
                while(cursor->GetSiguiente() != 0)
                {
                    if(cursor->Getdato() == elem)
                    {
                        return true  ;
                    }
                    else
                        cursor = cursor->GetSiguiente();
                }
            }
        }
        T Buscar_Anterior(T elem)
        {
            if(!EstaVacia())
            {
                CNodo<T> *cursor = ptr_cabeza ;
                while(cursor->GetSiguiente() != 0)
                {
                    if(cursor->GetSiguiente()->Getdato() == elem)
                    {
                        return cursor->Getdato();
                    }
                    else
                        cursor = cursor->GetSiguiente();
                }
            }
        }
}

Regresar a ejemplos