Listas simples con javascript

TRON (1982)

Estructuras de datos

Listas simples

Una lista simple o lista simplemente encadenada, son estructuras de datos muy parecidas a los array, donde el acceso al elemento o nodo , es a través de un puntero , a diferencia de un array donde este se accede a través de índices.
En un array los elementos están contiguos en lo que a memoria se refiere, en cambio en una lista pueden no estarlos , esto puede verse como una ventaja frente a los array, por ejemplo si agregamos un nuevo elemento en un array se verificará que haya un espacio contiguo en memoria disponible para el nuevo elemento y en caso de no haberlo se movera el array completo hasta otro lugar en memoria donde si haya un espacio completo, esto no sucede con las listas, los elementos pueden estar dispersos en memoria.
Otra ventaja, es que para ciertas operaciones como insertar en la mitad es constante en función del tiempo, por poner un ejemplo.

Una lista está compuesta por nodos, donde cada uno se conecta con el nodo siguiente (salvo el último), esto quiere decir que no puede ver para atrás o por quien fue enlazado.
Siempre se tiene como referencia el puntero o inicio de lista llamado head , este define el principio de la lista, sin este puntero de referencia no se podría acceder a la lista.
El último nodo enlaza con NULL y esto marca el fin de la lista.

Lista simplemente encadenada

Veamos una implementación de nodo y la lista:

En el código de arriba ⬆️ tenemos 2 funciones constructoras, por un lado la función Node a la cual le asignamos un value (que puede ser del tipo number, string, por nombrar algunos…) y tenemos next , que lo inicializamos en null, este sería el encargado de apuntar al próximo nodo en la lista, pero por ahora esa sería nuestra estructura inicial del tipo nodo.

La función constructora LinkedList , es la que utilizamos para inicializar la lista simple, es importante notar que al crear esta lista ya tenemos el puntero de referencia head para poder ir encadenando los nodos.

Hasta este momento solo tenemos….. una lista vacía, obviamente no nos es muy útil 😅 si no le agregamos métodos o funciones para poder ‘jugar’ un poco con este tipo de data abstracto .

Los nodos solo conocen a su predecesor.

🔰 Agregando nodos a la lista

Una vez instanciado linkedList , lo interesante sería poder agregar nuevos nodos, y acá se nos presentan varios casos a tener en consideración.

⚡️ Lista vacía insertamos el 1er nodo

Primer elemento de la lista.

Debemos asegurarnos, que al agregar el primer nodo a nuestra lista, head apunte a este nuevo nodo.
Ahora bien al momento de insertar un segundo o n nodo, podemos hacerlo al final de la lista o al principio de la lista.

⚡️ Agregar nodo al final (append)

Agregamos un nodo posterior

Para esta situación tenemos que buscar el nodo cuyo next sea NULL (eso significa que en el nodo que estoy parado es el último), y es importante resaltar esto de que el ‘próximo’ sea NULL… recordar que los nodos solo conocen su predecesor, por lo tanto si estuviéramos parados en NULL no podemos hacer que el anterior apunte al nuevo nodo!, por eso es que nos situamos un paso atrás y re asigansmosnode.next , ahora si, hacia el nuevo nodo.

⚡️ Agregar nodo al principio (prepend)

Reemplazamos el Head por 8

En este caso particular, lo importante es, primero crear el nuevo nodo (en este caso con un value de 8) y luego apuntarlo a lo que apunta head ( a 4 en este caso ), por último head reasignarlo al nuevo nodo.
Si lo hiciéramos en caso inverso, osea, primero pusiéramos la asignación de head al nuevo nodo, perdemos la referencia del resto de la lista 🤷🏻‍.

🔰 Removiendo nodos a la lista

Otra operación que necesitamos es la del borrado de nodo.

El caso más sencillo es querer borrar el primer elemento, en ese caso head se apunta a head.next .
Ahora para borrar cualquier otro elemento, lo primero es ubicar el nodo anterior al buscado( eso lo hacemos preguntando por next ) y apuntar ese nodo al next del que queremos borrar. 
Por ejemplo, queremos borrar el nodo con value 8, primero buscamos el nodo cuyo next tenga un value de 8 (ese seria el nodo con value 4) y hacemos que ese nodo apunte a lo que apunta el next del nodo que queremos borrar 🤢 (que sería el nodo con value 15), en otras palabras puentearlo…

🔰 Buscando un nodo

No hay mucho que explicar… si coincide con el elemento, devuelve true , si llega al final de la lista (NULL) el elemento no existe y devuelve false .

🔰 Primer elemento

Retorna el primer nodo 🤷🏻‍.

🔰 Largo de la lista

retorna el total de nodos presentes en la lista.

🌀 Implementacion completa

Proximo: Listas Dobles