                  La Implementacin de List.pas

                               por

                          Adolfo Di Mare

                    Reporte Tcnico ECCI-94-06
                       Proyecto 326-93-256
                           Revisin 1.0


Resumen:
=======

Se discute cmo est construida la implementacin del ADT TList en 
sus dos variaciones ms importantes: ListC.pas y List2.pas.  Estas 
dos implementaciones corresponden a la misma abstraccin del  Tipo 
Abstracto  de  Datos  (ADT)    TList,  aunque  su  rendimiento   y 
requerimientos de recursos difieren un poco.

ListC.pas es una implementacin mucho ms completa que  List2.pas, 
pues incluye comportamientos que List2.pas no tiene. Eventualmente 
ListC.pas  ser una  implementacin que subsuma  a List2.pas, pero 
List2.pas continuar existiendo por razones didcticas.

Estas implementaciones  se han  realizado para  el ambiente  Turbo 
Pascal v5.0, aunque para trabajar con ellas es ms cmodo usar  la 
versin v6.0 o una posterior.


Abstract:
========

We discuss  how the  implementation for  TList Abstract  Data Type 
(ADT)  is  constructed  in  its  two  more  important  variations: 
ListC.pas and List2.pas.  These implementations correspond to  the 
same  TList  abastraction,  even  though  their  performance   and 
resource requirements differ a little.

ListC.pas  is  a  more  complete  implementation  than  List2.pas, 
because it includes  behaviours  that  List2.pas  does  not  have. 
Eventually, the ListC.pas implementaqtion will subsume  List2.pas, 
but for didactic reasong List2.pas will continue to exist.

These implementations  have been  made for  the Turbo  Pascal v5.0 
environment, but  it is  less cumbersome  to use  version v6.0  or 
later to work with them.


Esta investigacin se realiz dentro del proyecto de investigacin 
326-93-256 "DBgen: Generacin de Sistemas  a partir de su Base  de 
Datos" inscrito ante  la  Vicerrectora  de  Investigacin  de  la 
Universidad  de  Costa  Rica.   La  Escuela  de  Ciencias  de   la 
Computacin e Informtica tambin ha aportado fondos para realizar 
este trabajo.


                  La Implementacin de List.pas
                  =============================


     Una clasificacin  simple de  los Tipos  Abstractos de  Datos 
(ADTs) los divide en dos tipos bsicos: los simples o elementales, 
y  los contenedores. Un  ADT es un contenedor  si contiene a otros 
ADTs. Los contenedores ms importantes son tres:

     1.- El ADT Arreglo [ARRAY]
     2.- El ADT Lista   [List.pas]
     3.- El ADT Arbol   [Tree.pas]

Existen  otros   ADTs  importantes,   como  Graph.pas,   Heap.pas, 
Matriz.pas,  etc,  pero  la  mayora de  las estructuras  de datos 
importantes se obtienen al combinar inteligentemente a estos  tres 
ADTs.   De todos estos, el ms  importante es, sin duda alguna, el 
Arreglo, hasta el punto de que todos los lenguajes de  computacin 
modernos lo incluyen como una construccin sintctica bsica.

     Despus del ADT Arreglo, la Lista es sin lugar a dudas el ms 
importante de los ADTs contenedores, por lo que es muy  importante 
estudiarlo.  Aunque todos  los  textos  de  Estructuras  de  Datos 
siempre  dedican  una buena  cantidad de  espacio a  este ADT,  es 
importante conocer una implementacin completa por las  siguientes 
razones:

1) La especificacin del ADT TList parece simple a primera  vista, 
   pero en la prctica es  bastante complicada, por lo que  cuando 
   el estudiante logra entenderla entonces aprende en detalle cmo 
   debe disear e implementar sus Tipos Abstractos de Datos.

2) La  mayora de  las implementaciones  del contenedor  TList que 
   aparecen en la  literatura  se  concentran  en  los  trucos  de 
   programacin que se pueden usar para manipular los punteros que 
   permiten implementar listas de  muchas formas, pero en  general 
   los autores no  tratan de definir  de manera bien  estructurada 
   qu es una lista,  hasta  el  punto  de  que  muchas  veces  se 
   confunde  al  ADT  contenedor  TList  con  los  elementos   que 
   contiene.

   La separacin de  funciones entre el  contenedor y el  elemento 
   contenido que  se presenta  en estas  implementaciones del  ADT 
   lista  es muy importantes porque  le muestra al estudiante como 
   crear nuevas estructuras de datos usando Abstraccin de  Datos, 
   lo  que  es  fundamental  para  escribir  cdigo  reutilizable. 
   Adems,  de  esta forma  el estudiantes  aprende a  implementar 
   nuevas estructuras de datos con base en las existentes.

