JavaScript

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

Leira Sánchez
Leira Sánchez

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.

class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}

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.

class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}

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
push(val) {
// crea un nuevo nodo con el valor aceptado por el método
const newNode = new Node(val);
// si está vacía, no tiene cabeza
if (!this.head) {
// de ser así, asigna head y tail a el nuevo nodo
this.head = newNode;
this.tail = this.head;
} else {
// si no está vacía, re-asgina el nodo que le sigue al tail a que sea el nuevo nodo
this.tail.next = newNode;
// re-asigna el tail para que sea el nuevo nodo
this.tail = newNode;
}
// aumenta el tamaño de la lista por 1
this.length++;
// devuelve la lista
return this;
}

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

const list = new SinglyLinkedList();
list.push("Hola");
list.push("Bonjour");
list.push("Hello");
console.log(list.length); // 3
console.log(list);
// SinglyLinkedList {
head: Node { val: 'Hola', next: Node { val: 'Bonjour', next: [Node] } },
tail: Node { val: 'Hello', next: null },
length: 3
}

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
pop() {
// si la lista está vacía, devuelve null
if (!this.head) return;
// crea una variable para mantener récord del nodo que estamos visitando
let currNode = this.head;
// crea otra variable para mantener récord del nodo que visitamos previamente
let prevNode = currNode;
while(currNode.next) {
// re-asigna las variables cada vez que visites un nuevo nodo
prevNode = currNode;
currNode = currNode.next;
}
// cuando hayas alcanzado el final de la lista, re-asgina tail al nodo anterior
this.tail = prevNode;
// reasigna el siguiente nodo de tail a null
this.tail.next = null;
// reduce el tamaño de la lista por 1
this.length--;
if (this.length === 0) {
// si esta remoción hace que la lista esté vacía, re-asgina head y tail a 0
this.head = null;
this.tail = null;
this.length = 0;
}
// devuelve el último nodo
return currNode;
}

Ahora podemos remover el último nodo en nuestra lista.

list.pop(); // Node { val: 'Hello', next: null }
console.log(list.length); // 2
console.log(list);
// SinglyLinkedList {
head: Node { val: 'Hola', next: Node { val: 'Bonjour', next: null } },
tail: Node { val: 'Bonjour', next: null },
length: 2
}

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
shift() {
// si la lista está vacía, devuelve null
if (!this.head) return;
// crea una constante para guardar el nodo head
const prevHead = this.head;
// re-asigna head al siguiente nodo del head antiguo que guardamos en el paso anterior
this.head = prevHead.next;
// reduce el tamaño de la lista por 1
this.length--;
// si esto remueve el último nodo de la lista, re-asigna tail a null
if (this.length === 0) this.tail = null;
// devuele el nodo que removiste
return prevHead;
}

Removamos el primer nodo de la lista. Luego de hacer esto solo debe quedar un nodo con valor “Bonjour”.

list.shift(); // Node { val: 'Hola', next: Node { val: 'Bonjour', next: null } }
console.log(list);
// SinglyLinkedList {
head: Node { val: 'Bonjour', next: null },
tail: Node { val: 'Bonjour', next: null },
length: 1
}

El único nodo que queda en la lista es el head y el tail a la misma vez.

Ahora aprenderemos como añadir nodos al principio de la lista.

Pseudocode unshift(val)

  1. Si la lista está vacía, el nuevo nodo será head y tail
  2. Si ya existe un nodo en la lista, guarda el head original en una constante
  3. Re-asigna el head al nuevo nodo
  4. El antiguo head ahora es el próximo nodo del head nuevo
  5. Aumenta el tamaño de la lista por 1
  6. Devuelve la lista
