Qué diferencia hay entre array y lista
Hay más de una manera de guardar muchas cosas en orden. Si pones las casillas juntas y numeradas en orden, puedes sacar cualquiera en cuanto dices su número. Si en cambio las dejas repartidas por ahí y las unes con notas que dicen dónde está la siguiente, resulta fácil meter una casilla nueva en el medio. ¿Qué importa más: sacar rápido o meter con facilidad?
Casilleros juntos: el arreglo
En la lección anterior vimos que cada recipiente tiene su propia forma. La más sencilla es el arreglo: piensa en un casillero cuyas casillas numeradas están pegadas unas a otras en una fila.
Las casillas suelen numerarse desde 0: casilla 0, casilla 1, casilla 2, y así sucesivamente. Como todas tienen el mismo tamaño y están juntas, basta con sumar a la posición inicial el tamaño de una casilla multiplicado por el número para saber al instante dónde está cualquiera.
Toca un número para saltar directo a esa casilla. Las casillas están juntas, así que el número la encuentra al instante.
Al tocar un número, esa casilla se iluminó enseguida. Como las casillas están una al lado de otra, a cualquiera se llega en un paso, y tarda lo mismo haya diez casillas o un millón.
Sacar algo por su número de este modo se llama acceso rápido, y es la mayor ventaja del arreglo. Pero ¿de verdad tienen que estar juntas las casillas? ¿Qué pasa si las repartimos?
Casilleros repartidos: la lista
Una lista no junta sus casillas: están repartidas por la memoria. Entonces, ¿cómo se mantiene el orden? Cada casilla lleva una nota que dice dónde está la siguiente.
Desde la primera casilla lees su nota y vas a la siguiente, lees esa nota y pasas a la otra. Como las casillas quedan enlazadas una tras otra por las notas, esta forma se llama lista enlazada.
Toca la nota para seguirla hasta la siguiente casilla. Las casillas están repartidas, pero las notas mantienen el orden.
Al seguir las notas, las casillas repartidas quedaron unidas en una fila. A diferencia del arreglo, que salta por número, la lista tiene que leer cada nota e ir casilla por casilla.
Parece un poco más engorroso, pero esta estructura repartida tiene una ventaja inesperada. Pronto verás cuál es.
Acceso rápido vs acceso lento
Ahora comparemos los dos. Imagina que quieres la quinta casilla. Al arreglo le basta con el número: las casillas están juntas, así que salta allí de una vez.
La lista no puede hacer eso. Desde la primera casilla sigue las notas y va contando: una casilla, dos casillas, tres casillas. Por eso, cuanto más lejos está la casilla, más tarda.
Llega a la quinta. El arreglo lo hace en un paso; la lista avanza casilla por casilla desde el principio. Compara cuántas veces tocas.
La diferencia es clara. El arreglo llegó con un toque, mientras que la lista llegó solo después de varios. Para sacar cosas, el arreglo que salta por número es mucho más rápido.
Entonces, ¿el arreglo siempre es mejor? No. En la siguiente escena llega el momento en que brilla la lista: cuando metes algo en el medio.
Meter una casilla en el medio
Esta vez, metamos una casilla nueva en medio de la fila. Para una lista es muy fácil: cambias la nota de la casilla anterior para que apunte a la nueva, y haces que la nota de la nueva apunte a la que antes iba después.
Basta con reescribir dos notas; las demás casillas no se tocan. Aunque haya un millón de casillas, solo cambian dos notas.
Mete una casilla nueva en el medio. La lista reescribe dos notas; el arreglo empuja todas las casillas posteriores. Compara cuánto trabajo da cada uno.
¿Qué tal le fue al arreglo? Para hacer sitio en el medio, tuvo que empujar una a una todas las casillas posteriores, porque están juntas y no queda ningún hueco. La lista terminó con dos notas.
Por eso, para tareas en las que se mete algo en el medio a menudo, la lista es mucho más cómoda. El acceso rápido es para el arreglo y la inserción fácil, para la lista: ganar una cosa significa renunciar a la otra.
En resumen
En pocas palabras: un arreglo es un casillero de casillas numeradas y juntas, así que puedes sacar cualquier cosa por su número al instante. Una lista son casillas repartidas, cada una con una nota que dice dónde está la siguiente, así que meter algo en el medio es fácil.
Para llegar a la quinta, el arreglo es rápido; para meter una en el medio, la lista es cómoda. Elige según lo que hagas más a menudo.
Toca en orden los puntos clave para repasar. (arreglo de casilleros juntos → lista de casilleros repartidos → acceso rápido vs lento → inserción en medio)
Ahora ya sabes que incluso las mismas cosas se dan bien para tareas distintas según cómo las guardes. Los arreglos y las listas son la primera bifurcación al elegir la forma de un recipiente.
La próxima lección trata de dos recipientes especiales: la pila, que mete y saca solo por un extremo, y la cola, que solo deja salir las cosas en el orden en que se pusieron en fila.