3) Dada la complejidad de esta implementacin, el estudiante tiene 
   la  oportunidad de  comprender cules son  las limitaciones que 
   tiene el uso de Tipos Abstractos de Datos para la  construccin 
   de programas sofisticados.

     El  ADT  lista es  el contenedor  que sirve  para representar 
secuencias de elementos  en computador.  Una  lista L contiene  un 
conjunto  finito  de  elementos  organizados  de  acuerdo  a   las 
siguientes propiedades:

a) L es un conjunto finito,  o vaco, de elementos almacenados  en 
   "nodos" [Empty(L)].

b) Cada nodo de la lista est conectado a su sucesor por medio  de 
   un enlace [Next(L,p)-Prev(L,p)].

c) Un lista no vaco siempre tiene nico nodo inicial [First(L)] y 
   un nodo final [Last(L)].

d) Cada nodo en la lista, excepto el primero, tiene un nico  nodo 
   que le precede [Prev(L)].

e) La longitud de  la lista  es el  nmero de  nodos que  contiene 
   [Count(L)].

f) Para accesar un nodo en la lista es necesario recorrerla  desde 
   el principio.

g) En general, una lista  es  una  estructura  de  datos  que  usa 
   memoria  dinmica  por  lo  que su  tamao y  requerimientos de 
   memoria pueden variar en tiempo de ejecucin.

     En el siguiente diagrama se muestra una lista:

               L = [a]->[b]->[c]->[d]->[e]->[f]
                   ^ ^             ^         ^
                  /  |             |         |
                 /   |             |         |
                /    |             |         |
               p  First(L)         q      Last(L)


     Para definir  la lista  como un  Tipo Abstracto  de Datos  es 
necesario distinguir entre un nodo  de la lista, el contenido  del 
nodo y su posicin  en la lista.  En  este diagrama los nodos  son 
las cajitas  ([a]...[f])   que  estn  ligadas  en  secuencia,  el 
contenido  de cada  nodo es lo  que aparece dentro  de cada cajita 
("a".."f"),  y la  posicin de cada  nodo es un  apuntador al nodo 
(@[d]=q).  Por ejemplo, la posicin del primer nodo de la lista es 
p=@[a]=First(L).

     Para  no cargar  mucho la notacin,  en este documento  no se 
hace distincin entre un nodo de  la lista y su contenido, por  lo 
que en lugar de hablar de "la posicin del primer nodo de la lista 
L" simplemente se dice que p=@a=First(L), o sea que el primer nodo 
de L se denota  con @a: la notacin  "@" sirve para distinguir  al 
valor  del  nodo de  su posicin  en el  lista.  Esta  notacin es 
ambigua pues no permite representar un  lista en que dos o ms  de 
sus nodos tienen el mismo valor, aunque es ms cmoda de usar.  De 
acuerdo a esta convencin, el  diagrama del lista L es  cualquiera 
de estas dos:
               L = a->b->c->d->e->f

               L = (a,b,c,d,e,f)

     En general, las lista se denotan encerrando entre  parntesis 
entre los valores de sus elementos: L=(a,b,c,d,e,f).

     Como  se muestra en  el diagrama de L,  este lista cumple con 
las siguientes propiedades del ADT TList:

- L no est vaca: Empty(L) = FALSE.

- El primer node de L es [a]: @a=Fisrt(L).

- El segundo nodo de L es el que contiene a "b", y el penltimo es 
  el que contiene "e":

  @b = Next(L, @a) = Next(L, First(L))
  @e = Prev(L, @f) = Prev(L, Last(L))


Abstraccin de TList
====================

     Para almacenar una lista en el computador es necesario  crear 
una  abstraccin  del  concepto  "lista", la  que luego  puede ser 
cristalizada en  la implementacin  del ADT  lista.  Para  definir 
esta abstraccin es necesario definir los elementos que forman una 
lista:
     1) Nodos
     2) Valor almacenado en cada nodo    [Unidad Elem.pas]
     3) Posicin en el lista
     4) Aristas de enlace entre nodos.

     En  la  implementacin, a  cada uno  de estos  conceptos debe 
corresponder un tipo de datos o un campo en una instancia. En esta 
implementacin, la correspondencia es la siguiente:

     1) Nodo       Tipo    TNode_RepList  List.pas
     2) Valor      Tipo    TElem          Elem.pas
     3) Posicin   Tipo    PLpos          List.pas
     4) Arista     Campo   punteros       List.pas

     Es  importante   destacar  que   existen  muchas   formas  de 
