En este post vamos a implementar una estructura de datos en C de tipo lista ligada.

Se trata de una cola, que a su vez es una lista en donde iremos colocando los elementos al final de la misma, contrario a una pila en donde cada elemento va a la parte superior.

Hay varias operaciones para una cola en C, pero por ahora te mostraré las 2 básicas: la de encolar un elemento y la de recorrer la cola.

Con esos dos métodos ya puedes calcular el tamaño de la lista, comprobar si un elemento existe en la cola y muchas cosas más.

Recuerda que la cola en C puede ser de cualquier tipo y guardar cualquier cantidad de datos de cualquier tipo. Al final nosotros le asignamos memoria dinámicamente con malloc.

El nodo de la lista

Veamos el struct que será el nodo. Este nodo guarda el dato que irá en la cola, y además un apuntador al siguiente elemento.

Recuerda que este nodo o elemento de la lista puede guardar más datos, incluso otros nodos, apuntadores y varias cosas.

En mi caso para hacer las cosas simples solo he colocado un elemento de tipo cadena:

struct NodoDeLista
{
	char nombre[MAXIMA_LONGITUD_CADENA];
	// Aquí podrían ir más datos...
	struct NodoDeLista *siguiente;
};

Lo importante aquí es que el elemento de la cola se llama NodoDeLista, y que tiene un apuntador a otro nodo de su mismo tipo pero además tiene un elemento de tipo string llamado nombre.

Agregar elemento a la cola en C

Veamos una de las operaciones más interesantes, y es la de agregar un elemento a esta lista en C.

Recuerda que tenemos que agregarlo al final de todos los elementos, así que usamos las recursividad o recursión. Por cierto, en la función recibimos un apuntador a un struct, y no solo un struct.

void agregarNodoALista(struct NodoDeLista **nodo, char *nombre)
{
	struct NodoDeLista *nuevoNodo = malloc(sizeof(struct NodoDeLista));
	strcpy(nuevoNodo->nombre, nombre);
	nuevoNodo->siguiente = NULL;
	if ((*nodo) == NULL)
	{
		*nodo = nuevoNodo;
	}
	else
	{
		agregarNodoALista(&(*nodo)->siguiente, nombre);
	}
}

Esta es una de las partes más importantes, así que lee con atención. En la línea 3 estamos alojando memoria para nuestro nodo, estamos solicitando RAM al sistema operativo, ahí es en donde la magia sucede.

Nota: si por alguna razón no hubiera memoria, malloc devolvería NULL, pero no estoy manejando ese caso.

Luego en la línea 4 asignamos al nodo el valor del nombre que vamos a agregar. Aquí es necesario el uso de strcpy para asignar la cadena ya que en C las cadenas son algo difíciles de tratar.

Si fuera un tipo de dato como un entero o algo simple, podríamos hacer por ejemplo: nuevoNodo->edad = 25;

Hasta este punto solo hemos declarado el nodo, y no lo hemos ligado o relacionado con otro.

Si la cola está vacía

En la línea 6 comprobamos si el nodo actual está vacío (esto sería en caso de que sea el primer elemento) y en ese caso asignamos el nuevo nodo al inicio de la lista.

En las siguientes llamadas nos volverán a pasar ese apuntador pero ya tendrá un elemento, y ahí aplicaremos recursividad.

Si la cola tiene elementos

Por otro lado, si el nodo que nos pasan ya está definido entonces invocamos a la función (recursión) dentro de sí misma pasándole los mismos argumentos pero en lugar del nodo original le pasamos el siguiente nodo.

Esta recursividad se va a repetir hasta que lleguemos la final de la cola, en donde el nodo será NULL.

Recorrer cola

Ya vimos la operación de agregar elementos a la lista en C. Ahora veamos cómo recorrerla, y podemos hacerlo usando recursividad o un ciclo while.

Yo he decidido usar un ciclo por simplicidad, ya que la recursión no es obligatoria. Simplemente establecemos un apuntador al inicio de la lista, y mientras el mismo no sea nulo, lo asignamos a su siguiente.

void imprimirLista(struct NodoDeLista *nodo)
{
	while (nodo != NULL)
	{
		printf("Encontramos un nombre en la lista: '%s'\n", nodo->nombre);
		nodo = nodo->siguiente;
	}
}

Aquí es en donde podemos contar los elementos o saber si existe cierto elemento, ya que en cada paso podemos acceder a todas las propiedades del elemento actual de la cola.

Poniendo todo junto

Ya te mostré el nodo de la cola y las funciones para agregar o listar. Ahora veamos cómo declarar el primer elemento e invocar a las funciones. El código completo queda así:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXIMA_LONGITUD_CADENA 1000

struct NodoDeLista
{
	char nombre[MAXIMA_LONGITUD_CADENA];
	// Aquí podrían ir más datos...
	struct NodoDeLista *siguiente;
};

void agregarNodoALista(struct NodoDeLista **nodo, char *nombre)
{
	struct NodoDeLista *nuevoNodo = malloc(sizeof(struct NodoDeLista));
	strcpy(nuevoNodo->nombre, nombre);
	nuevoNodo->siguiente = NULL;
	if ((*nodo) == NULL)
	{
		*nodo = nuevoNodo;
	}
	else
	{
		agregarNodoALista(&(*nodo)->siguiente, nombre);
	}
}

void imprimirLista(struct NodoDeLista *nodo)
{
	while (nodo != NULL)
	{
		printf("Encontramos un nombre en la lista: '%s'\n", nodo->nombre);
		nodo = nodo->siguiente;
	}
}

int main()
{
	// https://parzibyte.me/blog
	struct NodoDeLista *apuntadorLista = NULL;
	agregarNodoALista(&apuntadorLista, "Luis");
	agregarNodoALista(&apuntadorLista, "Parzibyte");
	agregarNodoALista(&apuntadorLista, "Link");
	agregarNodoALista(&apuntadorLista, "Shovel Knight");
	imprimirLista(apuntadorLista);
}

Solo fíjate en que la función de agregarNodoALista recibe el apuntador al struct, y la función que imprime la lista solo recibe el struct inicial.

Eso de los apuntadores es necesario para poder modificar la lista desde otra función; es algo así como pasar la lista por referencia.

Para terminar te dejo con más programas en C.