Estructuras de datos explicadas: arrays vs listas enlazadas

Un array y una lista enlazada resuelven el mismo problema —guardar una colección ordenada de elementos— pero lo hacen con planteamientos completamente distintos por dentro. Esa diferencia interna es la que explica por qué una operación que es instantánea en una estructura puede ser lenta en la otra, y por qué elegir mal la estructura de datos puede convertir un programa rápido en uno que se arrastra a medida que crecen los datos.

Si vienes de la hoja de ruta para empezar a programar y ya conoces las listas de Python o los arrays de JavaScript a nivel de uso, este artículo te lleva un paso más allá: qué pasa realmente en memoria cuando las usas.

Qué es un array por dentro

Un array reserva un bloque de memoria contiguo: todos sus elementos están uno justo detrás del otro. Esto tiene una consecuencia enorme: si conoces la posición (el índice) de un elemento, el ordenador puede calcular su dirección exacta en memoria con una simple operación aritmética, sin tener que recorrer nada. Por eso acceder a lista[500] tarda exactamente lo mismo que acceder a lista[0].

El precio de esa ventaja aparece cuando insertas o borras algo que no está al final: como los elementos deben seguir contiguos, el ordenador tiene que desplazar en memoria todos los elementos posteriores para hacer (o cerrar) el hueco.

Qué es una lista enlazada por dentro

Una lista enlazada no reserva un bloque contiguo. En su lugar, cada elemento ("nodo") guarda su valor y un puntero al siguiente nodo, y esos nodos pueden estar dispersos en cualquier parte de la memoria. Para llegar al elemento en la posición 500 no hay atajo aritmético posible: hay que empezar en el primer nodo e ir saltando de puntero en puntero, uno a uno, hasta llegar.

A cambio, insertar o borrar un nodo cuando ya tienes una referencia a su posición es casi gratis: basta con recolocar un par de punteros, sin mover ningún otro elemento de sitio.

Complejidad de sus operaciones, en una tabla

El "O(1) amortizado" del array al insertar al final se debe a que, en lenguajes como Python o JavaScript, los arrays dinámicos reservan más memoria de la necesaria y solo tienen que redimensionarse (copiarse a un bloque más grande) de vez en cuando, no en cada inserción.

El mismo problema, dos estructuras distintas

Para que la diferencia quede clara, aquí tienes la misma operación —insertar un elemento al principio de la colección— resuelta con un array normal y con una lista enlazada implementada a mano en Python.

tareas = ["revisar PR", "desplegar", "responder correos"]

# Insertar al principio: Python desplaza el resto de elementos
tareas.insert(0, "reunión diaria")

print(tareas)
# ['reunión diaria', 'revisar PR', 'desplegar', 'responder correos']
# Coste: O(n), porque cada elemento se mueve una posición

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.siguiente = None

class ListaEnlazada:
    def __init__(self):
        self.cabeza = None

    def insertar_al_principio(self, valor):
        nuevo = Nodo(valor)
        nuevo.siguiente = self.cabeza  # solo recoloca punteros
        self.cabeza = nuevo            # coste: O(1), no hay que mover nada

lista = ListaEnlazada()
lista.insertar_al_principio("desplegar")
lista.insertar_al_principio("reunión diaria")

Cuándo usar cada una en la práctica

En el día a día, casi siempre vas a usar arrays (listas de Python, arrays de JavaScript): son más simples, tienen mejor rendimiento en caché por la contigüidad en memoria, y la mayoría de problemas reales necesitan acceso frecuente por índice. Las listas enlazadas aparecen sobre todo como pieza interna de otras estructuras —pilas, colas, tablas hash con colisiones— o cuando sabes de antemano que vas a hacer muchísimas inserciones y borrados en los extremos y muy pocos accesos aleatorios.

Entender esta diferencia también te prepara para el siguiente paso lógico: una vez tienes claro cómo se guardan los datos, el orden en que los recorres o los ordenas empieza a importar. Ahí es donde entran en juego los algoritmos de ordenación, que dependen directamente de cómo esté organizada la colección que están ordenando.

Por qué esto se pregunta tanto en entrevistas

No es casualidad que las diferencias entre array y lista enlazada aparezcan en casi cualquier entrevista técnica de programador, incluso para puestos junior. No se trata de que vayas a implementar una lista enlazada a mano en tu trabajo del día a día —rara vez ocurre—, sino de comprobar si entiendes qué pasa "debajo" de las estructuras que usas constantemente. Esa comprensión es la que te permite explicar por qué tu código es lento cuando lo es, en lugar de limitarte a probar cosas al azar.