8 - Aplicaciones y casos de uso
Puentes hacia proyectos reales
Las listas enlazadas son más que un ejercicio académico: se utilizan en pilas, colas, buffers y planificadores de sistemas operativos. Este tema repasa cinco aplicaciones comunes con ejemplos concretos en C.
8.1 Pilas implementadas con listas
Una pila (stack) agrega y retira elementos por el mismo extremo. Usar una lista enlazada permite crecimiento dinámico sin definir una capacidad fija.
typedef struct Nodo {
int valor;
struct Nodo *sig;
} Nodo;
typedef struct {
Nodo *tope;
} Pila;
void pila_push(Pila *pila, int valor) {
Nodo *n = malloc(sizeof(Nodo));
if (!n) return;
n->valor = valor;
n->sig = pila->tope;
pila->tope = n;
}
bool pila_pop(Pila *pila, int *resultado) {
if (!pila->tope) return false;
Nodo *victima = pila->tope;
*resultado = victima->valor;
pila->tope = victima->sig;
free(victima);
return true;
}El puntero tope actúa como cabeza de la lista. Cada llamada a push inserta al inicio y pop reutiliza la función de eliminación del primer nodo.
8.2 Colas implementadas con listas
Las colas agregan por la cola y retiran por la cabeza. Con una lista enlazada se garantiza inserción O(1) si se mantiene referencia al último nodo.
typedef struct {
Nodo *cabeza;
Nodo *cola;
} Cola;
bool cola_enqueue(Cola *cola, int valor) {
Nodo *n = malloc(sizeof(Nodo));
if (!n) return false;
n->valor = valor;
n->sig = NULL;
if (!cola->cabeza) {
cola->cabeza = cola->cola = n;
} else {
cola->cola->sig = n;
cola->cola = n;
}
return true;
}
bool cola_dequeue(Cola *cola, int *resultado) {
if (!cola->cabeza) return false;
Nodo *victima = cola->cabeza;
*resultado = victima->valor;
cola->cabeza = victima->sig;
if (!cola->cabeza) cola->cola = NULL;
free(victima);
return true;
}8.3 Buffers circulares
Los buffers circulares se usan para procesar flujos continuos (por ejemplo, audio o mensajes). Una lista circular evita realocar memoria constantemente.
typedef struct NodoCircular {
int valor;
struct NodoCircular *sig;
} NodoCircular;
typedef struct {
NodoCircular *cola;
} BufferCircular;
bool buffer_insertar(BufferCircular *buffer, int valor) {
NodoCircular *n = malloc(sizeof(NodoCircular));
if (!n) return false;
if (!buffer->cola) {
n->valor = valor;
n->sig = n;
buffer->cola = n;
return true;
}
n->valor = valor;
n->sig = buffer->cola->sig;
buffer->cola->sig = n;
buffer->cola = n;
return true;
}Dependiendo del uso, se puede mantener un tamaño máximo y eliminar el nodo más antiguo cuando el buffer se llena.
8.4 Listas en sistemas operativos
Los kernels utilizan listas enlazadas para mantener colas de procesos, hilos, dispositivos y estructuras de memoria. Un ejemplo simplificado de cola de procesos listos:
typedef struct Proceso {
int pid;
struct Proceso *sig;
} Proceso;
typedef struct {
Proceso *cabeza;
Proceso *cola;
} ColaProcesos;
void procesos_agregar(ColaProcesos *cola, int pid) {
Proceso *p = malloc(sizeof(Proceso));
if (!p) return;
p->pid = pid;
p->sig = NULL;
if (!cola->cabeza) {
cola->cabeza = cola->cola = p;
} else {
cola->cola->sig = p;
cola->cola = p;
}
}El planificador toma el primer proceso y lo mueve entre listas (listos, bloqueados, ejecutando) según su estado.
8.5 Algoritmos como Josephus o round-robin
Problemas clásicos como Josephus o el planificador round-robin se benefician de listas circulares, ya que el puntero puede seguir girando indefinidamente.
int josephus(ListaCircular *lista, int salto) {
if (!lista->cola) return -1;
NodoCircular *actual = lista->cola->sig;
NodoCircular *anterior = lista->cola;
while (actual != anterior) {
for (int i = 1; i < salto; ++i) {
anterior = actual;
actual = actual->sig;
}
anterior->sig = actual->sig;
free(actual);
actual = anterior->sig;
}
int sobreviviente = actual->valor;
free(actual);
lista->cola = NULL;
return sobreviviente;
}Este algoritmo elimina nodos en ciclos hasta que queda un sobreviviente. Round-robin aplica la misma idea para repartir CPU, pero en vez de eliminar, mueve el proceso al final de la lista circular.
8.6 Código base reutilizable
Si deseas experimentar con varias estructuras en un mismo proyecto, puedes partir de los siguientes archivos:
/* estructuras.h */
#ifndef ESTRUCTURAS_H
#define ESTRUCTURAS_H
#include <stdbool.h>
typedef struct Nodo {
int valor;
struct Nodo *sig;
} Nodo;
typedef struct {
Nodo *tope;
} Pila;
typedef struct {
Nodo *cabeza;
Nodo *cola;
} Cola;
typedef struct NodoCircular {
int valor;
struct NodoCircular *sig;
} NodoCircular;
typedef struct {
NodoCircular *cola;
} ListaCircular;
void pila_push(Pila *pila, int valor);
bool pila_pop(Pila *pila, int *resultado);
bool cola_enqueue(Cola *cola, int valor);
bool cola_dequeue(Cola *cola, int *resultado);
bool lista_circular_insertar(ListaCircular *lista, int valor);
void lista_circular_imprimir(const ListaCircular *lista);
#endif/* estructuras.c */
#include "estructuras.h"
#include <stdio.h>
#include <stdlib.h>
void pila_push(Pila *pila, int valor) {
Nodo *n = malloc(sizeof(Nodo));
if (!n) return;
n->valor = valor;
n->sig = pila->tope;
pila->tope = n;
}
bool pila_pop(Pila *pila, int *resultado) {
if (!pila->tope) return false;
Nodo *victima = pila->tope;
*resultado = victima->valor;
pila->tope = victima->sig;
free(victima);
return true;
}
bool cola_enqueue(Cola *cola, int valor) {
Nodo *n = malloc(sizeof(Nodo));
if (!n) return false;
n->valor = valor;
n->sig = NULL;
if (!cola->cabeza) {
cola->cabeza = cola->cola = n;
} else {
cola->cola->sig = n;
cola->cola = n;
}
return true;
}
bool cola_dequeue(Cola *cola, int *resultado) {
if (!cola->cabeza) return false;
Nodo *victima = cola->cabeza;
*resultado = victima->valor;
cola->cabeza = victima->sig;
if (!cola->cabeza) cola->cola = NULL;
free(victima);
return true;
}
bool lista_circular_insertar(ListaCircular *lista, int valor) {
NodoCircular *n = malloc(sizeof(NodoCircular));
if (!n) return false;
n->valor = valor;
if (!lista->cola) {
n->sig = n;
lista->cola = n;
return true;
}
n->sig = lista->cola->sig;
lista->cola->sig = n;
lista->cola = n;
return true;
}
void lista_circular_imprimir(const ListaCircular *lista) {
if (!lista->cola) {
puts("(vacía)");
return;
}
const NodoCircular *inicio = lista->cola->sig;
const NodoCircular *reco = inicio;
do {
printf("%d -> ", reco->valor);
reco = reco->sig;
} while (reco != inicio);
puts("(inicio)");
}/* main.c */
#include "estructuras.h"
#include <stdio.h>
int main(void) {
Pila pila = {0};
Cola cola = {0};
ListaCircular buffer = {0};
pila_push(&pila, 1);
pila_push(&pila, 2);
cola_enqueue(&cola, 10);
cola_enqueue(&cola, 20);
lista_circular_insertar(&buffer, 100);
lista_circular_insertar(&buffer, 200);
printf("Pila y cola inicializadas. Buffer circular:\n");
lista_circular_imprimir(&buffer);
return 0;
}Estos archivos permiten experimentar con distintas aplicaciones en un solo proyecto, modificando las funciones según el escenario.
