Compartir entrada

martes, 11 de junio de 2013

Curso básico de C 9/10: Listas dinámicas (I)

En la octava entrega del curso básico de C pudimos tomar contando con el concepto de puntero, pudimos ir jugando un poco con sus operaciones y comprobando las diferencias entre tratar valores y punteros. Ahora vamos a tratar uno de los aspectos más potentes de C, las listas dinámicas.

Curso básico de C 9/10: Listas dinámicas (I)
Foto tomada de freedigitalphotos.net

El concepto de puntero nos servirá sobretodo para poder desarrollar el concepto de lista dinámica. Realmente es tanto el juego que brinda que dependiendo de cómo organicemos las estructuras de datos podemos encontrarnos estructuras de muchos tipos:

  • Listas simples.
  • Listas doblemente enlazadas.
  • Pilas.
  • Colas.
  • Listas circulares.
  • Árboles binarios.
  • Árboles binarios de búsqueda.
  • Árboles AVL.
  • Árboles B.
  • Tablas HASH.
  • Grafos.
  • Diccionarios.

Listas con enlace simple.

Una lista con enlace simple o lista dinámica es una estructura de datos que reserva espacio de memoria a medida que el programa se ejecuta y cuyos nodos se enlazan mediante un único puntero que apunta al siguiente nodo.

Concepto de Nodo.

Para comenzar a trabajar con una estructura dinámica de datos es necesario declarar una estructura con los datos que vamos a tratar y un puntero para poder apuntar al siguiente conjunto de datos. Esto conforma un único elemento de la lista al que llamamos nodo.

Un nodo de una lista dinámica lo declararemos como una estructura de datos con el siguiente esquema:

struct nodo {
            tipo_dato1 identificador1;
            tipo_dato2 identificador2;
            ...
            struct nodo *siguiente_elemento;
}

¿Qué significa esto? Pues que un nodo con ésta estructura contendrá una serie de datos con sus correspondientes tipos y además contendrá un puntero que apuntará a la dirección de memoria donde se encuentra el siguiente nodo con la misma estructura. De ésta forma no hay límite en la cantidad de información a almacenar, cosa que si pasa con los arrays.

Además es importante tener en cuenta en la declaración que debemos declarar ciertos elementos adicionales para poder guardar información necesaria para trabajar con la lista, como por ejemplo el puntero al primer nodo, éste es muy importante debido a que si no almacenamos su valor no podremos localizar el inicio de la lista y por lo tanto la perderíamos.

La declaración de la estructura quedaría así:

typedef struct _nodo
{
int dato;
struct _nodo *siguiente;
} tipoNodo;

Un dato importante es que al declarar el primer nodo de una lista hay que inicializarlo a null para especificar que comenzamos una lista vacía.

La declaración completa de una lista de una estructura de enteros quedaría así:

struct Nodo
{
int dato1;
int dato2;
Nodo *siguiente;
};

int main (void)
{
            struct Nodo *lista=NULL;
}

Con esto tenemos declarada la estructura y el inicio de una lista, ahora vamos a ver las operaciones más frecuentes:

Comienzo de una lista.

Lo primero que debemos hacer para comenzar una lista y asignar los primeros valores es reservar un espacio de memoria, para ello utilizaremos la librería stdlib.h y su función malloc:

struct Nodo
{
int dato1;
int dato2;
Nodo *siguiente;
};

int main (void)
{
            struct Nodo *lista=NULL;
            lista = malloc( sizeof(struct Nodo) );
}

Con esto ya hemos iniciado la lista, ahora vamos a hacer que las variables enteras tengan datos y que el puntero apunte a null (ya que aún no tenemos ningún nodo que continúe).

struct Nodo
{
int dato1;
int dato2;
Nodo *siguiente;
};

int main (void)
{
            struct Nodo *lista=NULL;
            lista = malloc( sizeof(struct Nodo) );

            lista -> dato1=10;
lista -> dato2=25;
lista -> siguiente =NULL;

}

