Cómo conectar datos entre sí sin necesitar un bloque continuo de memoria.
Un array reserva un bloque fijo y continuo de memoria. Si se llena, o si necesitas insertar algo en el medio, es costoso: hay que mover todo lo que está después.
Tamaño fijo desde el inicio. Insertar en el medio implica correr todos los elementos siguientes un lugar.
Crece de a un elemento. Insertar es solo cambiar a qué apunta un puntero, sin mover nada más.
Cada nodo guarda dos cosas: un dato y una referencia (puntero) al siguiente nodo.
Cada nodo apunta solo al siguiente. El último apunta a NULL: ahí termina la lista.
el nuevo nodo pasa a ser la cabeza
se recorre hasta el último y se conecta ahí
A ahora apunta directo a C
Se empieza en la cabeza y se avanza nodo por nodo hasta llegar a NULL.
| Paso | Puntero actual |
|---|---|
| actual = head | apunta a A imprime A |
| actual = actual.siguiente | apunta a B imprime B |
| actual = actual.siguiente | apunta a C imprime C |
| actual = actual.siguiente | apunta a NULL → se detiene |
Cada nodo guarda dos punteros: uno al siguiente y otro al anterior. Se puede recorrer para adelante o para atrás.
En una lista simple, para ir "atrás" hay que recorrer todo desde el inicio. En una lista doble, el nodo ya sabe quién es su anterior.
El botón "anterior" en un carrusel de fotos, o navegar atrás y adelante en un editor de texto.
El nodo a borrar ya conoce a su anterior y a su siguiente: solo hay que reconectarlos entre sí.
No hay NULL al final: la lista se cierra en un círculo. Sirve para turnos que se repiten, como el reparto round-robin.
| Array | Lista enlazada | |
|---|---|---|
| Tamaño | Fijo desde el inicio | Crece de a un nodo |
| Acceder a un elemento | Directo, por posición | Hay que recorrer desde el inicio |
| Insertar en el medio | Mueve todo lo siguiente | Solo cambia un puntero |
| Memoria | Un bloque continuo | Nodos sueltos, conectados por punteros |
Simple: cada nodo apunta solo al siguiente. El último apunta a NULL.
Doble: cada nodo apunta al siguiente y al anterior. Se recorre en ambos sentidos.
Circular: el último nodo apunta de vuelta al primero. No hay NULL.
Dato curioso: una cola FIFO se puede construir con una lista enlazada, encolando al final y desencolando desde la cabeza.