8.2.2 Lista doblemente encadenda

En la lista doblemente encadenada cada Nodo tiene un apuntador al siguiente y otro al anterior como se ve en la figura .

Figure: Lista doblemente encadenada.

La librería para el TDA Lista con versión doblemente encadenada es la siguiente:

/*

listad.h

Autor: L. Alejandro Bernal R.

Fecha: 2000.12.06

*/

#ifndef _LISTAD_H_

#define _LISTAD_H_

#include <stdlib.h>

#include <iostream.h>

/*

TDA Nodo 

    Descripción: Un nodo representa a cado uno de los elementos de la lista.

    Invariante: nodo pertenece a Nodo y nodo=(inf,sig,ant) y sig pertenece a *Nodo y inf pertenece a TipoB y ant pertenece a *Nodo.

*/

template<class TipoB>

class Nodo{

    private:

    // Atributos:

    TipoB inf; // Información del nodo.

    Nodo *sig; // Apuntador al siguiente nodo.

    Nodo *ant; // Apuntador al anterior nod.

    public:

    //Operaciones: 

    /*

    Operación Nodo 

        Descripción: Construye un nodo con la información.

        Descripción operacional: Nodo: TipoB -> Nodo

        Precondición: in pertenece a TipoB 

        Poscondición: nodo=(inf,sig) 

    */

    Nodo(TipoB in) { inf = in; sig = NULL; ant = NULL; }

    /*

    Operación obtinf 

        Descripción: Obtiene la información del nodo.  

        Descripción operacional: obtinf: Nodo -> TipoB 

        Precondición: 

        Poscondición: obtinf=inf 

    */

    TipoB obtinf() { return inf; }

    /*

    Operación modinf 

        Descripción: Modifica la información del nodo.  

        Descripción operacional: modinf: Nodo x TipoB -> Nodo 

        Precondición: nue pertenece a TipoB 

        Poscondición: nodo=(nue,sig) 

    */

    void modinf(TipoB nue) { inf = nue;  }

    /*

    Operación obtsig 

        Descripción: Obtiene el apuntador al siguiente nodo.

        Descripción operacional: obtsig: Nodo -> *Nodo

        Precondición: 

        Poscondición: obtsig=sig 

    */

    Nodo *obtsig() { return sig; }

    /*

    Operación modsig 

        Descripción: Modifica el apuntador al siguiente.

        Descripción operacional: modsig: Nodo x *Nodo -> Nodo 

        Precondición: si pertenece a *Nodo 

        Poscondición: nodo=(ing,si,ant)

    */

    void modsig(Nodo *si) { sig = si; }

    /*

    Operación obtant

        Descripción: Obtiene el apuntador al anterior nodo.

        Descripción operacional: obtant: Nodo -> *Nodo

        Precondición:

        Poscondición: obtant=ant

    */

    Nodo *obtant() { return ant; }

    /*

    Operación modsig

        Descripción: Modifica el apuntador al anterior nodo.

        Descripción operacional: modant: Nodo x *Nodo -> Nodo

        Precondición: si pertenece a *Nodo

        Poscondición: nodo=(ing,sig,an)

    */

    void modant(Nodo *an) { ant = an; }

}; // class Nodo

/*

TDA Lista 

    Descripción: El TDA Lista es una secuencia de elementos todos del mismo tipo, uno de los cuales está distiguido como actual.

    Invariante: Lista=(elem,actual) y elem=<elem[0],elem[1],elem[2],...,elem[i],...,elem[n-1]> y (Para todo i,0<=i<n,elem[i] pertenece a Nodo) y actual pertenece a elementos.

*/

template<class TipoB>

class Lista{

    private:

    // Atributos:

    Nodo<TipoB> *elem; // Apuntador al primer elemento.

    Nodo<TipoB> *actual; // Apuntador al elemento actual.

    Nodo<TipoB> *ultimo; // Apuntador al ultimo elemento.

