Estructura De Datos

Listas |

Introducción
Las estructuras de datos presentadas hasta el momento, arreglos y registros, se denominan estáticas. Reciben este nombre debido a que durante la compilación se les asigna un espacio de memoria, y este permanece inalterable durante la ejecución del programa.

En este tema se presenta la estructura de datos lista. Este es un tipo de estructura lineal y dinámica de datos.Lineal porque a cada elemento le puede seguir solo otro elemento; dinámica porque se puede manejar la memoria de manera flexible, sin necesidad de reservar espacio con antelación.
La principal ventaja de manejar un tipo dinámico de datos es que se pueden adquirir posiciones de memoria a medida que se necesitan; estas se liberan cuando ya no se requieren. Así es posible crear estructurasdinámicas que se expandan o contraigan, según se les agregue o elimine elementos. El dinamismo de estas estructuras soluciona el problema de decidir cuál es la cantidad óptima de memoria que se debe reservar para un problema específico. Sin embargo, es importante destacar que las estructuras dinámicas no pueden reemplazar a los arreglos en todas sus aplicaciones. Existen numerosos casos que podríanfácilmente ser solucionados aplicando arreglos, mientras que si se utilizaran estructuras dinámicas, como las listas, la solución de estos problemas se complicaría.
Las listas ligadas son colecciones de elementos llamados nodos; el orden entre estos se establece por medio de un tipo de datos denominado punteros, apuntadores, direcciones o referencias a otros nodos. Por tanto, siempre es importantedistinguir entre un dato de tipo apuntador y el dato contenido en la celda al cual este apunta. Se usara la notación P <- D para indicar que P es un apuntador al nodo D, Crear(P) para señalar el proceso de asignación de memoria al nodo P, y Quitar(P) para indicar el proceso inverso; es decir, cuando se libera una position de memoria apuntada por P.

Las operaciones más importantes que se realizanen las estructuras de datos son las de búsqueda, inserción y eliminación. Se utilizan también para comparar la eficiencia de las estructuras de datos y de esta forma observar cual es la estructura que mejor se adapta al tipo de problema que se quiera resolver. La búsqueda, por ejemplo, es una operación que no se puede realizar en forma eficiente en las listas. Por otra parte, las operaciones deinserción y eliminación se efectúan de manera eficiente en este tipo de estructuras de datos.
Listas Simples |

Una lista simplemente ligada constituye una colección de elementos llamados nodos. El orden entre estos se establece por medio de punteros; es decir, direcciones o referencias a otros nodos. Un tipo especial de lista simplemente ligada es la lista vacía. La figura F331 - 1 presenta laestructura de un nodo de una lista simplemente ligada. En general, un nodo consta de dos partes:
1. Un campo INFORMACION que será del tipo de los datos que se quiera almacenar en la lista.
2. Un campo LIGA, de tipo puntero, que se utiliza para establecer la liga o el enlace con otro nodo de la lista. Si el nodo fuera el último de la lista, este campo como valor NULO —vacio—. Al emplearse elcampo liga para relacionar dos, no será necesario almacenar físicamente a los nodos en espacios contiguos.

En la figura F331-2 se presenta un ejemplo de una lista simplemente ligada que almacena apellidos. El primer nodo de la lista es apuntado por una variable P, de tipo apuntador  —P almacena la dirección del primer nodo—. El campo liga del último nodo de la tiene un valor NULO, que indica quedicho nodo no apunta a ningún otro. El apuntador al inicio de la lista es importante porque permite posicionarnos en el primer nodo de la misma y tener acceso al resto de los elementos. Si, por alguna razón, este apuntador se extraviara, entonces perderemos toda la información almacenada en la lista. Por otra parte, si la lista simplemente ligada estuviera vacía, entonces el apuntador al tendrá...