8.2.1 Lista simple

El encabezado de ésta implementación es el siguiente:

/*

lista.h

Autor: L. Alejandro Bernal R.

Fecha: 2000.12.06

*/

#ifndef _LISTA_H_

#define _LISTA_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) y sig pertenece a *Nodo y inf pertenece a TipoB 

*/

template<class TipoB>

class Nodo{

    private:

    // Atributos:

    TipoB inf; // Información del nodo.

    Nodo *sig; // Apuntador al siguiente nodo.

    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; }

    /*

    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)

    */

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

}; // 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{

    protected:

    // Atributos:

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

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

    // Operaciones:

    /*

    Operación obtantact

        Descripción: Optiene el apuntador al nodo anterior al actual.

        Descripción operacional: obtantact: Lista -> Nodo*

        Precondición:

        Poscondición: obtantact = ant y (Existe un ant pertenece a elem, ant.sig = actual)

    */

    Nodo<TipoB> *obtantact();

    public:

    // Excepciones:

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

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

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

    // 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; }

    /*

    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();

    /*

    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 obtantact

    Descripción: Optiene el apuntador al nodo anterior al actual.

    Descripción operacional: obtantact: Lista -> Nodo*

    Precondición:

    Poscondición: obtantact = ant y (Existe un ant pertenece a elem, ant.sig = actual)

*/

template<class TipoB>

Nodo<TipoB> *Lista<TipoB>::obtantact()

{

    if(actual == NULL){

         return NULL;

    }

    Nodo<TipoB> *ap; // Reccorre la lista de elementos.

    for(ap = elem; ap->obtsig() != actual; ap = ap->obsig()){

    }

    return ap;

} // Nodo<TipoB> *Lista<TipoB>::obtantact()

/*

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;

        return ;

    }

    Nodo<TipoB> *ap;

    for(ap = elem; ap->obtsig() != NULL; ap = ap->obtsig()){

    }

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

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

        throw NoHayMemoria();

    }

    actual = ap->obtsig();

} // 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();

    }

    Nodo<TipoB> *ap_ant = obtantact();

    Nodo<TipoB> *ap = actual;

    // Reencadenar.

    ap_ant->modsig(ap->obtsig()); // Paso 1.

    ap->modsig(NULL); // Paso 2.

    actual = ap_ant->obtsig(); // Paso 3.

    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)

{

    // Pedir el nodo. Paso 0.

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

    if(ap == NULL){

        throw NoHayMemoria();

    }

    // Reencadenar.

    ap->modsig(actual->obtsig()); // Paso 1.

    actual->modsig(ap);           // Paso 2.

    actual = ap;                  // Paso 3.

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

/*

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]).

*/

template<class TipoB>

void Lista<TipoB>::colultact()

{

    if(elem == NULL){

        actual = NULL;

        return;

    }

    // Encontrar el último.

    Nodo<TipoB> *ap; // Para recorrer la lista de elementos.

    for(ap = elem; ap->obtsig() != NULL; ap = ap->obtsig()){

    }

    // Poner actual como el último

    actual = ap;

} // void Lista<TipoB>::colultact()

/*

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 el anterior código es importante ver en detalle como se inserta. El código de insertar es:

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

{

    // Pedir el nodo. Paso 0.

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

    if(ap == NULL){

        throw NoHayMemoria();

    }

    // Reencadenar.

    ap->modsig(actual->obtsig()); // Paso 1.

    actual->modsig(ap);           // Paso 2.

    actual = ap;                  // Paso 3.

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

Se han numerado los pasos, esto para poder hacer un seguimiento gráfico, que se puede ver en la figura .

Figure: Algoritmo de insertar.

El paso 0 es crear un Nodo contiene la información. El paso 1 es poner como siguiente del nuevo nodo el siguiente de actual. El paso 2 es actualizar el siguiente de el nodo actual. Y finalmente, el paso 3 es poner como actual el nuevo nodo.

También es bueno ver como se retira. El código de retirar es:

template<class TipoB>

TipoB Lista<TipoB>::retirar()

{

    if(actual == NULL){

        throw ActualNoEstaDefinido();

    }

    Nodo<TipoB> *ap_ant = obtantact(); // Paso 0

    Nodo<TipoB> *ap = actual;

    // Reencadenar.

    ap_ant->modsig(ap->obtsig()); // Paso 1.

    ap->modsig(NULL); // Paso 2.

    actual = ap_ant->obtsig(); // Paso 3.

    TipoB elem = ap->obtinf();

    delete ap;

    return elem;

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

Aquí se ha llamado una función obtant que un apuntador al nodo anterior, esto es necesario, por lo que se ve en la figura .

Figure: Retirar de la lista.

El paso 0 consiste en econtrar el nodo anterior al actual y pone a ap a apuntar al actual, esto último por li que ese Nodo será liberado de memoria. El paso 1 consiste en saltar el nodo actual. El paso 2 es poner a nulo el qiguiente de este. Pos último en el paso 3 se pone como actual al siguiente, toma la información y se libera el espacio de memoria apuntado por ap.

El problema de este algoritmo es la llamada a la función obtantact, es muy ineficiente, para resolver esto sería necesario que cada Nodo supiera quién es su antecesor, el anterior. Esto se conoce como una lista doblemente encadenada que será la siguiente forma de implementación.