Algoritmos de listas ligadas

Listas ligadas http://www.sistemas.ith.mx/msanchez/estdat/punto1_8_clip_image001_0000.gif
http://ict.udlap.mx/people/ingrid/Clases/IS211/ListaLig.gif
En las secciones anteriores se contemplaron diferentes estructuras estáticas en dónde la manipulación de datos es a través de posiciones localizadas secuencialmente. Para de clarar estas estructuras se debía definir un tamaño determinado el cualno podía modificarse posteriormente. Esto puede ser un problema en el caso de que:
* no sepamos de antemano el tamaño requerido para nuestra aplicación
* hay una gran cantidad de operaciones y manipulaciones de los datos dentro de las estructuras
En estos casos es generalmente m&a acute;s conveniente utilizar estructuras dinámicas, es decir, las cuales pueden aumentar o disminuir de tamañode acuerdo a los requerimientos específicos del procedimiento. Así se resuelve el problema de no saber el tama&ntild e;o exacto desde un principio y las manipulaciones de datos se pueden hacer de una manera mas rápida y eficiente.
Una lista ligada es entonces un grupo de datos organizados secuencialmente, pero a diferencia de los arreglos, la organización no esta dada implícitamente por suposición en el arreglo. En una lista ligada cada elemento es un nodo que contiene el dato y además una liga al siguiente dato. Estas ligas son simplemente variables que contienen la(s) dirección(es) de los datos contiguos o relacionados.
Para manejar una lista es necesario contar con un apuntador al primer elemento de la lista "head" .
Las ventajas de las listas ligadas son que:
* Permiten quesus tamaños cambien durante la ejecución del programa
* Proveen una major flexibilidad en el manejo de los datos.
Este principio de listas ligadas se puede aplicar a cualquiera de los conceptos de estructura de datos vistos anteriormente: arreglos, colas y pilas . Es decir, las operaciones de altas, bajas y cambios, así como búsquedas y ordenamientos se tendrán que adaptar en la cuestión delmanejo de localidades únicamente.
 
Listas ligadas sencillas
Una lista ligada sencilla es un grupo de datos en dónde cada dato contiene además un apuntador hacia el siguiente dato en la lista, es decir, una liga hacia el siguiente dato.

Los siguientes algoritmos fueron tomados de "Estructuras de Datos", Cairó - Guardati, 2a. Ed., McGraw Hill, 2002.

Algoritmo 5.1CREAINICIO(P)

{Este algoritmo crea una lista, agregando cada nuevo nodo al inicio de la misma}
{ P y Q son variables de tipo puntero. P apuntará al inicio de la lista}

1. CREA (P) {Crea el primer nodo de la lista}
2. Leer P->INFORMACIÓN
3. HacerP->LIGA=NIL
4. Repetir
CREA (Q)
Leer Q->INFORMACIÓN
Hacer Q->LIGA= P y P = Q

5. Hasta (que ya no haya información)



Algoritmo 5.2

CREAFINAL(P)

{Este algoritmo creauna lista, agregando cada nuevo nodo al final de la misma}
{P y Q son variables de tipo puntero. P apuntará al inicio de la lista}

1. CREA (P) {Crea el primer nodo de la lista}
2. Leer P->INFORMACIÓN
3. Hacer P->LIGA=NIL y T=P
4. Repetir
CREA (Q)
LeerQ->INFORMACIÓN
Hacer Q->LIGA=NIL, T->LIGA=Q y T=Q
5. Hasta (que ya no haya información)


Para poder dar de alta un dato en una lista ligada sencilla es necesario recorrer la lista nodo por nodo hasta encontrar la posición adecuada. Se crea un nuevo nodo, se inserta el dato y se actualizan las ligas del nodo nuevo y del anterior para...