Arreglos y listas enlazadas
Mapa conceptual
Arreglo (array)
Bloque de memoria contigua de mismo tipo. Como los elementos están uno tras otro, el acceso por índice es O(1): el computador calcula la dirección base + índice·tamaño. El precio: insertar o borrar en el medio obliga a DESPLAZAR todos los siguientes (O(n)), y el tamaño fijo puede obligar a copiar todo al crecer.
Lista enlazada
Secuencia de nodos, cada uno con su dato y un puntero al siguiente. Insertar al inicio o junto a un nodo conocido es O(1): solo cambias punteros, no mueves datos. El precio: para llegar al elemento k hay que RECORRER desde la cabecera (O(n)); no hay acceso aleatorio.
| Operación | Arreglo | Lista enlazada |
|---|---|---|
| Acceso por índice | O(1) | O(n) (recorrer) |
| Insertar al inicio | O(n) (desplazar) | O(1) (nuevo nodo) |
| Insertar en el medio | O(n) | O(1) una vez localizado el sitio |
| Buscar un valor | O(n) | O(n) |
| Memoria por elemento | compacta, contigua | extra por el puntero |
| Crecimiento | a veces copiar (amortizado O(1)) | siempre O(1) añadir al final |
¿Cuándo cada uno?
- Arreglo cuando predominan LECTURAS por posición o recorridos secuenciales rápidos (cache friendly): vectores, filas de un dataset, píxeles.
- Lista enlazada cuando hay MUCHAS inserciones/borrados en el medio a partir de un nodo ya conocido, y no necesitas acceso aleatorio: colas de prioridad enlazadas, historiales deshacer.
- En la práctica, el arreglo dinámico (vector/lista de Python) gana casi siempre por localidad de memoria; la lista enlazada pura es más pedagógica que usada.
¿Cuál es la complejidad de INSERTAR un elemento al principio de una lista enlazada simplemente enlazada frente a un arreglo?
El acceso aleatorio a la posición i de un arreglo es O(1) porque sus elementos son de tamaño fijo y están en memoria contigua.
Clasifica cada operación según dónde rinde mejor (complejidad más baja).
Arreglo
Lista enlazada
Igual en ambos
Errores frecuentes
- Creer que la lista enlazada hace cualquier inserción O(1): Localisation del punto cuesta O(n).
- Olvidar el costo en caché y asumir que dos estructuras con el mismo Big-O son igual de rápidas.
- Usar arreglo cuando se necesita insertar al inicio a menudo: cada inserción desplaza todo.
Ejemplo resuelto
- Necesitas una cola de tareas donde siempre añades al final y tomas del principio.
- Con un arreglo, tomar del principio desplaza todos los elementos: O(n).
- Con una lista enlazada (o un arreglo circular), tomar del principio es mover la cabecera: O(1).
- Conclusión: para ese patrón FIFO, la estructura enlazada o un deque es mejor que un arreglo plano.
- Nota: si además necesitaras «mirar la tarea i-ésima», volverías a preferir el arreglo.
Todo un DataFrame es, por dentro, un arreglo (o varios). Por eso filtrar por posición o recorrer columnas es veloz, e insertar filas en el medio es caro. Entender arreglo-vs-enlazada explica por qué «añadir una fila a un CSV reescribiéndolo» no escala y una base de datos usa índices aparte.
Contiguo o enlazado
Estructuras lineales (repaso formal)
Arreglos y listas enlazadas con sus operaciones y costos.
Estás implementando un historial «deshacer» donde lo frecuente es añadir la última acción y deshacer la más reciente, pero a veces consultar la acción número k. Argumenta si prefieres arreglo o lista enlazada y qué operación de tu lista de deseos sale cara.
VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.