implementar  el ADT  lista, cada una  de las que  tiene diferentes 
ventajas  que en general comportan  una mejora de rendimiento para 
realizar una o varias de las operaciones.  Por ejemplo, en algunas 
implementaciones no  es  necesario  representar  directamente  las 
aristas, pues con base en la posicin relativa de los nodos de  la 
lista se puede deducir cuales  son los enlaces entre nodos.   Este 
hecho se usa en  la implementacin del ADT  TList por medio de  un 
vector de elementos.

     Para incrementar la modularidad del ADT, la implementacin de 
TList consta  de  dos  unidades  Pascal.   La  primera,  List.pas, 
contiene todo el cdigo que implementa al ADT Lista. La segunda es 
la unidad llamada  Elem.pas, que tiene  todas las operaciones  del 
ADT elemental contenido en la lista. Este ADT elemental puede ser, 
a su vez, otro contenedor. El ADT lista puede contener a cualquier 
otro  ADT para el que  estn definidas las operaciones elementales 
que usa List.pas para manipular a Elem.pas.

     Para adaptar  el lista  a diferentes  ADTs elementales  basta 
cambiar el nombre del ADT elemental  usado en el lista, lo que  se 
puede hacer con relativa facilidad usando un editor de texto  para 
modificar el programa  fuente  List.pas.   Para  facilitarle  este 
trabajo al programador usuario de TList, en el mdulo List.pas hay 
un recuadro llamado  PARAMETERS  que  tiene  los  nombres  de  los 
identificadores que es necesario cambiar si el elemento  contenido 
en el lista no se llama "Elem".

     El concepto de lista en Computacin es muy amplio, por lo que 
a veces no queda bien  definido.  Esta abstraccin se ha  escogido 
porque   permite   definir  sobre   ella  todas   las  operaciones 
importantes  asociadas   con  listas.    En  este   sentido,  esta 
abstraccin  es  muy  "general",   lo  que  tiene  gran   utilidad 
didctica.

     Despus  de definir  la abstraccin para  TList han realizado 
dos implementaciones. La primera implementacin est en el  mdulo 
ListC.pas, que usa una lista circula con puntero al ltimo nodo de 
la lista.  La otra implementacin est en List2.pas, que usa nodos 
dobles para construir una lista doblemente enlazada con puntero al 
primero  nodo  de  la  lista.   Como  estas  dos  implementaciones 
corresponden  a  la   misma  abstraccin,  necesariamente   tienen 
exactamente las mismas operaciones, aunque el rendimiento en  cada 
operacin  puede  ser  diferente,  porque  el  rendimiento  y  los 
requerimientos  de memoria de  cada implementacin son diferentes. 
Si   un   programa  es   implementado  usando   una  de   las  dos 
implementaciones, entonces tambin funcionar con la otra, pero lo 
que seguramente variar es el rendimiento del programa.

     Precisamente   porque  ListC.pas   y  List2.pas  corresponden 
exactamente  a la  misma abstraccin del  ADT TList es  por lo que 
cualquier  programa  que funcione  con una  implementacin tambin 
puede usar la otra.

     Para usar el ADT TList,  el programador usuario del ADT  debe 
copiar uno  de los  dos archivos  ListC.pas o  List2.pas sobre  el 
archivo List.pas.


Operaciones
===========

     Como  ocurre cuando  el programador usa  a la mayora  de los 
ADTs contenedores, las operaciones sobre la lista deben permitirle 
definir sobre cul de todos los nodos del lista desea actuar. Para 
definir una posicin en el lista se usa el tipo de datos PLpos.

     Una variable de tipo PLpos es  un puntero a uno de los  nodos 
de  la  lista.   Como  este tipo  est definido  como parte  de la 
abstraccin del ADT lista, entonces un PLpos es puntero Pascal que 
no puede ser  derreferenciado.   Esto  quiere  decir  que  si  una 
variable  "p" es  de tipo PLpos,  entonces nunca puede  ser vlido 
manipular aquello a lo que apunta:

     VAR
       p : PLpos;
     ...
     p^ := ....;   {  ERROR !!! }
     FunProc(p):   { OK }

     El ADT lista tiene todas las operaciones de un ADT elemental. 
