5.8 Ejemplo de lista doblemente enlazada en C++ usando clases

Veamos ahora el mismo ejemplo usando clases.

Para empezar, y como siempre, necesitaremos dos clases, una para nodo y otra para lista. Además la clase para nodo debe ser amiga de la clase lista, ya que ésta debe acceder a los miembros privados de nodo.

class nodo {
   public:
    nodo(int v, nodo *sig = NULL, nodo *ant = NULL) : 
        valor(v), siguiente(sig), anterior(ant) {}

   private:
    int valor;
    nodo *siguiente;
    nodo *anterior;
        
   friend class lista;
};
 
typedef nodo *pnodo;
 
class lista {
   public:
    lista() : lista(NULL) {}
    ~lista();
    
    void Insertar(int v);
    void Borrar(int v);
    bool ListaVacia() { return lista == NULL; } 
    void Mostrar();
    void Siguiente();
    void Anterior();
    void Primero();
    void Ultimo();
    pnodo Actual() { return lista; }
    int ValorActual() { return lista->valor; }
    
   private:
    pnodo lista;
};

Ahora sólo necesitamos un puntero para referenciar la lista y movernos a través de ella. Hemos añadido funciones para avanzar y retroceder, moverse al primero o último nodo, obtener un puntero al nodo actual o su valor.

Los algoritmos para insertar y borrar elementos son los mismos que expusimos para el ejemplo C, tan sólo cambia el modo de crear y destruir nodos.

Código del ejemplo completo

#include <iostream>
using namespace std;
 
#define ASCENDENTE 1
#define DESCENDENTE 0

class nodo {
   public:
    nodo(int v, nodo *sig = NULL, nodo *ant = NULL) :
       valor(v), siguiente(sig), anterior(ant) {}

   private:
    int valor;
    nodo *siguiente;
    nodo *anterior;
        
   friend class lista;
};

typedef nodo *pnodo;

class lista {
   public:
    lista() : plista(NULL) {}
    ~lista();
    
    void Insertar(int v);
    void Borrar(int v);
    bool ListaVacia() { return plista == NULL; } 
    void Mostrar(int);
    void Siguiente();
    void Anterior();
    void Primero();
    void Ultimo();
    bool Actual() { return plista != NULL; }
    int ValorActual() { return plista-&gt;valor; }
    
   private:
    pnodo plista;
};

lista::~lista() {
   pnodo aux;
   
   Primero();
   while(plista) {
      aux = plista;
      plista = plista->siguiente;
      delete aux;
   }
}

void lista::Insertar(int v) {
   pnodo nuevo;
 
   Primero();
   // Si la lista está vacía
   if(ListaVacia() || plista->valor > v) {
      // Asignamos a lista un nuevo nodo de valor v y
      // cuyo siguiente elemento es la lista actual                    
      nuevo = new nodo(v, plista);
      if(!plista) plista = nuevo;
      else plista->anterior = nuevo;
   }
   else {
      // Buscar el nodo de valor menor a v 
      // Avanzamos hasta el último elemento o hasta que el siguiente tenga 
      // un valor mayor que v 
      while(plista->siguiente && plista->siguiente->valor <= v) Siguiente();
      // Creamos un nuevo nodo después del nodo actual
      nuevo = new nodo(v, plista->siguiente, plista);
      plista->siguiente = nuevo;
      if(nuevo->siguiente) nuevo->siguiente->anterior = nuevo;
   }
}

void lista::Borrar(int v) {
   pnodo nodo;
   
   nodo = plista;
   while(nodo && nodo->valor < v) nodo = nodo->siguiente;
   while(nodo && nodo->valor > v) nodo = nodo->anterior;

   if(!nodo || nodo->valor != v) return;
   // Borrar el nodo 
   
   if(nodo->anterior) // no es el primer elemento 
      nodo->anterior->siguiente = nodo->siguiente;
   if(nodo->siguiente) // no el el último nodo
      nodo->siguiente->anterior = nodo->anterior;
   delete nodo;
}

