Ambos almacenan secuencias, pero tienen perfiles de costos opuestos. Un array es memoria contigua con indexación O(1); una lista enlazada son nodos dispersos unidos por punteros, con inserción/eliminación O(1) en los extremos pero sin indexación.
Ambos almacenan secuencias, pero tienen perfiles de costos opuestos. Un array es memoria contigua con indexación O(1); una lista enlazada son nodos dispersos unidos por punteros, con inserción/eliminación O(1) en los extremos pero sin indexación.
| Operación | Array (dinámico) | Lista enlazada |
|---|
| Acceso por índice | O(1) | O(n) |
| Búsqueda | O(n) | O(n) |
| Inserción/eliminación en la cabeza | O(n) | O(1) |
| Inserción/eliminación en la cola | O(1) amortizado | O(1) con tail ptr |
| Inserción/eliminación en el medio | O(n) | O(n) búsqueda + O(1) splice |
| Sobrecarga de memoria | baja | alta (puntero por nodo) |
| Localidad de caché | excelente | pobre |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
En la práctica los arrays ganan la mayoría de las veces porque la localidad de caché supera las diferencias Big-O para tamaños típicos.
Conocer ambos te permite justificar tu elección en entrevistas en lugar de asumir ciegamente — y explicar por qué "la inserción O(1)" rara vez vence a un array contiguo.
Una biblioteca de preguntas de entrevista de IT con respuestas detalladas — de Junior a Senior.
Donar