Estas operaciones son las siguientes:

     Init(L):     Constructor; inicializa la lista.
     Clear(L):    Limpia la lista.
     Done(L):     Destructor; destruye a la lista.

     Copy(x,y):   Copia el valor de la lista "y" en "x".
     Move(x,y):   Le traslada a "x" el valor de la lista "y".

     Equal(x,y):  Compara el valor de "x" con el de "y".
     Less(x,y):   Compara el valor de "x" con el de "y".

     Load(L,F):   Carga el valor de "L" desde el archivo "F".
     Store(L,F):  Almacena el valor de "L" en el archivo "F".

     OK(L):       Verifica la invariante del ADT.
     Fix(L):      Repara listas.

TList tiene todas las operaciones de un ADT contenedor:

     Empty(L):        Verifica si la lista est vaca.
     Count(L):        Cantidad de elementos de la lista.

     Behave(L,b,sw):  Cambia el comportamiento de la lista.
     Behaviour(L,b):  Verifica si "L" tiene el comportamiento "b".

     Retrieve(L,p):   Transforma una posicin en puntero al valor.
     Locate(L,x):     Busca un valor en la lista.
     Valid(L,p):      TRUE si "p" es una posicin de L.

     La operacin  Retrieve(L,p)   retorna  un  puntero  al  valor 
almancenado  en uno de los nodos  de la lista "L".  Esta operacin 
es  muy importante porque  es la que separa  al contenedor, que en 
este  caso es el  ADT TList, de su  elemento contenido, TElem.  La 
existencia  de esta operacin se  justifica porque muchas veces el 
programador  necesita   escribir  algoritmos   que  manipulan   la 
estructura de la lista, sin  importar cul es su contenido.   Como 
en  esta abstraccin se  separa la estructura del  lista de lo que 
contiene, entonces los algoritmos que slo manipulan la estructura 
de  la lista  no necesitan ser  reprogramados cuando se  cambia el 
tipo  de valor almacenado en  la lista: la operacin Retrieve(L,p) 
los independiza de ese valor.

     Si, por el contrario,  el programador necesita manipular  los 
valores  de los elementos almacenados  en la lista, entonces puede 
accesarlos en dos pasos: primero debe obtener la posicin "p"  del 
nodo de la lista, y luego  puede obtener el valor del nodo  usando 
Retrieve(L,p).

     La  operacin  Count(L) siempre  aparece en  los contenedores 
pues retorna el nmero total de elementos; en el caso de la lista, 
retorna el nmero de nodos de la lista.

     Las  operaciones  arriba descritas  son comunes  a todos  los 
contenedores. Lo que realmente define  al ADT lista son las  dems 
operaciones,  las que  pueden ser ejecutadas  eficientemente en la 
estructura de datos de la lista.  La operacin para agregar  nodos 
al lista, al insertarle valores, es InsertA().

     InsertA(L,p,e) inserta al elemento "e" de forma que quede  en 
en nodo que sigue  al nodo cuya posicin  en el lista "L"  es "p". 
Por ejemplo, para agregarle el  nodo "x" como segundo elemento  de 
la lista "L" se debe invocar a InsertA() de la siguiente forma:

     L = a->b->c->d->e->f

          InsertA(L, First(L), x)

                   L = a->x->b->c->d->e->f

     Para insertar  en la  primera posicin  de la  lista hay  que 
especificar la posicin nula, List.Null, como segundo argumento de 
InsertA():
- InsertA(L, List.Null, x): inserta "x" al principio de "L".

     La operacin Cut() permite trasladar una sublista completa de 
una lista a  otra.  List.Cut(L1,r, L2,p,q)   es una operacin  que 
complementa  a  InsertA() porque  traslada la  sublista de  L2 que 
ocmienza despus de  la posicin "p"  de L2, y  que termina en  la 
posicin  "q",  y la  traslada de  forma que  quede despus  de la 
posicin "r" de la lista L1:

  Listas           Posiciones    Sublista  Resultado
  =======          ==========    ========  ===============
  L = (A,B,C)        r=@A                  L = (A,3,4,B,C)
  L2= (1,2,3,4,5)    p=@2, q=@4    [3,4]   L2= (1,2,5)
         p-->q
                      Cut(L,r, L2,p,q)

     Para manipular al lista el programador necesita poder obtener 
la posicin de los nodos del lista.  Las operaciones que  retornan 
posiciones en el lista son:

     First(L):  Retorna la posicin del primer nodo de lista.
     Last(L):   Retorna la posicin del ltimo nodo de lista.
     Next(L,p): Posicin del nodo que sigue al nodo "p".
     Prev(L,p): Posicin del nodo que precede al nodo "p".

     En algunas ocasiones el  programador necesita usar una  lista 
