Arreglos vs. listas enlazadas

Al finalizar este tema

Podrás explicar las diferencias en la estructura de memoria entre los arreglos y las listas enlazadas, y podrás decidir cuál elegir según el contexto.

Arreglos: memoria contigua

Los arreglos (Arrays) almacenan los datos de forma contigua en la memoria.

Dirección de memoria:  100  104  108  112  116
            +----+----+----+----+----+
Valor:         | 10 | 20 | 30 | 40 | 50 |
            +----+----+----+----+----+
Índice:       0    1    2    3    4

La ventaja es que permite el acceso inmediato a través del índice.

arr = [10, 20, 30, 40, 50]
print(arr[3])  # 40 — Acceso inmediato (O(1))

Cuando decimos "tercera posición", calculamos la dirección de inicio más (3 × tamaño), lo que nos lleva directamente a esa ubicación. Se accede en un solo paso, independientemente del número de elementos.

Desventajas de los arreglos: inserción y eliminación

¿Cómo insertar 15 en el índice 1 de [10, 20, 30, 40, 50]?

Paso 1: Mover todos los elementos 20, 30, 40, 50 una posición hacia atrás
Paso 2: Insertar 15 en el espacio vacío

[10, 15, 20, 30, 40, 50]

Si hay 1 millón de datos, al insertar al principio es necesario desplazar los 1 millón de elementos.

Lista enlazada: memoria dispersa

En una lista enlazada, cada elemento recuerda la ubicación del siguiente elemento.

[10|→] → [20|→] → [30|→] → [40|→] → [50|∅]

Cada nodo = valor + dirección del siguiente nodo (puntero)

No es necesario que los nodos estén ubicados en posiciones contiguas en la memoria. Cada nodo solo necesita saber cuál es el siguiente.

Ventajas de las listas enlazadas: inserción y eliminación

Inserción de 25 después de 20 en [10|→] → [20|→] → [30|→]:

Paso 1: Crear nuevo nodo [25|→]
Paso 2: Cambiar el puntero de 20 a 25 y el puntero de 25 a 30

[10|→] → [20|→] → [25|→] → [30|→]

No es necesario desplazar otros nodos. Basta con modificar dos punteros. O(1).

Desventaja de las listas enlazadas: acceso.

# "¿Cuál es el tercer valor?"
# Arreglo: arr[3] → inmediato (O(1))
# Lista enlazada: desde el inicio 1→2→3 siguiendo (O(n))

Como no hay índices, para encontrar el valor en la posición n-ésima, hay que recorrerlo desde el principio n veces.

Resumen comparativo

Criterios de selección

En la práctica, la mayoría utiliza arreglos (listas en Python, Arrays en JavaScript). Los arreglos dinámicos de los lenguajes modernos ajustan su tamaño automáticamente y son favorables para la caché de la CPU. Las listas enlazadas se utilizan en situaciones especiales (implementación de colas, pilas, inserciones/eliminaciones a gran escala).