qqqqqq

Listas enlazadas simples (I)

[Anterior] [Siguiente] [Contenido]
Contenido

Introducción
Cómo funciona una lista
Ejemplo de una lista simple
Añadir nuevos elementos
Mostrar la lista completa
Introducción

En el capítulo de 'Asignación dinámica de memoria' vimos que para ahorrar memoria podíamos reservarla dinámicamente (sobre la marcha). En mayor parte de los ejemplos que hemos vistohasta ahora reservábamos la memoria que íbamos a usar al comenzar el programa (al definir las variables).

El problema surge a la hora de hacer un programa al estilo de una agenda. No sabemos a priori cuántos nombres vamos a meter en la agenda, así que si usamos un array para este programa podemos quedarnos cortos o pasarnos. Si por ejemplo creamos una agenda con un array de mil elementos (quepueda contener mil números) y usamos sólo 100 estamos desperdiciando una cantidad de memoria importante. Si por el contrario decidimos crear una agenda con sólo 100 elementos para ahorrar memoria y necesitamos 200 nos vamos a quedar cortos. La mejor solución para este tipo de programas son las listas enlazadas.

En una lista enlazada la memoria se va tomando según se necesita. Cuando queremosañadir un nuevo elemento reservamos memoria para él y lo añadimos a la lista. Cuando queremos eliminar el elemento simplemente lo sacamos de la lista y liberamos la memoria usada.

Las listas enlazadas pueden ser simples, dobles o circulares. En este capítulo y el siguiente vamos a ver sólo las listas simples.

[Arriba]

Cómo funciona una lista

Para crear una lista necesitamos recordarnuestros conocimientos sobre estructuras y asignación dinámica de memoria. Vamos a desarrollar este tema creando una sencilla agenda que contiene el nombre y el número de teléfono.

Una lista enlazada simple necesita una estructura con varios campos, los campos que contienen los datos necesarios (nombre y teléfono) y otro campo que contiene un puntero a la propia estructura. Este puntero se usa parasaber dónde está el siguiente elemento de la lista, para saber la posición en memoria del siguiente elemento.

struct _agenda {
char nombre[20];
char telefono[12];
struct _agenda *siguiente;
};
Comprobado con DJGPP
Podríamos representar la estructura algo así:

representación de un elemento genérico de la lista
Ahora supongamos que añadimos un elemento ala lista, por ejemplo mis datos: nombre="Gorka Urrutia", telefono="99 429 31 23" (el teléfono es totalmente falso :-). Lo primero que debemos hacer es reservar (con la función malloc que ya hemos visto) un espacio en memoria para almacenar el elemento. Supongamos que se almacena en la posición 3000 (por decir un número cualquiera). El puntero siguiente debe apuntar a NULL, ya que no hay máselementos en la lista. El elemento quedaría así:

representación de un elemento de la lista
Ahora añadimos un nuevo elemento: nombre="Alberto López" telefono="99 999 99 99". Hay que reservar (con malloc) memoria para este nuevo elemento. Vamos a imaginar que este elemento se guarda en la posición de la memoria número 3420. La lista quedaría así:

Lista con dos elementos
Lo primero que debemoshacer es reservar la memoria para el elemento, luego se le rellenan los datos, se pone el puntero siguiente apuntando a NULL (porque será el último), y decir al elemento anterior que apunte al elemento que hemos añadido.

Si quisiéramos mostrar en pantalla la lista comenzaríamos por el primer elemento, lo imprimiríamos y con el puntero siguiente saltaríamos al segundo elemento, y así hasta que elpuntero siguiente apunte a NULL.

Siempre debemos tener un puntero del tipo _agenda para recordar la posición en memoria del primer elemento de la lista. Si perdemos este puntero perderemos la lista completa, así que mucho cuidado. Este puntero se definiría así:

struct _agenda primero;

Añadiendo otro elemento más:

Lista con tres elementos
[Arriba]

Ejemplo de una lista simple...