como  si fuera un arreglo, aunque  a sabiendas de que la velocidad 
de proeceso  esta  estructura  de  datos  para  estas  operaciones 
decrece  conforme aumenta el tamao  de la lista.  Las operaciones 
tiles para esto son Lpos() y Lind():
     Lpos(L,i): Posicin del i-simo nodo de la lista.
     Lind(L,p): Indice del nodo est en la posicin "p" de L.
Lpos() es el inverso de Lind():
     p = Lind(L, k) <==> k = Lpos(L, p)

     Estas  operaciones  le permiten  al progamador  moverse a  lo 
largo  de  la lista.   Generalmente el  recorrido comienza  por el 
principio  de la lista, aunque  tambin puede usarse Locate() para 
encontrar un nodo especfico en el lista.

               L = a->b->c->d->e->f

     @a = First(L)     @f = Last(L)

     @b = Next(L, @a) = Next(L, First(L))
     @e = Prev(L, @f) = Prev(L, Last(L))

     Lpos(L,0) = List.Null        Lind(L,Null) = 0
     Lpos(L,1) = First(L) =@a  1= Lind(L,@a) = Lind(L, First(L))
     Lpos(L,6) = Last(L)  =@f  6= Lind(L,@f) = Lind(L, Last(L))

     @a = Locate(L,"a")        @f = Locate(L,"f")

     Como tanto  Lpos() como  Lind() son  operaciones de  uso poco 
frecuente, ambas aceptan como argumento a List.Null y a 0.

     La operacin que complementa a InsertA() es DeleteA(L,p), que 
es  la  que  permite  eliminarle nodos  al lista.   Esta operacin 
elimina de la lista L al nodo que est despus de la posicin "p":

     L = a->b->c->d->e->f

          DeleteA(L, First(L), x)

                   L = a->c->d->e->f

     En  algunas implementaciones la  operacin de borrado incluye 
un  tercer argumento para que en  l DeleteA()  deje una copia del 
elemento  que  se  elimina  de  la  lista.   El  inconveniente  de 
especificar  DeleteA()   de  esa  manera  es  que  se  obliga   al 
programador a pagar el costo de copiar el elemento cada vez que se 
hace un borrado.  Si el  programador necesita ese valor, lo  puede 
copiar  usando  las operaciones  List.Retrieve(), y  Elem.Copy() o 
Elem.Move(), como  se  muestra  a  continuacin  en  el  siguiente 
esqueleto de programa:

     VAR
       pe: PElem;
       e:  TElem;
       p:  PLpos;
     { ... }

     { obtiene el puntero al elemento }
     pe := List.Retrieve(L, p);

     { obtien el valor a eliminar }
     IF Behaviour(L, Insert_using_Copy) THEN BEGIN
       Elem.Copy(e, pe^);
     END
     ELSE BEGIN
       Elem.Move(e, pe^);
     END:

     { borra el nodo de la lista }
     DeleteA(L, p);

     Delete_All(L) es otra operacin que permite eliminar nodos de 
una  lista,  pues  de  hecho los  elimina a  todos.  Al  invocar a 
Clear(L)  tambin se  obtiene  este  resultado,  pero  Clear(),  a 
diferencia de Delete_All(), tambin cambia el comportamiento de L, 
pues lo restaura  al valor que  tuvo despus de  ser inicializada.  
Delete_All() es la  operacin que en  general usa el  programador, 
mientras que Clear() es til ms  bien al principio o final de  un 
bloque de operaciones sobre la lista.

     Para permitirle al programador usuario de TList controlar con 
mayor efectidad el rendimiento de su programa, se ha aumentado  la 
funcionaliad de ListC.pas incluyndole la capacidad de manejar una 
batera de nodos borrados.

     La  utilidad  de  la  batera  de  borrados  la  disfruta  el 
programador   cuando  en  una   aplicacin  debe  realizar  muchas 
inserciones y borrados consecutivamente. En este caso es til  que 
TList no devuelva al manejador  de memoria dinmica los nodos  que 
son desechados mediante la operacin List.DeleteA(), de manera que 
cuando se invoque  de nueve a  List.InsertA() se pueda  tomar, con 
gran rapidez, un nodo de la batera de borrados para completar  la 
insercin  del nodo en  la lista.  Para controlar  el tamao de la 
batera  de  borrados  el  programador  debe  usar  la   operacin 
List.Prepare(L,n),  que hace  que esa lista  tenga exactamente "n" 
nodos. La operacin Count_Del(L) retorna el nmero de borrados  de 
que  tiene  la  batera.   Para activar  el uso  de la  batera de 
borrados el programador usuario de TList debe usar las operaciones 
Behave() y Behaviour().

     Para  mejorar el  rendimiento del programa  de aplicacin, la 