    // Operaciones:

    public:

    // Excepciones:

    class Excepcion { }; // Excepción general.

    class NoHayMemoria : public Excepcion { }; // No hay memoria.

    class ActualNoEstaDefinido : public Excepcion { }; // No está definido actual.

    class UltimoNoEstaDefinido : public Excepcion { }; // No está definido el último.

    // Operaciones: 

    /*

    Operación Lista 

        Descripción: Construlle una lista vacia.

        Descripción operacional: construir: -> Lista

        Precondición: verdadero 

        Poscondición: lista pertenece a Lista y lista=(<>,).

    */

    Lista() { elem = NULL; actual = NULL; ultimo = NULL; }

    /*

    Operación adicionar 

        Descripción: Adiciona un nuevo elemento a la lista.

        Descripción operacional: adicionar:Lista x TipoB -> Lista

        Precondición: lista pertenece a Lista y nuevo pertenece a TipoB

        Poscondición: lista=<elem[0],...,elem[n-e],nuevo> y actual=nuevo.  

    */

    void adicionar(TipoB nuevo);

    /*

    Operación retirar 

        Descripción: Retira el elemento actual retornandolo y dejando el siguiente como actual.

        Descripción operacional: retirar:Lista -> Lista

        Precondición: lista pertenece a Lista y lista=(<elem[0],elem[1],elem[2],...,elem[i-1],elem[i],elem[i+1],...,elem[n-1]>,elem[i])

        Poscondición: lista=(<elem[0],elem[1],elem[2],...,elem[i-1],elem[i+1],...,elem[n-2]>,elem[i+1]) y retirar=elem[i]

    */

    TipoB retirar();

    /*

    Operación insertar 

        Descripción: Inserta el elemento nuevo en la lista después del actual y lo pone como actual.

        Descripción operacional: insertar:Lista x TipoB -> Lista

        Prencondición: lista pertenece a Lista y lista=(<elem[0],...,elem[i],elem[i+1],...,elem[n-1]>,elem[i]) y nuevo pertenece a TipoB.

        Poscondición: lista=(<elem[0],...,elem[i],nuevo,elem[i+1],...,elem[n]>,nuevo)

    */

    void insertar(TipoB nuevo);

    /*

    Operación colprimact 

         Descripción: Coloca como actual el primer elemento de la lista.

         Descripción operacional: colprimact:Lista -> Lista 

         Precondición: lista pertenece a Lista y lista=(<elem[0],elem[1],elem[2],...,elem[i],...,elem[n-1]>,elem[i])

         Poscondición: lista=(<elem[0],elem[1],elem[2],...,elem[i],...,elem[n-1]>,elem[0])

    */

    void colprimact() { actual = elem; }

    /*

    Operación colultact 

        Descripción: Coloca como como actual el último elemento de la lista.

        Descripción operacional: colultact:Lista -> Lista

        Precondición: lista pertenece a Lista y lista=(<elem[0],elem[1],elem[2]....,elem[i],elem[i+1],...,elem[n-1]>,elem[i])

        Poscondición: lista=(<elem[0],elem[1],elem[2],...,elem[i],...,elem[n-1]>,elem[n-1])

    */

    void colultact() { actual = ultimo; }

    /*

    Operación colsigact 

        Descripción: Coloca el siguiente al actual como actual.

        Descripción operacional: colsigact:Lista -> Lista 

        Precondición: lista pertenece a Lista y lista=(<elem[0],elem[1],elem[2],...,elem[i],elem[i+1]...,elem[n-1]>,elem[i])

        Poscondición: lista=(<elem[0],elem[1],elem[2],...,elem[i],elem[i+1],...,elem[n-1]>,elem[i+1])

    */

    void colsigact()

    {

        if(actual == NULL) {

            throw ActualNoEstaDefinido();

        }

        actual = actual->obtsig();

    }

