La Guía Definitiva de Estructuras de Datos en JavaScript - Linked-Lists

Tiempo
~7m

Este es el tercer artículo en la serie sobre entrevistas para ingenieros de Frontend. Si te perdiste los primeros artículos, puedes accederlos aquí:

  1. Intro a Rendimiento de Algoritmos y Algoritmos de Búsqueda
  2. Algoritmos de Ordenación en JavaScript
  3. La Guía Definitiva de Estructuras de Datos: Stacks & Queues

Pre-requisitos

Cómo correr los ejemplos

Durante este artículo estaré utilizando repl.it para demostrar los ejemplos. Cada ejemplo tendrá un enlace donde podrás correr el código. Además podrás hacerle fork para que experimentes con el algoritmo o añadas notas.

Al entrar a los enlaces de repl.it podrás darle play o Run al algoritmo para ver el resultado. Para ver el código, presiona Show files. Puedes copiarlo a tu cuenta presionando Fork repl.

👉 Recomiendo que intentes construir el algoritmo antes de proceder a mi solución. Puedes hacerlo en repl.it, localmente en tu computadora, o cualquier otro método que te permita correr funciones de JavaScript.

Introducción

Un linked list es una estructura de datos linear que representa una lista de nodos conectados por punteros. Mantiene récord de cuál está al principio, cuál está al final, y de su tamaño. Cada nodo en la lista se preocupa por su propio valor y un puntero a valores adyacentes. No hay manera de accesar un nodo directamente ya que no tenemos una referencia directa.

Típicamente se le llama head al primer nodo en la lista y tail al último nodo en la lista. Los stacks y queues son tipos de linked lists. Un tren con varios vagones o la ruta trazada por Google Maps son algunos ejemplos de la vida real.

En este artículo veremos dos tipos de linked-lists:

  1. Singly-Linked Lists - sus nodos solo tienen una referencia a otro nodo, típicamente el próximo en la lista
  2. Doubly-Linked Lists - sus nodos tienen dos referencias a nodos, el que está antes en la lista y el que le sigue

Utilizaremos clases para modelar las estructuras y sus métodos. En el artículo anterior hice una pequeña introducción en caso de que necesites refrescar los conceptos.

👇 En este enlace podrás ver visualizaciones para stacks, queues, y linked-lists.

✨ Visualización Linked-Lists

Singly-Linked Lists

Las singly-linked lists tienen nodos que además de preocuparse por su valor, mantienen un puntero al próximo nodo en la lista.

Para recorrer una singly-linked list tienes que comenzar al principio y visitar a cada nodo hasta encontrar el que buscas, pero no puedes volver atrás.

Como los nodos sólo saben cuál nodo viene después, no se interesan por el que viene antes. El último nodo no apunta a ningún otro nodo por lo que hace referencia a null.

Utilizaremos un método que ya se nos hace bastante familiar, push(val), para añadir nodos al final de la lista.

Pseudocode push(val)

  1. Crea un nuevo nodo con el valor aceptado por el método
  2. Si está vacía, asigna el nuevo nodo a head y a tail
  3. Si no está vacía, re-asigna el nodo que le sigue al tail a que sea el nuevo nodo
  4. Re-asigna el tail para que sea el nuevo nodo
  5. Aumenta el tamaño de la lista por 1
  6. Devuelve la lista

Cada nodo puede tener cualquier valor. En este ejemplo añadiré strings.

La lista se ve como un objeto con tres propiedades. El valor de head y de tail tiene la forma de otro objeto (el nodo) con dos propiedades. La propiedad val lleva el valor del nodo y la propiedad next lleva la referencia al próximo nodo. La última propiedad es el dígito que representa el tamaño de la lista.

Para remover nodos del final de la lista, crearemos pop().

Pseudocode pop()

  1. Si la lista está vacía, devuelve null
  2. Crea una variable para mantener récord del nodo que estamos visitando
  3. Crea otra variable para mantener récord del nodo que visitamos previamente
  4. Re-asigna las variables cada vez que visites un nuevo nodo
  5. Cuando hayas alcanzado el final de la lista, re-asigna tail al nodo anterior
  6. Reasigna el siguiente nodo de tail a null
  7. Reduce el tamaño de la lista por 1
  8. Si esta remoción hace que la lista esté vacía, re-asigna head y tail a 0
  9. Devuelve el último nodo

Ahora podemos remover el último nodo en nuestra lista.

Un beneficio de las linked-lists es que podemos insertar y remover de ambos extremos en tiempo constante. Ya vimos como hacerlo al final de la lista, ahora veremos cómo hacerlo al principio. Utilizaremos dos métodos que también reconocerás como métodos de arreglos. Shift() remueve un nodo del principio mientras que unshift(val) añade un nodo al principio. Los nombres de estos métodos son confusos, pero si piensas que shift tiene menos letras que unshift puedes asociarlo con que hace que la lista sea más corta. Unshift es más larga por lo que la puedes asociar con alargar o agrandar la lista.

Pseudocode shift()

  1. Si la lista está vacía, devuelve null
  2. Crea una constante para guardar el nodo head
  3. Re-asigna head al siguiente nodo del head antiguo que guardamos en el paso anterior
  4. Reduce el tamaño de la lista por 1
  5. Si esto remueve el último nodo de la lista, re-asigna tail a null
  6. Devuelve el nodo que removiste

La complejidad de una doubly-linked list es parecida a la de las listas anteriores. La diferencia es en la remoción. Ya que los nodos de esta cuentan con punteros en ambas direcciones, el rendimiento es constante al remover nodos del principio o del final de la lista.

✨ Replit Doubly-Linked Lists

Conclusión

Las linked-lists son útiles cuando el orden de los datos es importante y solo requerimos acceso por los extremos. Algunos ejemplos reales de linked-lists lo son la habilidad del buscador de ir a la página anterior en ambas direcciones y la habilidad de deshacer y rehacer (undo/redo).

Para aplicaciones que requieran acceder elementos en posiciones específicas a menudo, no las recomendaría. La decisión al escoger un tipo de lista sobre otro va a depender, mayormente, de si necesitas remover elementos en cualquier extremo o si necesitas recorrer la lista en cualquier dirección.