unshift(val) {
// si la lista está vacía, el nuevo nodo será head y tail
if(!this.head) {
this.head = new Node(val);
this.tail = this.head;
} else {
// si ya existe un nodo en la lista, guarda el head original en una constante
const prevHead = this.head;
// re-asigna el head al nuevo nodo
this.head = new Node(val);
// el antiguo head ahora es el próximo nodo del head nuevo
this.head.next = prevHead;
}
// aumenta el tamaño de la lista por 1
this.length++;
// devuelve la lista
return this;
}

Volvamos a colocar “Hola” al principio de la lista con unshift(”hola”).

list.unshift("Hola");
console.log(list);
// SinglyLinkedList {
head: Node { val: 'Hola', next: Node { val: 'Bonjour', next: null } },
tail: Node { val: 'Bonjour', next: null },
length: 2
}

La complejidad de una singly-linked list es:

| Acción | Big O |
| --------- | ----------- |
| Inserción | O(1) |
| Remoción | O(1) - O(n) |
| Búsqueda | O(n) |

Insertar nodos al final de la lista es constante pues siempre sabemos cuál es el último nodo. Remover nodos dependerá de la posición en la que se encuentre. Será constante si es el primer o el último nodo. De lo contrario, habría que recorrer la lista uno a uno desde el principio hasta encontrar el nodo y removerlo. En el peor caso, habría que recorrer casi toda la lista hasta dar con el nodo por lo que el rendimiento sería O(n).

✨ Replit Singly-Linked Lists

Doubly-Linked Lists

Las doubly-linked lists son muy parecidas a las singly-linked lists. La única diferencia es que los nodos de ésta tienen dos punteros, uno para el próximo nodo y otro para el nodo anterior. Así que se pueden recorrer en ambas direcciones empezando en cualquier extremo.

class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}

La clase es idéntica al singly-linked list. La diferencia la veremos en la clase del nodo y en sus métodos. Tiene los mismos métodos, pero la lógica es diferente ya que hay que tomar en consideración un puntero más.

class Node {
constructor(val) {
this.val = val;
this.next = null;
this.prev = null;
}
}

El primer nodo, head, tiene un puntero para el valor anterior apuntando a null y otro apuntando al próximo nodo, de haberlo. Si solo hay un nodo, ambos punteros tendrán valor null. El último nodo, tail, tiene un puntero hacia el nodo anterior y el puntero hacia el próximo nodo apunta a null. Al igual que el head, si solo hay un nodo en la lista, ambos punteros de tail tendrán valor null.

Pseudocode push(val)

  1. Crea un nodo nuevo con el valor aceptado por el método
  2. Si la lista está vacía, asigna el nodo nuevo a head
  3. Si no está vacía, crea una constante para guardar el tail original
  4. Asigna el nodo nuevo al puntero al próximo valor del tail
  5. Asigna el tail original al puntero al valor previo del nodo nuevo
  6. Independientemente de si está vacía o no, al utilizar push los nodos se añaden al final de la lista por lo que siempre hay que asignarlo a ser el nuevo tail
  7. Aumenta el tamaño de la lista por 1
  8. Devuelve la lista
push(val) {
// crea un nodo nuevo con el valor aceptado por el método
const newNode = new Node(val);
// si la lista está vacía, asigna el nuevo nodo a head
if (!this.head) {
this.head = newNode;
} else {
// si la lista no está vacía, crea una constante para guardar el tail original
const tail = this.tail;
// asigna el nodo nuevo al puntero al próximo valor del tail
tail.next = newNode;
// asigna el tail original al puntero al valor previo del nodo nuevo
newNode.prev = tail;
}
// el nodo nuevo ahora será el tail de la lista
this.tail = newNode;
// aumenta el tamaño de la lista por 1
this.length++;
// devuelve la lista
return this;
}

Crearemos una lista con un solo nodo. Podremos ver que ambos el head y el tail apuntan al nodo nuevo. No existe un valor antes ni un valor después por lo que los punteros a next y a prev apuntan a null.

