Tad Lista

Especificación formal del TAD lista
Una lista consiste en una cantidad arbitraria de elementos ordenados. Una Lista es, a la vez, un TD (tipo de datos), un TAD (tipo abstracto de datos) o una ED(estructura De datos). La especificación formal más simple del tipo lista son las Listas simplemente Enlazadas. Una lista simplemente enlazada está constituida por una cantidad arbitraria de elementosdel mismo tipo donde todo elemento lleva un enlace al siguiente elemento de la Lista. Además, el enlace del último elemento es un valor especial FIN DE LISTA (NIL) y Un enlace específico permiteacceder al primer elemento de la lista. Las listas simplemente enlazadas: constituyen un tipo de datos, un tipo abstracto de datos y una estructura de datos.
El Tipo de Datos:
Existen diferentesformas sencillas de Representación de una lista simplemente
Enlazada como son:
Lista] →{elem;p]→{elem;p] → .... → {elem;p]→{elem;p]→
Lista elem elem elem elem
Implementación de la lista conestructura dinámica
Las Estructuras Dinámicas de Datos (EDD) son las que utilizan una cantidad de memoria variable. Se construyen utilizando el tipo de datos punteros o apuntador: cuyos valorescorresponden a direcciones de memoria (entre las que se incluye una dirección nula especial denominada NIL). Las operaciones usuales del correspondiente tipo abstracto de datos son: NEW y DISPOSE. El tipode datos abstracto concreto que se implementa depende de la declaración. Es necesario diferenciar claramente entre la variable apuntadora (declarada de la forma ^Tipo) y la variable apuntada(declarada a continuación, generalmente como un registro;
Tipo RECORD …).
La estructura dinámica de datos se puede representar de la forma:
p]-->(v q]-->(u
Un ejemplo de la posible declaraciónpara un tipo de datos dinámico elemental es
la siguiente:
TYPE Tipo_P = ^Tipo_V ;
VAR p,q : Tipo_P
Las operaciones de asignación y comparación:
p := q ; p^ := q^ ; p = q ; p^ = q^ ;...