Listas ligadas

Listas ligadas
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 declarar estas estructuras se debía definir un tamaño determinado el cual no podía modificarse posteriormente. Esto puede ser un problema en el caso de que:
* no sepamos de antemano el tamaño requerido paranuestra 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ño de acuerdo a los requerimientos específicos del procedimiento. Así se resuelve el problema de no saber el tama&ntild e;oexacto desde un principio y las manipulaciones de datos se pueden hacer de una manera más 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 su posició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 que sus 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 del manejo de localidades únicamente.
Listas ligadas sencillas
Una lista ligada sencilla es un grupo de datos en dónde cadadato 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.1

CREAINICIO(P)

{Este algoritmo crea una lista, agregando cadanuevo 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. Hacer P->LIGA=NIL
4. Repetir
CREA (Q)
Leer Q->INFORMACIÓNHacer Q->LIGA= P y P = Q

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



Algoritmo 5.2

CREAFINAL(P)

{Este algoritmo crea una lista, agregando cada nuevo nodo al final de la misma}
{P y Q son variables de tipopuntero. 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)
Leer Q->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 intercalar el nuevo nodo en la lista.


Algoritmo 5.3...