const list = new DoublyLinkedList() // list: DoublyLinkedList { head: null, tail: null, length: 0 }
list.push("hello");
console.log(list);
// list: DoublyLinkedList {
head: Node { val: 'hello', next: null, prev: null },
tail: Node { val: 'hello', next: null, prev: null },
length: 1
}

Al igual push, pop nos permite modificar el final de la lista en tiempo constante. En este caso, removeremos el último nodo.

Pseudocode pop()

  1. Si la lista está vacía, devuelve null
  2. Crea una constante para guardar el tail original
  3. Si solo hay un nodo, re-asigna head y tail a null
  4. De lo contrario
    1. El nuevo tail será el nodo anterior al tail original
    2. No habrá nodo después del nuevo tail
    3. El nodo anterior al nuevo tail será el nodo anterior al nodo anterior al tail original
  5. Reduce el tamaño de la lista por 1
  6. Devuelve la lista
pop() {
// si la lista está vacía, devuelve null
if (!this.head) return head;
// crea una constante para guardar el tail original
const tail = this.tail;
// si solo hay un nodo, re-asigna head y tail a null
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
// el nuevo tail será el nodo anterior al tail original
this.tail = tail.prev;
// no habrá nodo después del nuevo tail
this.tail.next = null;
// el nodo anterior al nuevo tail será el nodo anterior al nodo anterior del tail original
this.tail.prev = tail.prev.prev;
}
// reduce el tamaño de la lista por 1
this.length--;
// devuelve la lista
return tail;
}

Si removemos el único nodo que hemos añadido, la lista volverá a estar vacía. Ahora veremos cómo modificar el principio de la lista en tiempo constante. Empezaremos utilizando unshift(val) para añadir un nodo.

Pseudocode unshift(val)

  1. Crea un nodo nuevo con el valor aceptado por el método
  2. Si la lista está vacía, asigna el nodo nuevo a head y a tail
  3. De lo contrario
    1. Crea una constante para guardar el head original
    2. Asigna el nodo nuevo al head de la lista
    3. El head original pasa a ser el nodo que le sigue al head nuevo
    4. El puntero al nodo anterior al head original apunta al nodo nuevo
  4. Aumenta el tamaño de la lista por 1
  5. Devuelve la lista
unshift(val) {
// crea un nuevo nodo con el valor aceptado por el método
const newNode = new Node(val);
// si la lista está vacía, asigna el nodo nuevo a head y a tail
if (this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
// de lo contrario, crea una constante para guardar el head original
let oldHead = this.head;
// asigna el nodo nuevo al head de la lista
this.head = newNode;
// el head original pasa a ser el nodo que le sigue al head nuevo
newNode.next = oldHead;
// el puntero al nodo anterior al head original apunta al nodo nuevo
oldHead.prev = newNode;
}
// aumenta el tamaño de la lista por 1
this.length++;
// devuelve la lista
return this;
}

Para remover el primer nodo de la lista, utilizaremos shift().

Pseudocode shift()

  1. Si la lista está vacía, devuelve null
  2. Crea una constante para guardar el head original
  3. Si la lista solo tiene un nodo, vacía el head y el tail
  4. Si la lista no está vacía
    1. El head nuevo es el nodo siguiente al head original
    2. Antes del head nuevo, no hay nada
  5. Reduce el tamaño de la lista por 1
  6. Devuelve el nodo removido
shift() {
// si la lista está vacía, devuelve null
if (!this.head) return head;
// crea una constante para guardar el head original
const head = this.head;
// si la lista solo tiene un nodo, vacía el head y el tail
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
// de lo contrario, el head nuevo es el nodo siguiente al head original
this.head = head.next;
// antes del head nuevo, no hay nada
this.head.prev = null;
}
// reduce el tamaño de la lista por 1
this.length--;
// devuelve el nodo removido
return head;
}

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.

| Acción | Big O |
| --------- | ----- |
| Inserción | O(1) |
| Remoción | O(1) |
| Búsqueda | O(n) |

✨ 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.

¿Quieres mejorar tus habilidades de frontend?