C++ Lista

Listas
Hay dos desventajas serias con respecto a las estructuras estáticas de pilas y colas usando arreglos. Estas desventajas son que tienen un espacio limitado de memoria y la otra desventaja es que es posible no ocupar toda la memoria disponible, haciendo que se desperdicie espacio.
Una solución es usar listas. Las listas son estructuras de datos que son dinámicas, esto significa queadquieren espacio y liberan espacio a medida que se necesita. sin embargo, hay una advertencia. Como regla general siempre hay que tener cuidado al manejar direcciones de espacios de memoria, porque es posible que accedamos a una localidad de memoria de la cual no deseábamos cambiar su contenido.
Antes de estudiar las listas, daremos una breve introducción a los grafos, pues las listas son un casoespecial de los grafos.

Grafos
Los grafos son una manera visual de representar las relaciones.
Definición 7   Si y son dos conjuntos, decimos que está relacionado con si es verdadera una sentencia que considere a ambos elementos. Esta sentencia puede ser cualquier predicado, por ejemplo: ``es padre de'', ``debe dinero a'', ``toma el curso de'' etc.; si el predicado es verdadero para ese parde elementos, lo escribimos como , y si el predicado es falso, lo escribimos como .
Así los ejemplos citados, si se puede leer:
* Si es el conjunto de alumnos, es el conjunto de materias y es ``toma el curso'', entonces se lee `` . En la figura 17 se puede apreciar esto en forma de diagramas de Venn.
* Si es el conjunto de personas y es también el conjunto de personas, y es ``debedinero a''; significa que ``marisol debe dinero a rafaelle'' y de ningún modo es al contrario, es decir ``rafaelle no debe dinero a marisol''.
|
Figura 17: Relación ``toma el curso de'' para los conjuntos de personas y de materias. |
Los elementos de la figura 17 definen un nuevo conjunto de elementos, el conjunto de pares de elementos que estan relacionados. Así la relación ``toma el curso de''es el siguiente:

Gráficamente podemos ilustrar el conjunto de ``toma el curso de'' con un grafo como el que se muestra en la figura 18.
|
Figura 18: Grafo que ilustra la relación ``toma el curso de''. |
De manera que podemos definir un grafo como una representación gráfica de una relación.
Definición 8   Para definir formalmente un grafo debemos establecer la siguiente tupla:Donde es un conjunto de aristas y un conjunto no vacío de nodos. En el caso de , el conjunto es el conjunto de nodos y el conjunto de flechas es el conjunto de aristas.
Notemos que el conjunto de aristas puede ser un conjunto vacío, pero de ningún modo hay grafo sin nodos, es decir el conjunto debe ser diferente que el conjunto vacío.
Supongamos ahora y la siguiente relación en :

Esta relaciónluce como aparece en la figura 20.
|
Figura: Relación de A en A |
y en forma de grafo es:
|
Figura: Grafo de la relación |
A esta clase de grafos, en las que cada nodo tiene a lo más una arista dirigida que sale y a lo más una arista dirigida que entra, se le llama lista.

Listas simplemente encadenadas
Como vimos en la sección anterior, una lista es una relación de elementos,tales que cada elemento está relacionado con únicamente un elemento del conjunto, diferente a sí mismo.
Como cada elemento puede tener a lo más una arista dirigida que sale y una arista dirigida que entra, bien puede tener 0 aristas que salen, o cero aristas que entran. Si el nodo tiene 0 aristas que salen, entonces es el final de la lista. Si el nodo tiene 0 aristas que entran, entonces es elinicio de la lista.
Por razones prácticas, se dibujan una flecha que sale de un identificador de la lista y entra al inicio de la lista y otra flecha que sale del final de la lista y apunta a un símbolo que se llama NULO.
|
Figura: Grafo de la relación con apuntadores del nombre de la lista listaLigada y hacia NULL |
En C/C++ el identificador de la lista contiene la dirección del primer...