Ya tenemos el nodo relleno de datos, ahora podremos hacer cualquier operación con ellos, como si de variables se tratase. Fíjate que para acceder al dato he utilizado el operador ->, esto es debido a que lista es del tipo de dato struct Nodo, lo cual quiere decir que es un puntero, gracias al operador -> podemos acceder al campo que deseemos directamente.

Añadir un nodo a la cabeza.

Ahora vamos a ver como añadir un nuevo nodo al principio de la lista. El planteamiento no es complicado, debemos crear un nuevo nodo, rellenar sus datos y hacer que el puntero *siguiente apunte al nodo cuyos datos son dato1 = 10 y dato2=25, es decir, el nodo único que tenemos originalmente.

Existe un gran problema a la hora de trabajar con listas dinámicas de datos, el problema no es otro que perder la referencia del siguiente nodo de la lista, bien porque modifiquemos la información del puntero *siguiente o bien porque lo vaciemos. En cualquier caso es importante tener en cuenta la siguiente: Si se pierde la referencia al siguiente nodo de la lista, es imposible volver a recuperarla, por lo que perderemos todos los elementos de la lista a partir de ese nodo.

Para evitar esto usaremos un puntero auxiliar, para no perder la referencia mientras añadimos el nodo nuevo.

El programa quedará así:

struct Nodo
{
int dato1;
int dato2;
Nodo *siguiente;
};

int main (void)
{
            struct Nodo *lista=NULL, * aux;
            lista = malloc( sizeof(struct Nodo) );

            lista -> dato1=10;
lista -> dato2=25;
lista -> siguiente =NULL;

aux = lista ;

lista = malloc( sizeof(struct Nodo) );
lista -> dato1=3;
lista -> dato2=5;
lista-> siguiente = aux ;

}

¿Con esto qué hemos hecho? Primero hemos declarado nuestro nodo inicial, le hemos dado valores, después utilizamos el puntero *aux para apuntar a este nodo y así no perder la referencia. Creamos el segundo nodo y rellenamos sus datos, después hacemos que el puntero *siguiente tenga el mismo valor que el puntero *aux, con lo cual gracias a esto el puntero *siguiente nuevo contiene la misma dirección de memoria que el puntero *aux, que es la de nuestro nodo original, quedando así los dos nodos de la lista perfectamente enlazados.

¿Qué hacemos con *aux ahora que ya no nos hace falta y sigue apuntando al segundo nodo? Podemos dejarlo tal y como está, siempre nos hará falta un puntero auxiliar para trabajar con listas dinámicas, tarde o temprano cambiará de valor.

El puntero *aux es el puntero más importante que usaremos, puesto que gracias a él podremos trabajar con las listas sin perder las referencias.

Éste código podemos guardárnoslo perfectamente para posteriores usos en forma de un procedimiento o una función perteneciente a un programa o una librería propia.

Añadir un nodo al final.

El caso que nos ocupa ahora es también sencillo si entendemos correctamente la teoría de listas dinámicas.

Para añadir un nodo al final de la lista basta con encontrar el nodo cuyo puntero *siguiente apunte a NULL. Realizar esto de forma manual mediante una sucesión de -> siguiente -> siguiente es completamente innecesario e ineficiente. Para recorrer una lista lo mejor es usar un bucle while de la forma:

while (aux->siguiente != NULL)

Una vez encontremos el nodo cuyo puntero *siguiente apunta a NULL procedemos a añadir el nuevo nodo. Necesitaremos de un nuevo nodo aparte del *aux para poder conservar los datos (o rellenarlos a posteriori, esto es una buena práctica).

El código para añadir un nodo al final de una lista es el siguiente:

struct Nodo
{
int dato1;
int dato2;
Nodo *siguiente;
};

int main (void)
{
            struct Nodo *lista=NULL, * aux, *nuevo;
            lista = malloc( sizeof(struct Nodo) );

            lista -> dato1=10;
lista -> dato2=25;
lista -> siguiente =NULL;

aux = lista ;

while (aux->siguiente != NULL)
{
            aux = aux-> siguiente;
}

nuevo = malloc( sizeof(struct Nodo) );
nuevo-> dato1=2;
nuevo-> dato2=6;
nuevo-> siguiente = NULL;
aux-> siguiente = nuevo ;
}