    /*

    Operación colxact 

        Descripción: Coloca el x-esimo elemento como actual. Si no existe ese elemento actual queda nulo.

        Descripción operacional: coliact:Lista x N -> Lista

        Precondición: lista pertenece a Lista y lista=(<elem[0],elem[1],elem[2],...,elem[i],...,elem[x],...,elem[n-1]>,elem[i]) y 0<=x=n

        Poscondición: lista=(<elem[0],elem[1],elem[2],...,elem[i],...,elem[x],...,elem[n-1]>,elem[x])

    */

    void colxact(int x);

    /*

    Operación obtact 

        Descripción: Obtiene el elemento actual de la lista.

        Descripción operacional: obtact:Lista -> TipoB

        Precondición: lista pertenece a Lista y lista=(<elem[0],elem[1],elem[2],...,elem[i],...,elem[n-1]>,actual) y actual=elem[i]

        Poscondición: obtact=actual

    */

    TipoB obtact() { return actual->obtinf(); }

        

}; // class lista

/*

Operación adicionar

    Descripción: Adiciona un nuevo elemento a la lista.

    Descripción operacional: adicionar:Lista x TipoB -> Lista

    Precondición: lista pertenece a Lista y nuevo pertenece a TipoB

    Poscondición: lista=<elem[0],...,elem[n-e],nuevo> y actual=nuevo.

*/

template<class TipoB>

void Lista<TipoB>::adicionar(TipoB nuevo){

    if(elem == NULL){

        elem = new Nodo<TipoB> (nuevo);

        if(elem == NULL){

            throw NoHayMemoria();

        }

       actual = elem;

       ultimo = elem;

       return ;

    }

    ultimo->modsig(new Nodo<TipoB>(nuevo));

    if(ultimo->obtsig() == NULL){

        throw NoHayMemoria();

    }

} // void Lista<TipoB>::adicionar(TipoB nuevo);

/*

Operación retirar 

    Descripción: Retira el elemento actual retornandolo y dejando el siguiente como actual.

    Descripción operacional: retirar:Lista -> Lista 

    Precondición: lista pertenece a Lista y lista=(<elem[0],elem[1],elem[2],...,elem[i-1],elem[i],elem[i+1],...,elem[n-1]>,elem[i])

    Poscondición: lista=(<elem[0],elem[1],elem[2],...,elem[i-1],elem[i+1],...,elem[n-2]>,elem[i+1]) y retirar=elem[i]

*/

template<class TipoB>

TipoB Lista<TipoB>::retirar()

{

    if(actual == NULL){

        throw ActualNoEstaDefinido();

    }

    // Paso 0.

    Nodo<TipoB> *ap = actual;

    Nodo<TipoB> *ap_ant = ap->obtant();

    Nodo<TipoB> *ap_sig = ap->obtsig();

    // Reencadenar.

    // Paso 1.

    ap_ant->modsig(ap_sig);

    ap_sig->modant(ap_ant);

    // Paso 2.

    ap->modsig(NULL);

    ap->modant(NULL);

    // Paso 3.

    actual = ap_sig;

    TipoB elem = ap->obtinf();

    delete ap;

    return elem;

} // TipoB Lista<TipoB>::retirar();

/*

Operación insertar 

    Descripción: Inserta el elemento nuevo en la lista después del actual y lo pone como actual.

    Descripción operacional: insertar:Lista x TipoB -> Lista

    Prencondición: lista pertenece a Lista y lista=(<elem[0],...,elem[i],elem[i+1],...,elem[n-1]>,elem[i]) y nuevo pertenece a TipoB

    Poscondición: lista=(<elem[0],...,elem[i],nuevo,elem[i+1],...,elem[n]>,nuevo)

*/

template<class TipoB>

void Lista<TipoB>::insertar(TipoB nuevo)