batera de borrados se maneja como si fuera una pila, de forma que 
los ltimos  nodos que  han sido  eliminados de  la lista  son los 
primero  en ser  destruidos por List.Prepare(L,n).   Esto tiende a 
darle una vida ms larga a los nodos ms viejos, lo que en general 
hace que el manejador de memoria dinmica sea ms eficiente.


Modelo
======

     El  modelo del ADT  es un diagrama de  la estructura de datos 
usado para implementarlo.  En todos los libros de texto las listas 
se  representan como estructuras de  datos compuestas de nodos que 
estn  enlazados  por medio  de punteros,  como se  muestra en  el 
siguiente modelo:

          Ŀ   Ŀ   Ŀ   Ŀ
     L> A  > B  > C  > D  >NIL
                   

     Cada  nodo es un registro Pascal  que tiene dos campos: el de 
informacin, y un puntero al siguiente nodo. El ltimo nodo  tiene 
el valor NIL, que  es el usado en  Pascal para denotar al  puntero 
nulo.  Esta forma de representar la  lista es muy cmoda, pues los 
algoritmos principales de la lista pueden implementarse usando muy 
pocas  instrucciones Pascal.  Por ejemplo, para  insertar un nuevo 
nodo  despus  de "B"  basta crear  un nuevo  nodo, y  enlazar los 
punteros:

          Ŀ   Ŀ   Ŀ   Ŀ
     L> A  > B    > C  > D  >NIL
                  
                               
                            v   
                          Ŀ
                           X   
                          

     El problema  principal  de  esta  implementacin  es  que  la 
operacin  Last()   requiere tiempo  de ejecucin  proporcional al 
tamao de la lista para calcular su resultado. La solucin a  este 
dilema  es representar una lista con  un puntero al ltimo nodo de 
la lista, y enlazar este nodo la siguiente, como se muestra en  el 
modelo que corresponde a la implementacin de ListC.pas:

     L >Ŀ
                                                  
                                                  v
          Ŀ   Ŀ   Ŀ   Ŀ
      > A  > B  > C  > D  Ŀ
                    
      <<<

     La mayora de los libros de texto no usan este modelo  porque 
la  implementacin  de InsertA()   y Delete()   es un  poquito ms 
complicada, aunque no mucho en realidad. Como ListC.pas es una ADT 
cuya implementacin ha evolucionado a lo largo de varios aos,  la 
implementacin escogida del ADT lista ha sido la que corresponde a 
este modelo, pues en  este  caso  la  operacin  Last()  se  puede 
implementar  con  myor eficiencia.   Tambin esta  implementacin 
permite  que  List.Cut()   pueda  trasladar  sublistas  tanto   al 
principio como al final de la lista usando una cantidad  constante 
de tiempo, independientemente del tamao de la listas.

     La otra operacin que tiene un gran impacto en el modelo  que 
se escoge para implementar una lista es la operacin  List.Prev(). 
Como  todos los punteros apuntan  al siguiente nodo, entonces para 
encontrar  el predecesor de un  nodo siempre es necesario recorrer 
toda la lista.  La obvia solucin a esta restriccin es incluir en 
cada nodo un puntero al nodo anterior de cada nodo:

     L >Ŀ
                                                 
                                                 v
       <<<Ŀ
          Ŀ   Ŀ   Ŀ  
       >       >       >       >
       Ĵ  A    <Ĵ  B    <Ĵ  C    <Ŀ
                  
       >>>

     Este  modelo  es la  extensin natural  de la  lista circular 
implemlentada en ListC.pas.   Sin  embargo,  por  razones  razones 
histricas,  el  modelo usado  en la  implementacin de  las lista 
doblemente enlazada List2.pas no es este, sino uno ms sencillo en 
que en lugar de que "L" apunte al ltimo nodo de la lista,  apunta 
al primero como se muestra a continuacin.

     L >Ŀ           List2.pas
                 
                 v
       <<<Ŀ
          Ŀ   Ŀ   Ŀ  
       >       >       >       >
       Ĵ  A    <Ĵ  B    <Ĵ  C    <Ŀ
                  
       >>>

    El usar este modelo hace que la implementacin cada  operacin 
de List2.pas sea  bastante diferente a  la de ListC.pas,  pues las 
diferencias no se limitan al cdigo que actualiza el puntero hacia 
atrs  en  List2.pas. Sin  embargo, como  las implementaciones  de 
listas  de  la  mayora  de los  libros de  texto usan  listas que 
apuntan al primer nodo, y no al ltimo, de hecho la implementacin 
de  List2.pas es similar a las de  los libros de texto, lo que les 
ayuda a los  estudiantes a entender  el cdigo tanto  de ListC.pas 
como de List2.pas.

     Aunque  List2.pas   cuenta  tiene   exactamente  las   mismas 