Mediante el bucle while y usando el puntero *aux vamos avanzando en la lista, el puntero *aux va apuntando a donde apunte *siguiente hasta que *siguiente sea NULL, de ésta forma *aux está posicionado en el último nodo y está listo para apuntar al nuevo nodo, que se quedaría en el final.

Aquí se puede comprobar la importancia del uso del puntero *aux, si en vez usar el puntero *aux, usáramos *lista, con cada vuelta del bucle while estaríamos perdiendo la referencia al nodo anterior, por lo que no podríamos referenciar el inicio de la lista y la perderíamos.

Nuevamente éste código se puede guardar para su uso posterior.

Borrar el primer nodo de una lista.

Borrar el primer nodo de una lista no debería ser complicado ya que según hemos podido ver, en cuanto perdemos la referencia de un nodo, éste es irrecuperable. Con lo cual si quisiéramos borrar el primer nodo de una lista nada más fácil que hacer lo siguiente:

lista=lista -> siguiente;

Esto teóricamente hace lo que deseamos, ya que al hacer que el puntero *lista apunte al nodo siguiente en vez de al primer nodo perdemos la referencia y nos hemos librado de ese nodo. No obstante presenta un problema, el primer nodo sigue existiendo en la memoria, lo cual no debería suceder ya que está consumiendo recursos de la máquina.

Para evitar esto usaremos la función free incluida también en la librería stdlib.h:

lista=lista->siguiente;
free(lista);

Error, esto provocaría un verdadero problema, ya que hemos borrado un nodo ubicado en la lista y hemos perdido referencia al siguiente elemento y al anterior, teniendo como resultado dos listas separadas y perdidas en la memoria sin posibilidad de recuperarlas. Hagámoslo al revés:

free(lista);
lista=lista->siguiente;

Esto tampoco es correcto, intentamos avanzar en la lista mediante un puntero que ya no apunta a nada porque hemos liberado la memoria, perdiendo así el resto de la lista.

La solución, como va a ser costumbre, viene de la mano del puntero *aux, el programa sería así:

int main(void)
{
struct Nodo * lista = NULL, * aux, * nuevo;

aux = lista->sig ;
free(lista);
lista = aux;

return 0;
}

¿Qué hemos hecho con ésto? Hemos hecho que el puntero *aux apunte al siguiente nodo de la lista, liberamos la memoria del puntero *lista (que siempre será nuestro punto de partida) y hacemos que *lista apunte a *aux, gracias a esto volvemos a tener un punto de inicio de la lista y hemos liberado en memoria el que antes era el primer nodo.

Borrar el último nodo de la lista.

El último código de hoy en teoría parece también sencillo, si para borrar el primer elemento de la lista tan sólo se necesita un auxiliar para no perderlo todo, eliminar el último elemento debe ser igualmente fácil, tan sólo tendríamos que posicionarnos en el último elemento de la lista y liberar su memoria.

while (aux->siguiente != NULL)
{
            aux = aux-> siguiente;
}
free(aux);

Esto está bien a medias, porque ahora necesitamos que el penúltimo nodo (que ahora es el último) apunte a NULL, pero esto no es posible hacerlo debido a que no podemos determinar cual es el último nodo de la lista, ya que ninguna apunta a NULL, todos los nodos apuntan a un elemento.

¿Cómo solucionarlo? Pues de una forma muy sencilla, si con un auxiliar no tenemos suficiente, usemos dos.

Mediante un segundo auxiliar podemos determinar el nodo anterior al nodo que apunta *aux, de ésta forma cuando liberemos *aux podemos decir que *aux2 -> siguiente apunte a NULL, de ésta forma tenemos de nuevo la lista confeccionada correctamente.

El código es el siguiente:

struct Nodo * lista = NULL, * aux, * atras;

....
atras=NULL;
aux=lista;

