Thread by @charliesbot

Hora de un ⚡️#thread #Javascript

Una estructura de datos que enterramos saliendo de la escuela porque en lenguajes de alto nivel no es muy usada. Pero muchas de las estructuras que usamos la usan por dentro, y por ende es pilar de la programación.

Hablemos de Linked Lists!

Hace poco escuche una analogía que me gustó mucho para explicar linked lists.

Imaginemos que hiciste una mudanza. Clasificaste las cosas en cajas, y cada una de ellas tiene un post-it que indica donde está la siguiente caja.

De esta forma, para poder llegar a cualquier caja, tendremos que empezar desde la primera, e ir leyendo cada post-it hasta encontrar la que necesitemos.

Cada caja solo sabe su contenido y donde está la siguiente caja (y la anterior en el caso de una lista doblemente ligada)

Podemos acceder a una caja de forma directa? No! Solo desde la 1er caja podemos seguir el orden.

La ventaja? Podemos poner una caja en x lado, sin importar donde. Ya no estamos limitados por el espacio alrededor: si tenemos un rincón libre en la casa, ahí puede estar una caja.

Porque esto es ventaja? 📦

Pensemos en estructuras de datos.

Un array usa memoria contigua. Esto es que el sistema reserva memoria para guardar información. Aunque tengamos más memoria en el sistema, no podremos usarla porque no es vecina de la memoria que estamos usando

Una linked list usa memoria dinámica: esto es, que donde haya memoria libre, ahí se guardará información. Sin importar donde este. Para eso tenemos los post-its! Ellos nos dirán donde buscar.

Pues bien, en una linked list, la caja es lo que llamamos nodo.

Lo que contiene la caja son los datos. Y el post it es conocido como puntero, el cual es una referencia al nodo (caja) siguiente!

La estructura general de un linked list es:
- Cabeza: es el primer nodo, y es un auxiliar para ayudarnos a conocer como ir moviendonos en la estructura
- Nodo: contienen data y una referencia al siguiente nodo!

Y como sabemos que acabamos de recorrer la lista?

Sabemos que terminamos de recorrer la cuando encontramos un nodo que no tiene una referencia a otro nodo!

Hay varios métodos en un linked list!

- push
- pop
- get (recibe un index y regresa el contenido de ese nodo)
- delete (elimina un nodo de cierto index!)

Push

1) Recibimos como parámetro la nueva data
2) Creamos un nuevo nodo y asignamos la data que recibimos
3) Recorremos toda la lista hasta encontrar el último nodo
4) En lugar de que su referencia sea null, su nueva referencia va a ser... el nodo que creamos!

Pop
1) Recorremos la lista hasta llegar al último nodo
2) Conforme avanzamos, guardamos una referencia al nodo anterior
3) Cuando lleguemos al último nodo, sabemos que este es el vamos a eliminar. Usamos la referencia del anterior para reemplazar su puntero a null.

Cómo se ve un Linked List en código?

Tenemos dos clases: Nodo y LinkedList.

Linked List está a cargo de moverse a través de todos los nodos!

Empecemos con algo interesante: que tal si implementas tu la función get?

Recuerda: get recibe un index y regresa el dato de ese index!

Antes de concluir el thread: algo que siempre escucho es "para que aprendo linked lists si mi lenguaje hace todo por mi?"

Y es cierto! Lenguajes como Ruby y Javascript se hacen cargo de la memoria por ti.

Pero detrás de escenas, las estructuras que usamos como stack y queues usan Linked Lists para el manejo de memoria.

Conocer las bases de la programación nos ayuda a entender porque ocurren las cosas.

El próximo thread será de un ejercicio de leetcode que justamente gira en torno a resolver el problema con Linked List.

Pero no podemos trabajarlo sin explicar primero que herramienta tenemos a la mano!

Este es un accesorio más para nuestras batallas de código.

Y esto es todo! Nos vemos en otro ⚡️ #thread de: aprendiendo estructuras de datos y algoritmos para las entrevistas de trabajo en #FAANG.

🤓