operaciones que ListC.pas, no toda la funcionalidad que  ListC.pas 
se ha  incorporado  en  List2.pas,  pues  eventualmente  ListC.pas 
evolucionar hasta el punto de tener la capacidad de manejar tanto 
nodos simples como nodos dobles, que son lo distingue a  List2.pas 
de ListC.pas.

     El Rep de ListC.pas contiene cuatro campos.  "_bhvr" tiene el 
conjunto de comportamientos de la  lista, "_excp" es para uso  del 
manejador  de  excepciones, "_last"  apunta al  ltimo nodo  de la 
lista, y "_free" apunta al ltimo nodo de la batera de  borrados. 
El modelo para ListC.pas es el siguiente:

        L                 ListC.pas
  Ŀ
   _last >Ŀ
  Ĵ                                         
   _bhvr                                          
  Ĵ                                         
   _excp                                          
  Ĵ           L = (A,B,C,D)                 
   _free                                          
                                           
                                                   v
           Ŀ   Ŀ   Ŀ   Ŀ
       > A  > B  > C  > D  Ŀ
                     
       <<<
      
      >Ŀ
                                                    
                   Borrados = (,,)               
                                                    v
                        Ŀ   Ŀ   Ŀ
                    >   >   >   Ŀ
                               
                    <<<

     El modelo usado en ListC.pas es el de una lista circular, con 
un  puntero  al  ltimo  nodo.  Adems,  ListC.pas cuenta  con una 
batera  de borrados implementada como  una lista circular.  El de 
List2.pas es  el de  una lista  circular doblemente  enlazada, con 
puntero al primer nodo de la lista, aunque List2.pas no puede usar 
la batera de borrados.


Comportamientos
===============

     Para aumentarle  la  utilidad  de  su  ADT  el  implementador 
siempre trata de  trata de lograr  que su ADT  sea lo ms  general 
posible.   Para  esto define  varios comportamientos,  los que  le 
permiten  al programador usuario ajustar  el ADT a sus necesidades 
personales. Para agregarle un comportameinto al ADT el programador 
usuario inovoca a la funcin Behave(L,b,TRUE), la que le agrega  a 
"L" el comportamiento "b", pero  slo si es vlido hacerlo.   Para 
quitarle el comportamiento se usa Behave(L,b,FALSE).

     Los comportamientos implementados para el ADT TList son  dos: 
Insert_using_Move y Use_Free_Nodes.

     Cada vez que se inserta un valor en el lista por medio de  la 
operacin InsertA(L,p,x), es necesario copiar o trasladar el valor 
de "x" al nuevo  nodo del lista.  Cuando  el lista "L" incluye  el 
comportamiento  Insert_using_Move   entonces  Insert(L,p,x)    usa 
Elem.Move() para trasladar el  valor de "x" al  nodo, y si no  usa 
Elem.Copy() para copiar el valor "x" al nodo.

     Si el lista  "L"  incluye  al  comportamiento  Use_Free_Nodes 
entonces L administra el programador puede usar la batera denodos 
borrados de la lista, y de lo contrario todas las operaciones  que 
tengan que sirven para manipularla no tendrn ningn efecto.


Detalles de implementacin
==========================

     En general la parte ms compleja en la implementacin del ADT 
TList es  la manipulacin  de punteros,  pues un  pequeo descuido 
puede  resultar  en  puntero  roto, que  en general  tiene efectos 
impredecibles en el programa.  Precisamente por lo difcil que  es 
manipular  punteros   se  justifica   usar  ADTs,   pues  permiten 
encapsular  su   uso  en   un  mdulo   que  puede   ser  depurado 
independientemente del resto del programa.

     Desgraciadamente en este ADT no se logra una separacin total 
entre el ADT contenedor y su elemento contenido. De hecho, un nodo 
est compuesto de la agregacin del TElem junto con los campos que 
manipula  el  ADT  TList.   El principal  problema de  mezclar los 
campos del contenedor con los del elemento contenidos es que si en 
un programa se  necesita usar dos  tipos de lista,  ser necesario 
crear  dos copias completas  del ADT TList, una  para cada tipo de 
elemento.   Ms an,  es imposible que  un mismo elemento  est en 
varios contenedores a menos que el contenedor use punteros a  cada 
elemento.  En  algunos lenguajes  modernos, como  C++ y  ADA, esta 
restriccin se soluciona, de forma parcial y poco elegante, con el 
uso  de  Tipos  Parametrizados,  llamados  plantillas  o  paquetes 
genricos.   Existe  una solucin  alterna, pero  requiere de  una 
filosofa de construccin de programas bastantes diferente, aunque 
su  uso incrementa  significativamente la modularidad  de los ADTs 
as  usados,  lo que  se logra  con la  unidad Binder.pas,  que se 
describe en otro documento.

     Otra  incomodidad bastante grande  que debe sobrellevar quien 
