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 0aristas que salen, entonces es el final de la lista. Si el nodo tiene 0 aristas que entran, entonces es el inicio 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 dela lista listaLigada y hacia NULL |
En C/C++ el identificador de la lista contiene la dirección del primer elemento de la lista, así como sucede con los arreglos. El valor NULO es útil para saber cuándo termina la lista, es una constante estándar y no tiene valor.
El contenido de los nodos, como ya hemos visto, son los elementos de un conjunto. Si ese conjunto tiene elementos estructurados,también es válido usarlos.
Normalmente cada nodo de la lista está estructurado con dos partes:
1. La parte de información.
2. La parte de dirección al siguiente nodo de la lista.
El campo de información contiene el elemento real de la lista. El campo de dirección al siguiente contiene un apuntador al elemento con el cuál está relacionado, es decir, al elemento siguiente de la lista. Lalista completa se accesa mediante el identificador de lalista. El campo de la dirección del último nodo apunta a una direccion nula.
La lista que no tiene elementos (solamente tiene un identificador que apunta a nulo) se llama lista nula o lista vacía. Una lista se inicializa a una lista vacía haciendo lista=null, recordemos que lista es un apuntador a una dirección de memoria que puede albergaruna variable del tipo que se hayan definido los nodos; null es una dirección de cualquier tipo, así que el compilador asigna la dirección null a lista.
Enseguida vamos a dar una lista de términos usados para manejar los elementos de una lista simplemente encadenada, aunque no son los que usa C/C++ , pero sí son bastante claros para hacer algoritmos. Si p es un apuntador a la dirección de unavariable del tipo declarado para los nodos de una lista:
node(p):
hace referencia al noso al que se apunta mediante p.
info(p):
hace referencia a la información del nodo al que apunta p.
next(p):
hace referencia a la parte dirección siguiente y, por tanto, es un apuntador.
Así que la expresión info(next(p)) significa que se hace referencia a la sección de información del nodo siguienteal que apunta p.

Insertar y eliminar nodos de una lista
En el uso de las listas ligadas se ven involucradas varias operaciones, entre ellas la de insertar un nuevo nodo a la lista y la operación de eliminar un nodo de la lista. En ambos casos debemos recordar que se trata de manejo de la memoria, así que insertar un nodo en la lista significa obtener un espacio de memoria disponible yrelacionarlo con los elementos de la lista; así mismo, eliminar un nodo de la lista significa liberar la memoria que ocupa ese nodo sin perder la relación con el resto de los nodos de la lista.
Insertar un elemento al inicio de la lista. La operación p=getnode(); obtiene un nodo vacío y establece el contenido de una variable nombrada p en la dirección de este nodo, como se muestra en la figura 22.a.Este nodo aún no pertenece a alguna lista, simplemente se ha logrado dedicar un especio de memoria que es apuntado por p, figura 22.b.
|
Figura 22: a) Creación de un nuevo nodo. b) El nuevo nodo debe de ir insertado al frente, atrás o en medio de la lista. |
Una vez que se ha creado un nuevo espacio para el nuevo nodo, se debe de establecer la parte de información de ese nodo con la...