void lista::Mostrar(int orden) {
   pnodo nodo;
   if(orden == ASCENDENTE) {
      Primero();
      nodo = plista;
      while(nodo) {
         cout << nodo->valor << "-> ";
         nodo = nodo->siguiente;
      }
   }
   else {
      Ultimo();
      nodo = plista;
      while(nodo) {
         cout << nodo->valor << "-> ";
         nodo = nodo->anterior;
      }
   }
   cout << endl;
}

void lista::Siguiente() {
   if(plista) plista = plista->siguiente;
}

void lista::Anterior() {
   if(plista) plista = plista->anterior;
}

void lista::Primero() {
   while(plista && plista->anterior) plista = plista->anterior;
}

void lista::Ultimo() {
   while(plista && plista->siguiente) plista = plista->siguiente;
}

int main() {
   lista Lista;
   
   Lista.Insertar(20);
   Lista.Insertar(10);
   Lista.Insertar(40);
   Lista.Insertar(30);

   Lista.Mostrar(ASCENDENTE);
   Lista.Mostrar(DESCENDENTE);

   Lista.Primero();
   cout << "Primero: " << Lista.ValorActual() << endl;
   
   Lista.Ultimo();
   cout << "Ultimo: " << Lista.ValorActual() << endl;
   
   Lista.Borrar(10);
   Lista.Borrar(15);
   Lista.Borrar(45);
   Lista.Borrar(40);
   
   Lista.Mostrar(ASCENDENTE);
   Lista.Mostrar(DESCENDENTE);

   return 0;
}

Fichero con el código fuente.

Ir a página de descargas: Descargar programa

Comentarios de los usuarios (3)

Donaldo
2010-03-28 22:09:18

muy buena descripcion del tema, soy principiante en tema de punteros y listas, pero tengo una duda, porque al intentar compilar el codigo de la lista doble enlazada en c++, no me deja usar \"using namespace std\" me solo ese error, y si lo omito el compilador se cuelga, me tira un error y me muestra la corrida pero se traba el compilador, desarrollo en un borland c++ 5.01.

Esta es la parte del codigo que me indica en azul cuando se traba.

 while(plista && plista->anterior) plista = plista->anterior;
jesus
2011-11-21 04:46:47

si el valor a borrar o insertar fuese una cadena de caracteres, las condiciones para ambas funciones deben llevar strlen()?;esq tengo un programa muy parecido al de ustedes solo q manejo cadenas y cuando en el main predefino los valores a insertar o a borrar no me causa ningun problema,,pero cuando intento hacer un menu, solo me borra el ultimo elemento de la lista(coloco la funcion borrar q es la q me esta causando problemas)

void lista::Borrarn(char*v) {

pnodo nodo;

nodo = plista;

while(nodo && strlen(nodo->nomb) < strlen(v)) nodo = nodo->siguiente;

while(nodo && strlen(nodo->nomb) > strlen(v)) nodo = nodo->anterior;

if(!nodo || strlen(nodo->nomb) != strlen(v)) return;

if(nodo == plista)

if(nodo->anterior) plista = nodo->anterior;

else plista = nodo->siguiente;

if(nodo->anterior)

nodo->anterior->siguiente = nodo->siguiente;

if(nodo->siguiente)

nodo->siguiente->anterior = nodo->anterior;

delete nodo;

}

Steven R. Davidson
2011-11-21 14:14:19

Hola Jesús,

No tiene mucho sentido comprobar la cantidad de caracteres de los nodos, al menos que quiera basarse en tal criterio. Lo normal sería comprobar si las cadenas de los nodos tienen igual contenido que la cadena a borrar. Para esto, usaríamos 'strcmp()'; esto es,

while( nodo && strcmp(nodo->nomb, v) < 0 ) nodo = nodo->siguiente;
while( nodo && strcmp(nodo->nomb, v) > 0 ) nodo = nodo->anterior;

if( !nodo || strcmp(nodo->nomb, v) != 0 ) return;

El otro problema es cómo defines el tipo del nodo. Si contiene un array dinámico, entonces es posible que tengas problemas al liberar un nodo, si el tipo del nodo no tiene un destructor para liberar esa memoria para el array dinámico. Esto es,

class nodo
{
  ...
  ~nodo()  { delete pCadena; }

private:
  char *pCadena;
  nodo *siguiente;
  nodo *anterior;
};

Espero haber aclarado la duda.

Steven