use el ADT  TList es que  debe definir un  ADT de tipo  TElem para 
usar el contendor. En muchas ocasiones los programdores encuentran 
esto tan  engorroso que  terminan cambiando  la implementacin  de 
TList para evitar  la proliferacin de  tipos TElem.  Esto  ocurre 
cuando se necesita  una  lista  simple,  que  contiene  nmeros  o 
letras,  pues en estos  casos el definir todo  un ADT para objetos 
tan  simples es un trabajo  demasiado grande (aburrido?)  para el 
programador.

     El  tipo PLpos  se implementa como  un puntero que  apunta al 
mismo tipo, de forma que el programador no puede  derreferenciarlo 
y  usarlo.   En  la  implementacin estos  PLpos son  covertidos a 
punteros a nodos, de tipo PNode_RepList.


Bibliografa
============

[1] Aho, Alfred V.; John E.  Hopcroft; Jefrrey  D.  Ullman:  "Data 
    Structures and Algorithms"; 1983. [AHO-83].

[2] Borland; "Turbo Pascal Version 5.5"; 1984.

[3] Liskov, Barbara; Gutag,  John; "Abstraction  and Specification 
    in Program Development"; McGraw-Hill; 1986.

[4] Di Mare, Adolfo:  "Convenciones de  Programacin para  Pascal, 
    Revisin 2"; Reporte tcnico ECCI-01-88, ECCI-UCR, 1988.

[5] Di  Mare, Adolfo:  "Abstraccin de  Datos en  Pascal"; Reporte 
    tcnico PIBDC-01-89, ECCI-UCR, 1991.

[6] Horowitz, E.; Sahni,  S.: "Fundamentals  of Data  Structures"; 
    Computer Science Press; 1982.


               Reportes tcnicos de Adolfo Di Mare
               ===================================

     Los siguientes Reportes Tcnicos, todos confeccionados por el 
mismo autor, describen todos  las implementaciones y algunos  usos 
importantes de los ADTs programados en Turbo Pascal en al  Escuela 
de Ciencias de la Computacin e Informtica, de la Universidad  de 
Costa Rica. 

     Todas estas  implementaciones estn  disponibles en  Internet
por medio de ftp annimo en el directorio:

     http://www.di-mare.com/adolfo/p/src/List.zip

     Los derechos de autor  estn reservados  a nombre  del autor,
Adolfo Di Mare.

     El texto de cada Reporte Tcnico se encuentra  en el  archivo
de texto nombrado entre parntesis cuadrados.

[R1]  "Prueba  interactiva  de  ADTs", Reporte  Tcnico ECCI-94-01
      [Archivo UseADT.doc]; Mayo, 1994.

[R2]  "La Implementacin de Elem.pas"; Reporte  Tcnico ECCI-94-02
      [Archivo Elem.doc]; Mayo 1994.

[R3]  "La   Implementacin   de  Rational.pas";   Reporte  Tcnico
      ECCI-94-03 [Archivo Rational.doc]; Mayo 1994.

[R4]  "La Implementacin de Poly.pas"; Reporte  Tcnico ECCI-94-04
      [Archivo Poly.doc]; Mayo 1994.

[R5]  "La    Implementacin  de   ListAHO.pas";  Reporte   Tcnico
      ECCI-94-05 [Archivo Aho.doc]; Mayo 1994.

[R6]  "La Implementacin de List.pas"; Reporte  Tcnico ECCI-94-06
      [Archivo List.doc]; Mayo 1994.

[R7]  "La Implementacin de Tree.pas"; Reporte  Tcnico ECCI-94-07
      [Archivo Tree.doc]; Mayo 1994.

[R8]  "La Implementacin de Heap.pas"; Reporte  Tcnico ECCI-94-08
      [Archivo Heap.doc]; Mayo 1994.

[R9]  "Uso  de  la  unidad Test.pas";  Reporte Tcnico  ECCI-94-09
      [Archivo Test.doc]; Mayo 1994.

[R10] "Manejo  de excepciones  en Turbo  Pascal"; Reporte  Tcnico
      ECCI-94-10 [Archivo Except.doc]; Mayo 1994.
