Estructuras dinámicas de datos
Cuando no se sabe de antemano cuántos datos van a llegar, el arreglo estorba. La lista enlazada crece y se achica siguiendo punteros, y con ese mecanismo se construyen colas, pilas y árboles.
01Cuando el arreglo no alcanza
Un arreglo es rápido y simple, pero tiene un tamaño fijo decidido antes de correr el programa. Si llegan más datos de los previstos, se desborda; si llegan menos, se desperdicia memoria. Una estructura dinámica crece y se achica durante la ejecución, reservando un nodo por dato.
| Operación | Arreglo | Lista enlazada |
|---|---|---|
| Acceder al elemento i | O(1): cuenta directa | O(n): hay que recorrer |
| Insertar al principio | O(n): correr todo | O(1): cambiar dos punteros |
| Insertar al final | O(1) si hay lugar | O(n), u O(1) con puntero a la cola |
| Eliminar del medio | O(n): correr todo | O(1) si ya se tiene el nodo anterior |
| Memoria por dato | Sólo el dato | El dato más un puntero |
| Localidad en caché | Excelente: contiguo | Pobre: nodos dispersos |
No hay ganador: hay criterio. Si se conoce el tamaño y se accede por índice, arreglo. Si hay muchas inserciones y eliminaciones en cualquier posición, lista. Y en la práctica, para pocos elementos el arreglo suele ganar igual, porque la memoria contigua vuela en la caché del procesador.
02La lista enlazada
Cada nodo guarda el dato y la dirección del siguiente. El último apunta a NULL, y una variable externa —la cabeza— guarda la dirección del primero:
typedef struct nodo {
int dato;
struct nodo *sig;
} Nodo;
Nodo *cabeza = NULL;
La estructura se refiere a sí misma: por eso hace falta el nombre struct nodo dentro de su
propia definición. Insertar al principio son tres líneas:
Nodo *n = malloc(sizeof(Nodo));
n->dato = x;
n->sig = cabeza;
cabeza = n;
Si se hace cabeza = n antes de n->sig = cabeza, el nodo apunta a
sí mismo y se pierde toda la lista. En estructuras enlazadas, el orden de las asignaciones de punteros
es el error más frecuente y el más difícil de ver leyendo.
Insertá y eliminá nodos, y mirá cómo se reacomodan los punteros y cuántos pasos cuesta cada operación.
03Variantes y estructuras derivadas
| Estructura | Cómo es | Para qué sirve |
|---|---|---|
| Lista doblemente enlazada | Cada nodo apunta al siguiente y al anterior | Recorrer en los dos sentidos, eliminar sin buscar el anterior |
| Lista circular | El último apunta al primero | Planificadores por turno rotativo, buffers |
| Pila (LIFO) | Se saca el último que entró | Llamadas a funciones, deshacer, evaluar expresiones |
| Cola (FIFO) | Se saca el primero que entró | Buffers de comunicación, colas de eventos |
| Cola circular | Arreglo fijo con índices que dan la vuelta | Buffers de UART en microcontroladores |
| Árbol binario de búsqueda | Cada nodo tiene dos hijos, ordenados | Búsqueda en O(log n) si está equilibrado |
Cada llamada a una función apila su marco —variables locales y dirección de retorno— y al volver lo desapila. Por eso una recursión sin caso base termina en stack overflow: la estructura de datos que se desborda es, literalmente, una pila.
04Árboles binarios
En un árbol binario de búsqueda, todo lo menor que un nodo está en su subárbol izquierdo y todo lo mayor, en el derecho. Buscar es bajar comparando, y si el árbol está equilibrado cada comparación descarta la mitad de los datos restantes: 20 comparaciones alcanzan para un millón de elementos.
- Recorrido en orden —izquierdo, nodo, derecho— devuelve los datos ordenados de menor a mayor.
- En preorden —nodo, izquierdo, derecho— sirve para copiar la estructura.
- En postorden —izquierdo, derecho, nodo— para liberarla, porque destruye los hijos antes que el padre.
El problema es el desequilibrio: si los datos llegan ya ordenados, el árbol degenera en una lista y la búsqueda vuelve a ser O(n). De ahí salen los árboles que se reequilibran solos, como los AVL y los rojo-negro.
05Dónde se usan en un equipo
- Buffer circular de UART. La interrupción de recepción escribe en la cola y el programa principal lee: es la estructura más usada en sistemas embebidos.
- Cola de eventos. Una interfaz gráfica, un sistema operativo de tiempo real y un firmware con máquina de estados usan todos el mismo esquema productor-consumidor.
- Lista de tareas de un planificador. Ordenada por prioridad o por vencimiento.
- Historial de muestras. Una ventana deslizante para promediar o filtrar señales se implementa con una cola circular.
- Tabla de dispositivos. El núcleo de un sistema operativo mantiene listas enlazadas de procesos abiertos, archivos y controladores.
06En el laboratorio
Implementar en C insertar al inicio, al final y ordenado, eliminar por valor, buscar, contar y liberar toda la lista. Verificar con valgrind que no queda memoria perdida.
Escribir una cola circular de tamaño fijo con índices de lectura y escritura, y usarla para recibir datos de un puerto serie sin perder bytes mientras el programa hace otra cosa.
Insertar cien mil elementos al principio de un arreglo y de una lista, y medir el tiempo de cada uno. Repetir accediendo por índice. Contrastar los números con la tabla de la primera sección.
07Errores frecuentes
- Perder la cabeza de la lista al reasignar punteros en el orden equivocado.
- Liberar un nodo antes de guardar su
sig, y quedarse sin manera de llegar al resto. - No contemplar la lista vacía ni la eliminación del primer nodo, que son los dos casos borde.
- Olvidar poner NULL en el
sigdel último nodo. - Usar una lista donde convenía un arreglo, sólo porque suena más sofisticado.
- Recorrer con el mismo puntero que se usa para liberar, sin una variable auxiliar.
08Autoevaluación
¿Cuánto cuesta insertar al principio de una lista enlazada?
O(1): reservar el nodo y cambiar dos punteros, sin importar cuántos elementos haya.
¿Por qué acceder al elemento 500 de una lista es lento?
Porque hay que seguir 500 punteros: no se puede calcular la dirección, hay que recorrer.
¿Qué estructura conviene para el buffer de recepción de una UART?
Una cola circular sobre un arreglo fijo: no necesita malloc, es de tamaño conocido y la interrupción la puede usar con seguridad.
¿Qué recorrido de un árbol binario de búsqueda devuelve los datos ordenados?
El recorrido en orden: izquierdo, nodo, derecho.
¿Qué pasa si se insertan datos ya ordenados en un árbol binario simple?
Degenera en una lista: cada nodo tiene un solo hijo y la búsqueda pasa de O(log n) a O(n).
¿Por qué una recursión infinita termina en «stack overflow»?
Porque cada llamada apila un marco con sus variables locales, y la pila del programa tiene un tamaño limitado.
09Para ampliar
- Thomas H. Cormen y otros. Introduction to Algorithms. 4.ª ed., MIT Press, 2022. La referencia sobre estructuras de datos y su análisis de costos.
- Mark Allen Weiss. Estructuras de datos en C. Addison-Wesley, 1995. Implementaciones completas en C, al nivel exacto de la materia.
- Brian W. Kernighan y Dennis M. Ritchie. El lenguaje de programación C. 2.ª ed., Pearson, 1991. El capítulo 6 arma una tabla de símbolos con estructuras enlazadas, como ejemplo integrador.
- Robert Sedgewick. Algorithms in C. 3.ª ed., Addison-Wesley, 1998. Muy gráfico, con buenas explicaciones de árboles y su equilibrado.