{

    // Paso 0: Pedir la memoria para el nodo.

    Nodo<TipoB> *ap = new Nodo<TipoB>(nuevo);

    if(ap == NULL){

        throw NoHayMemoria();

    }

    // Reencadenar.

    // Paso 1.

    ap->modsig(actual->obtsig());

    ap->modant(actual);

    // Paso 2.

    actual->modsig(ap);

    ap->obtsig()->modant(ap);

    // Paso 3

    actual = ap;

        

} // void Lista:<TipoB>:insertar(TipoB nuevo);

/*

Operación colxact 

    Descripción: Coloca el x-esimo elemento como actual, si no existe ese elemento actual queda nulo.

    Descripción operacional: coliact:Lista x N -> Lista 

    Precondición: lista pertenece a Lista y lista=(<elem[0],elem[1],elem[2],...,elem[i],...,elem[x],...,elem[n-1]>,elem[i]) y 0<=x<n

    Poscondición: lista=(<elem[0],elem[1],elem[2],...,elem[i],...,elem[x],...,elem[n-1]>,elem[x]).

*/

template<class TipoB>

void Lista<TipoB>::colxact(int x)

{

    if(elem == NULL){

        actual = NULL;

        return;

    }

    // Buscar el x-esímo elemento.

    Nodo<TipoB> *ap; // Apuntador al x-esímo.

    int i; // Cuenta cuantos nodos han pasado.

    for(i = 0, ap = elem; i < x && ap != NULL; i++, ap = ap->obtsig()){

    }

    // Poner actual.

    actual = ap;

} // void Lista<TipoB>::colxact();

#endif

//------Fin lista.h

En esta versión las operaciones de insertar y retirar cambian. Veamos el código de insertar:

void Lista<TipoB>::insertar(TipoB nuevo)

{

    // Paso 0: Pedir la memoria para el nodo.

    Nodo<TipoB> *ap = new Nodo<TipoB>(nuevo);

    if(ap == NULL){

        throw NoHayMemoria();

    }

    // Reencadenar.

    // Paso 1.

    ap->modsig(actual->obtsig());

    ap->modant(actual);

    // Paso 2.

    actual->modsig(ap);

    ap->obtsig()->modant(ap);

    // Paso 3

    actual = ap;

        

} // void Lista:<TipoB>:insertar(TipoB nuevo);

Este lo pedemos seguir fácilmente si vemos al mismo tiempo la figura .

Figure: Los pasos de insertar de Listad

El paso 0 es pedir la memoria pera el Nodo que contiene la información. El paso 1 consiste en modificar el anterior y el siguientes del nuevo nodo. El paso 2 modifica al anterior del actual y el anterior del siguiente. Finalmente, el paso 3 esd poner a actual en su valor adecuado.

Ahora veamos la operación de retirar su código es el siguiente:

TipoB Lista<TipoB>::retirar()

{

    if(actual == NULL){

        throw ActualNoEstaDefinido();

    }

    // Paso 0.

    Nodo<TipoB> *ap = actual;

    Nodo<TipoB> *ap_ant = ap->obtant();

    Nodo<TipoB> *ap_sig = ap->obtsig();

    // Reencadenar.

    // Paso 1.

    ap_ant->modsig(ap_sig);

    ap_sig->modant(ap_ant);

    // Paso 2.

    ap->modsig(NULL);

    ap->modant(NULL);

    // Paso 3.

    actual = ap_sig;

    TipoB elem = ap->obtinf();

    delete ap;

    return elem;

} // TipoB Lista<TipoB>::retirar();

Y el seguimiento se puede hacer con la figura .

Figure: Los pasos de retirar de Listad.

El paso 0 es poiner a apuntar unos auxiliares para que el código sea más entendible. El paso 1 es hacer que al naterio y el siguiente salten el nodo que se va a retirar. El paso 2 es poner el anterior y el siguiente de nodo que va a retirar a nulo. Y el paso 3 es poner actual a su valor.