Las listas enlazadas son una familia de estructuras lineales descritas en la literatura desde los orígenes de la programación. Cada elemento se aloja en un nodo que conoce a su sucesor y, dependiendo de la variante, a su predecesor. A diferencia de los arreglos, no hay un bloque contiguo que reserve toda la memoria, sino que los nodos se solicitan bajo demanda.
Gracias a esta flexibilidad se vuelven una opción natural cuando el volumen de datos es incierto, cuando la aplicación requiere insertar o borrar elementos en posiciones arbitrarias o cuando se busca reutilizar nodos para ahorrar copias. En contextos modernos se siguen utilizando para colas de tareas, listas de espera y estructuras internas de lenguajes o bibliotecas.
El concepto formal está documentado en la entrada de listas enlazadas de Wikipedia, que resume las variantes históricas y sus principales aplicaciones. En este tutorial enfocamos el análisis en la implementación en C, de modo que comprendamos qué ocurre en memoria cuando manipulamos punteros.
Una lista enlazada es una colección de nodos enlazados por referencias. Cada nodo guarda el dato de interés (entero, cadena, estructura propia) y al menos un puntero que indica dónde continuar. El primer nodo se conoce como head y delimita la entrada oficial a la estructura; cuando la lista está vacía, el head apunta a NULL. El último nodo se denomina tail y su puntero también es NULL salvo en diseños circulares donde se vuelve a enlazar con el head.
Al recorrer una lista pensamos en una cadena de nodos: iniciar en head, inspeccionar su valor y seguir el enlace al siguiente nodo. Si alguno de los enlaces queda mal actualizado, se pierde parte de la estructura. Por ello las inserciones y eliminaciones siempre deben preservar la secuencia head → ... → tail.
En C podemos representar un nodo de la siguiente forma:
typedef struct Nodo {
int valor;
struct Nodo *sig; /* enlaza con el siguiente nodo */
} Nodo;Este esquema admite cualquier tipo de dato en valor; basta con sustituir el entero por otro struct o puntero. El objetivo es separar la lógica de enlace de los datos reales.
Comparar listas con arrays ayuda a decidir cuándo utilizar cada estructura. En la tabla siguiente se contrastan los aspectos más relevantes:
| Criterio | Array | Lista enlazada |
|---|---|---|
| Ubicación en memoria | Bloque contiguo; favorece la cercanía a nivel de caché | Nodos dispersos; puede aprovechar huecos libres en el heap |
| Coste de inserción intermedia | O(n) por desplazamiento de elementos | O(1) si se tiene la referencia al nodo anterior |
| Acceso por posición | O(1), basta con calcular la dirección base + desplazamiento | O(n); es necesario recorrer desde head |
| Consumo extra | No hay metadatos por elemento | Cada nodo incluye al menos un puntero adicional |
| Redimensión | Requiere realocar o copiar a un bloque más grande | Cada inserción reserva un nodo independiente |
El resultado principal es que un array es insuperable para lectura secuencial y acceso directo, pero se vuelve costoso cuando el tamaño cambia muchas veces por segundo. Las listas enlazadas sacrifican velocidad de acceso para ganar flexibilidad estructural y reducir copias.
Entre los beneficios más importantes destacan:
malloc cuando hace falta, sin restricciones fijas ni necesidad de predecir la capacidad.Estas ventajas cobran sentido en motores de videojuegos, sistemas operativos o servidores que procesan flujos de eventos infinitos, donde no se puede detener la ejecución para realocar grandes segmentos.
No hay estructura perfecta; las listas enlazadas introducen retos que deben evaluarse antes de adoptarlas:
sig o al liberar nodos genera fugas, referencias colgantes o listas corruptas difíciles de depurar.Por estas razones se suelen combinar con otras estructuras: por ejemplo, una lista enlazada que almacena arreglos pequeños para equilibrar flexibilidad y rendimiento.
Las listas enlazadas tienen presencia en componentes críticos de software:
Estos casos demuestran que, aunque existan estructuras más sofisticadas, la lista enlazada sigue siendo una herramienta indispensable cuando la mutabilidad y el control de memoria son prioritarios.