Poner en fila: arreglos y listas

Casilleros juntos: el arreglo

Antes aprendimos que cada recipiente
tiene su propia forma.
La forma más simple de todas es el arreglo.
Es un casillero donde las casillas numeradas
van juntas en una sola fila.
Casilla 0, casilla 1, casilla 2,
cada casilla lleva su propio número.
Como las casillas están todas juntas,
saber el número te dice al instante dónde está.

Toca un número para saltar directo a esa casilla. Las casillas van juntas, así que el número la encuentra al instante.

Cuando tocaste un número,
esa casilla se iluminó enseguida.
Como las casillas van una al lado de otra,
cualquier casilla se señala en un paso.
Sacar algo por número de este modo
se llama acceso rápido.
Es la mayor ventaja del arreglo.
Pero, ¿de verdad deben quedar juntas?
¿No podríamos esparcirlas?

Casilleros esparcidos: la lista

Una lista no junta sus casillas.
Las casillas están esparcidas por aquí y por allá.
¿Y cómo se mantiene el orden?
Cada casilla recibe una notita.
Esa nota guarda la dirección
de dónde está la siguiente casilla.
Así, desde la primera casilla lees su nota
y pasas a la siguiente, luego lees esa nota
y sigues a la de después.

Toca la nota para seguirla a la siguiente casilla. Las casillas están esparcidas, pero las notas mantienen el orden.

Siguiendo las notas,
las casillas esparcidas se enlazaron en una línea.
A diferencia del arreglo que salta por número,
una lista debe leer cada nota
e ir una casilla por vez, por turno.
Parece un poco más molesto,
pero esta estructura esparcida
da una ventaja inesperada.
Pronto verás cuál es.

Acceso rápido vs acceso lento

Ahora comparemos las dos.
Digamos que quieres la quinta casilla.
Para un arreglo, basta el número.
Las casillas van juntas, así que salta de una vez.
Una lista no puede hacer eso.
Desde la primera casilla sigues las notas,
una casilla, dos, tres,
contando tu camino por turno.
Así que cuanto más lejos, más tarda.

Llega al quinto. El arreglo lo hace en un paso; la lista va una casilla por vez desde el principio. Compara los clics.

La diferencia es clara.
El arreglo llegó con un toque,
mientras la lista necesitó varios para llegar.
Para sacar cosas,
el arreglo que salta por número es mucho más rápido.
¿Entonces el arreglo es sin más mejor?
No. En la siguiente escena
llega el momento en que la lista brilla:
cuando metes algo en medio.

Meter una en medio

Esta vez, en medio de la fila
metamos una casilla nueva.
Para una lista es muy fácil.
Cambias a dónde apunta la nota de la casilla de delante
para que apunte a la casilla nueva,
y haces que la nota de la casilla nueva
apunte a la que antes era la siguiente.
Arreglas solo dos notas,
dejas el resto de las casillas como están, y listo.

Inserta una casilla nueva en medio. La lista arregla dos notas; el arreglo empuja todas las casillas posteriores. Compara cuánto trabajo cuesta cada una.

¿Cómo le fue al arreglo?
Para hacer sitio en medio
tuvo que empujar cada casilla posterior, una a una.
Las casillas van juntas, así que no hay hueco vacío.
La lista, en cambio, terminó con dos notas.
Así que para insertar en medio a menudo,
una lista es mucho más cómoda.
El acceso rápido es del arreglo,
la inserción fácil es de la lista.
Las dos son un intercambio mutuo.

Resumamos

Reunido en una línea, es esto.
Un arreglo es un casillero de casillas numeradas y juntas,
con acceso rápido por número.
Una lista son casillas esparcidas,
cada una con una nota con la dirección de la siguiente,
así que insertar en medio es fácil.
Para llegar a la quinta, el arreglo es rápido;
para meter una en medio, la lista es cómoda.
Elige según lo que hagas más a menudo.

Toca los puntos clave en orden para repasar. (arreglo de casillero junto -> lista de casillero esparcido -> acceso rápido vs lento -> inserción en medio)

Ahora sabes que incluso las mismas cosas,
según cómo las guardes,
son buenas para tareas distintas.
Los arreglos y las listas
son la primera bifurcación al elegir la forma de un recipiente.
Luego veremos recipientes especiales
que meten y sacan
solo por un extremo,
apilar y hacer cola, juntos.