Estructuras dinámicas lineales

En este blog se explicara conceptos de variables dinámicas y punteros, con el motivo de tener un claro conocimiento sobre las estructuras dinámicas lineales.

Estructuras dinámicas lineales

Se dice que una estructura de datos es dinámica en el momento que se construye se utilizan variables dinámicas, variables cuya creación y eliminación se lleva acabo en tiempo de ejecución. La estructura dinámica mas sencilla son las listas simplemente enlazada, las cuales consisten en una simple secuencia de variables enlazadas mediante punteros.

Una lista es una secuencia de elementos del mismo tipo, los elementos de dichas listas se les conoce como nodo, los cuales entre ellos existen una relación que permite pasar de una nodo a otro solo si este existe, la lista vacía es un tipo especial de lista, como su nombre lo indica es una lista que no contiene ningún dato.

Un nodo contiene dos zonas de datos bien definidos, en una se almacena los datos, mientras en la otra un puntero que indica la dirección del siguiente de la lista si existiera uno, si no existe este indicaría NULL lo cual significa que existe ningún elemento siguiente.

Para poder recorrer una lista es necesario un puntero externo que apunte al comienzo de la misma lista, por tener dicho puntero el programa que va a utilizar la lista podrá hacer la siguientes funciones:

1. Recorrer la lista
2. Buscar un elemento en la lista
3. Insertar elementos en la lista
4. Eliminar elementos en la lista
5. Vaciarla 

Fuente:

http://di002.edv.uniovi.es/~dani/asignaturas/apuntes-leccion10

Un ejemplo de código de como podemos buscar en una lista dinámica en forma lineal:

nodo* buscar (int buscado) {

nodo *actual = primero;

while (actual != NULL)

if (actual->retornaDato () == buscado)

break;

else actual = actual->retornaSiguiente ();

return actual;

}

En el ejemplo anterior la función de buscar es de tipo nodo ya que como una lista contiene nodos el nos retornara el nodo a buscar si este existiera, comenzamos  inicializando una variable de tipo nodo, esta para así poder ingresarle el primer nodo de la lista, luego creamos un ciclo while el cual nos permitirá recorrer la lista de nodo en nodo, a esto se le llama búsqueda lineal, le agregamos una condición de parada para verificar cuando termina la lista, una listas simplemente enlazada podemos saber cuando termina en el momento que el un nodo tenga su puntero en NULL, luego hacemos una comparación del dato que contiene el nodo con el dato a buscar, si el dato no es el mismo, movemos el puntero al siguiente nodo y así sucesivamente hasta encontrar el dato o que la lista se termine.

Un ejemplo de código de como podemos insertar en una lista dinámica:

void insertar (int dato) {

nodo *nuevoNodo = new nodo (dato);

if (cantidad == 0)

primero = nuevoNodo;

else {

nodo *actual = primero;

while (actual->retornaSiguiente () != NULL)

actual = actual->retornaSiguiente ();

actual->modificarSiguiente (nuevoNodo);

}

cantidad++;

}

En el ejemplo anterior podemos ver que la función es llamada insertar. Esta función es la encargada de ir insertando los elementos a la lista, primero creamos una variable de tipo nodo la cual sera la que contenga cada nuevo nodo que se inserte en la lista, luego verificamos que la lista este vacía o no tenga ninguna elemento para esto utilizamos una variable que se incrementa cada vez que se inserta un nodo a la lista,

Si la lista esta vacía se inserta el nodo y se le integra el valor a la variable primero esto nos indicara cual es el primer nodo de la lista. 

Si la lista no se encuentra vacía creamos una variable de tipo nodo el cual nos ira indicando en que nodo nos encontramos así  recorremos la lista hasta el ultimo nodo, para eso utilizaremos el ciclo while el cual buscara el nodo que este apuntando a NULL eso indicara que es el ultimo nodo, al encontrarlo a la variable actual le asignaremos la dirección del ultimo nodo y luego modificaremos el puntero de ese nodo para que así apunte al nuevo nodo insertado.

Un ejemplo de código de como podemos Eliminar en una lista dinámica:

nodo* borrar (int dato) {
nodo *anterior = NULL;
nodo *borrado = primero;

while (borrado != NULL && borrado->retornaDato () != dato) {
anterior = borrado;
borrado = borrado->retornaSiguiente ();
}

if (borrado != NULL) {
if (anterior != NULL)
anterior->modificarSiguiente (borrado->retornaSiguiente ());
else primero = borrado->retornaSiguiente ();
borrado->modificarSiguiente (NULL);
}

cantidad--;
return borrado;

}

En el ejemplo anterior nos muestra una funcion simple para eliminar un nodo de una lista, para iniciar se inicializan dos variables una nos ayudara a saber el nodo anterior del nodo en donde nos encontremos, la otra para que contenga el nodo en donde estemos comparando o el que vamos a borrar cuando lo encontremos. 

Creamos un ciclo para recorrer la lista y asi poder buscar el elemento a eliminar, se verifica si la variable borrar se encuentra NULL y si el dato de esa variable es igual al dato a borrar si es a si el dato de la variable borrado se la agregamos a anterior y movemos el puntero que apunta al elemento a borrar al siguiente nodo y asi borramos el nodo.

Si no se cumple la condición del while  se pasa al if y se verifica si la variable borrado es NULL, si es asi verificamos que si la variable anterior se encuentra NULL, esto con el fin de pasar al siguiente nodo ya que seria el primer nodo y no es el dato a buscar.

Le asignamos el puntero el primer nodo a la variable anterior y el puntero del nodo que esta en borrado lo cambiamos por el siguiente y así podemos recorrer la lista para buscar el elemento a eliminar.

Podemos recalcar que es una estructura algo simple de utilizar, solo tenemos que tener cuidado con los punteros de los nodos y así no dañar la lista sin querer.