while (aux->siguiente != NULL)
{
            atras=aux;
            aux = aux-> siguiente;
}

free(aux);
atras->siguiente = NULL;
....

Ahora sí que hace la función para la cual está pensada, el último nodo se ha eliminado y la lista queda perfectamente preparada para trabajar

No obstante se presenta un pequeño caso que nos puede pasar perfectamente, el caso de que la lista tenga sólo un elemento, por lo tanto no tiene sentido hacer atrás->siguiente=NULL, el único nodo que existiría es igualmente el nodo de cola, corrijamos éste detalle:

struct Nodo * lista = NULL, * aux, * atras;

....
atras=NULL;
aux=lista;

while (aux->siguiente != NULL)
{
            atras=aux;
            aux = aux-> siguiente;
}

free(aux);

if (atrás==NULL)
{
            lista=NULL;
}
else
{
atras->siguiente = NULL;
}
....

Con esto tenemos contemplado el caso de que la lista sólo contenga un elemento, el código está listo para usarse.

Para finalizar voy a poner los cuatro códigos que hemos visto hoy, pero antes os plantearé un pequeño caso y cómo afrontarlo, además de modificar todos los códigos y así tenerlos perfectamente para usarlos.

Caso de la lista vacía.

Imaginemos que deseamos trabajar con listas pero ésta está vacía, los algoritmos que hemos planteado no sirven para listas vacías debido a que no tenemos nada que recorrer o que asignar a los punteros, esto es sencillo de controlar gracias a la estructura if, controlaremos que la lista no esté vacía y así podremos trabajar según qué casos.

Códigos finales.

Los siguientes códigos son los códigos que hemos visto pero teniendo en cuenta el caso de la lista vacía. Ésta sería su versión definitiva.

Estructura utilizada:

struct Nodo
{
int dato1;
int dato2;
Nodo *siguiente;
};

Añadir nodo en el principio:

{
            struct Nodo * aux;

if (lista == NULL)
{
lista = malloc(sizeof(struct Nodo));
lista->dato1 = 1;
lista->dato2 = 2;
lista->siguiente = NULL;
}
            else
            {
aux = lista ;

lista = malloc( sizeof(struct Nodo) );
lista -> dato1=3;
lista -> dato2=4;
lista-> siguiente = aux ;
}
}

Añadir nodo al final:

{
            struct Nodo * aux, *nuevo;

if (lista == NULL) {
lista = malloc(sizeof(struct Nodo));
lista->info = valor;
lista->siguiente = NULL;
}
else
{
aux = lista ;

while (aux->siguiente != NULL)
{
aux = aux-> siguiente;
}

nuevo = malloc( sizeof(struct Nodo) );
nuevo-> dato1=2;
nuevo-> dato2=6;
nuevo-> siguiente = NULL;
aux-> siguiente = nuevo ;
}
}

Borrar nodo al principio:

{
struct Nodo * aux;

if (lista != NULL)
{
aux = lista->sig ;
free(lista);
lista = aux;
}
}

Borrar nodo al final:

{
struct Nodo * aux, * atras;

if (lista != NULL)
{
atras=NULL;
aux=lista;

while (aux->siguiente != NULL)
{
            atras=aux;
            aux = aux-> siguiente;
}

free(aux);

if (atrás==NULL)
{
            lista=NULL;
}
else
{
atras->siguiente = NULL;
}
}
}

Conclusiones.

Hemos finalizado la primera parte del noveno capítulo del curso básico de C. Durante éste capítulo hemos podido ver el concepto de estructura dinámica de datos, nodos y listas con enlace simple además de cuatro operaciones básicas que se pueden hacer con ellas.

En la segunda parte veremos nuevas operaciones con listas con enlace simple, veremos cómo buscar un nodo dentro de la lista, eliminar un nodo en una posición cualquiera, insertar un nodo ordenadamente, escribir y operar con el contenido del nodo, etc.

¿Qué otras operaciones con listas se te ocurren? ¿Cómo mejorarías los cuatro primeros códigos?

 
Google+