Las estructuras de datos son la base de cualquier programa no trivial. En C no hay biblioteca estándar con listas, árboles o diccionarios listos para usar a diferencia de C++ con STL o Python con sus tipos built-in, así que hay que implementarlos. Eso es precisamente lo que hace a C un lenguaje educativo y potente: te obliga a entender la mecánica interna. Este artículo implementa las tres estructuras más usadas desde cero.
Lista enlazada simple
Una lista enlazada almacena elementos en nodos dispersos por el heap, conectados mediante punteros. A diferencia de los arrays, la inserción y eliminación en cualquier posición son O(1) si se tiene el puntero al nodo previo, pero el acceso por índice es O(n).
#include <stdlib.h>
#include <stdio.h>
typedef struct Nodo {
int dato;
struct Nodo* siguiente;
} Nodo;
/* Insertar al principio O(1) */
Nodo* insertar_inicio(Nodo* cabeza, int valor) {
Nodo* nuevo = malloc(sizeof(Nodo));
if (!nuevo) return cabeza;
nuevo->dato = valor;
nuevo->siguiente = cabeza;
return nuevo;
}
/* Imprimir la lista */
void imprimir_lista(const Nodo* n) {
while (n) {
printf("%d -> ", n->dato);
n = n->siguiente;
}
printf("NULLn");
}
/* Liberar toda la lista */
void liberar_lista(Nodo* n) {
while (n) {
Nodo* tmp = n->siguiente;
free(n);
n = tmp;
}
}
El patrón de liberar (tmp = n->siguiente; free(n); n = tmp;) es fundamental: si se libera n antes de guardar el siguiente puntero, se pierde la referencia al resto de la lista.
Eliminar un nodo por valor
Nodo* eliminar(Nodo* cabeza, int valor) {
if (!cabeza) return NULL;
if (cabeza->dato == valor) {
Nodo* siguiente = cabeza->siguiente;
free(cabeza);
return siguiente;
}
Nodo* actual = cabeza;
while (actual->siguiente && actual->siguiente->dato != valor) {
actual = actual->siguiente;
}
if (actual->siguiente) {
Nodo* a_borrar = actual->siguiente;
actual->siguiente = a_borrar->siguiente;
free(a_borrar);
}
return cabeza;
}
Árbol binario de búsqueda
Un árbol binario de búsqueda (BST) mantiene los elementos ordenados: el subárbol izquierdo contiene valores menores y el derecho valores mayores. Búsqueda, inserción y eliminación son O(log n) en un árbol equilibrado, O(n) en el peor caso (árbol degenerado).
typedef struct NodoArbol {
int valor;
struct NodoArbol* izquierda;
struct NodoArbol* derecha;
} NodoArbol;
NodoArbol* insertar_bst(NodoArbol* raiz, int valor) {
if (!raiz) {
NodoArbol* nuevo = malloc(sizeof(NodoArbol));
if (!nuevo) return NULL;
nuevo->valor = valor;
nuevo->izquierda = nuevo->derecha = NULL;
return nuevo;
}
if (valor < raiz->valor)
raiz->izquierda = insertar_bst(raiz->izquierda, valor);
else if (valor > raiz->valor)
raiz->derecha = insertar_bst(raiz->derecha, valor);
/* Si valor == raiz->valor: no duplicados */
return raiz;
}
/* Recorrido in-order: imprime en orden ascendente */
void inorden(const NodoArbol* n) {
if (!n) return;
inorden(n->izquierda);
printf("%d ", n->valor);
inorden(n->derecha);
}
/* Búsqueda */
int buscar_bst(const NodoArbol* raiz, int valor) {
if (!raiz) return 0;
if (valor == raiz->valor) return 1;
if (valor < raiz->valor) return buscar_bst(raiz->izquierda, valor);
return buscar_bst(raiz->derecha, valor);
}
void liberar_arbol(NodoArbol* n) {
if (!n) return;
liberar_arbol(n->izquierda);
liberar_arbol(n->derecha);
free(n);
}
Tabla hash con encadenamiento
Una tabla hash mapea claves a valores en tiempo O(1) amortizado. La función hash convierte la clave en un índice del array. Las colisiones (dos claves con el mismo índice) se resuelven con encadenamiento: cada posición del array es una lista enlazada.
#include <string.h>
#define TABLA_SIZE 64
typedef struct EntradaHash {
char* clave;
int valor;
struct EntradaHash* siguiente;
} EntradaHash;
typedef struct {
EntradaHash* buckets[TABLA_SIZE];
} TablaHash;
/* Función hash djb2 de Dan Bernstein */
unsigned int hash(const char* clave) {
unsigned int h = 5381;
int c;
while ((c = (unsigned char)*clave++))
h = ((h << 5) + h) + c;
return h % TABLA_SIZE;
}
void hash_insertar(TablaHash* t, const char* clave, int valor) {
unsigned int idx = hash(clave);
EntradaHash* e = malloc(sizeof(EntradaHash));
if (!e) return;
e->clave = strdup(clave);
e->valor = valor;
e->siguiente = t->buckets[idx];
t->buckets[idx] = e;
}
int hash_buscar(const TablaHash* t, const char* clave, int* resultado) {
unsigned int idx = hash(clave);
EntradaHash* e = t->buckets[idx];
while (e) {
if (strcmp(e->clave, clave) == 0) {
*resultado = e->valor;
return 1;
}
e = e->siguiente;
}
return 0;
}
La función djb2 tiene buena distribución para cadenas de texto. Para un factor de carga bajo (menos del 75% de buckets ocupados), las colisiones son mínimas.
Uso conjunto
int main(void) {
/* Lista enlazada */
Nodo* lista = NULL;
lista = insertar_inicio(lista, 3);
lista = insertar_inicio(lista, 1);
lista = insertar_inicio(lista, 2);
imprimir_lista(lista); /* 2 -> 1 -> 3 -> NULL */
liberar_lista(lista);
/* BST */
NodoArbol* raiz = NULL;
raiz = insertar_bst(raiz, 5);
raiz = insertar_bst(raiz, 3);
raiz = insertar_bst(raiz, 7);
inorden(raiz); /* 3 5 7 */
liberar_arbol(raiz);
/* Tabla hash */
TablaHash tabla = {0};
hash_insertar(&tabla, "usuario", 42);
int v;
if (hash_buscar(&tabla, "usuario", &v))
printf("Encontrado: %dn", v);
return 0;
}
Para profundizar en el manejo de memoria de estas estructuras, el artículo sobre gestión de memoria en C con Valgrind cubre cómo detectar fugas al liberar estas estructuras. Si te interesan alternativas con estructuras de datos genéricas integradas, C++26 ofrece la STL con contenedores listos para usar.
Imagen: Pexels / Thomas P