Listas dinámicas

La manera más práctica de trabajar con una lista de objetos del mismo tipo es un Vector (o Array), cuando se instancia un vector se está reservando en memoria una cantidad fija de bytes para almacenar la información, así si tenemos:

int myList[5]; //reserva espacio para 5 variables de tipo int

myList[0] = 1; //almacena el valor 1 en la primera posición del vector

Ahora utilizaré un ejemplo de un problema tipo de examen, habla sobre el registro de reclamaciones de un comercio, cada reclamación debe contener:

• El nombre de la persona que realiza la reclamación
• La fecha de la reclamación
• La descripción de la reclamación
• El estado de la reclamación: 0 si está abierta, 1 si está resuelta.

Para representar una reclamación podemos utilizar una estructura de este tipo:

typedef struct reclamacion

{

String nombrePersona;

Date fechaReclamacion;

String descripcion;

int estado;

}Reclamacion;

Ahora creamos un Vector para almacenar la lista de reclamaciones:

Reclamacion Lista[100]; //vector de capacidad para 100 reclamaciones

Pero, y ¿Qué pasa si hay más de 100 reclamaciones?

Cuando no sabemos la dimensión que puede tomar una lista lo mejor es reservar memoria de forma dinámica, para eso podemos utilizar los punteros.

Así, sólo creamos una variable de tipo puntero que apunte a la estructura, y modificamos la estructura para que apunte al siguiente elemento de la lista, así;

typedef struct reclamacion

{

String nombrePersona;

Date fechaReclamacion;

String descripcion;

int estado;

struct reclamacion * siguiente; //este puntero apunta a la siguiente reclamación

}Reclamacion;

Reclamacion * listaReclamaciones;

listaReclamaciones = NULL; //inicializamos el puntero a NULL hasta que empiecen a llegar las reclamaciones

//creamos la primera reclamación

Reclamacion * rec1 = new Reclamacion;

rec1.nombrePersona = “Juan”;

rec1.fechaReclamacion = new Date(); //representa que toma la fecha actual (esto varía según el lenguaje de programación)

rec1.descripcion = “ejemplo de reclamacion1”;

rec1.estado = 0; //lo inicializa a 0 porque cuando se crea está abierta

rec1->siguiente = NULL; //inicializa a NULL porque es un puntero

Ahora para agregar la primera reclamación a la lista hacemos que la variable listaReclamaciones ya no apunte a NULL sino que apunte al elemento rec1:

listaReclamaciones = rec1;

Para el caso de una segunda reclamación es distinto y dependerá si se quiere agregar al principio de la lista o al final de la lista, vamos a agregarlo al final, así listaReclamaciones apuntará a rec1 y rec1->siguiente apuntará a rec2:

//creamos la segunda reclamación

Reclamacion * rec2 = new Reclamacion;

rec2.nombrePersona = “Pedro”;

rec2.fechaReclamacion = new Date(); 

rec2.descripcion = “ejemplo de reclamacion2”;

rec2.estado = 0; 

rec2->siguiente = NULL; 

Si hacemos:

listaReclamaciones->siguiente = rec2; //es lo mismo que rec1->siguiente = rec2

Tenemos el problema resuelto, rec1->siguiente ya no apunta a NULL sino que apunta a rec2 y rec2 es la última de la lista.

¿Y que pasa si no sabemos la cantidad de elementos que tiene la lista y queremos agregar un elemento al final?

La solución es tomar un puntero auxiliar y desplazamos hasta el último elemento de la lista y hacer que este último elemento apunte al elemento nuevo que queremos agregar a la lista:

//puntero auxiliar que se desplaza hasta el último elemento

Reclamacion * pAuxiliar = listaReclamaciones; //se inicializa apuntando al primero de la lista

//mientras el siguiente del auxiliar es distinto a nulo, avanza el puntero al siguiente elemento, hasta llegar al último

while(pAuxiliar->siguiente != NULL) pAuxiliar = pAuxiliar->siguiente;

//ahora agregamos el nuevo elemento al final de la lista

pAuxiliar-> siguiente = nuevaRec; //nuevaRec es el nuevo elemento de tipo reclamacion*

Existen muchas variantes:

• agregar el elemento al inicio de la lista
• agregar el elemento en medio de la lista (por ejemplo para una lista ordenada)