Listas enlazadas en JavaScript

En este tutorial vamos a ver qué es una lista enlazada y cómo se crea esta estructura de datos en JavaScript, ya que por ahora y a diferencia de otros lenguajes como Java, este lenguaje no dispone de una implementación para las misma. ¿Por qué querrías saber cómo crear una lista enlazada? Entre otras cosas, además de resultar útil en varias circunstancias, su implementación es una pregunta estrella en muchas entrevistas de trabajo.

Qué es una lista enlazada

Una lista enlazada es un tipo de estructura de datos muy utilizada en el mundo de la programación. En una lista enlazada, cada elemento contiene una referencia al siguiente elemento de la lista.

A diferencia de un array, los elementos no se ordenan secuencialmente uno tras otro en memoria y tampoco contienen un índice que nos permita acceder a cada elemento de la lista individualmente.

Cuando se quiere recorrer una lista enlazada, se suele comenzar por el primer elemento de la lista, al que se le llama head, iterando por cada uno de los elementos hasta llegar a la cola o tail, que se corresponde con el último elemento de la lista. Para hacer referencia a algún elemento de la lista, tendremos que recorrerla desde el principio, ya que carecemos de una referencia.

Cómo crear una lista enlazada en JavaScript

JavaScript no dispone de una implementación para las listas enlazadas, por lo que tendremos que crearla. Para ello crearemos varias clases.

Para empezar, vamos a crear una clase a la que llamaremos Elemento que nos permita representar cada uno de los elementos de la lista:

class Elemento
{
  siguiente = null;
  valor = null;
 
  constructor(value) {
    this.valor = valor;
  }
}

Lo que hemos hecho es crear una clase que contenga el valor de cada elemento de la lista en la propiedad valor. La propiedad siguiente contendrá una referencia al siguiente elemento de la lista.

A continuación vamos a crear la clase que gestionará los elementos de la lista, a la que llamaremos ListaEnlazada. Esta clase contendrá dos propiedades, que serán las propiedades primero y ultimo, que contendrán referencias al primer y al último elemento de la lista respectivamente.

Vamos a definir también el método agregar, que añadirá un elemento a la lista. El método agregar, definido usando una función flecha, creará un nuevo elemento y lo asignará a la referencia siguiente del último elemento la lista, al que hace referencia la propiedad ultimo de la clase ListaEnlazada.

Decir que el primer elemento de la lista, será a su vez el último hasta que agreguemos algún elemento más. A continuación puedes ver el código de la clase ListaEnlazada:

class ListaEnlazada
{
  primero = null;
  ultimo = null;
 
  agregar = (valor) => {
 
    const elemento = new Elemento(valor);
 
    if (!this.primero) {
      this.primero = elemento;
      this.ultimo = elemento;
      return;
    }
 
    this.ultimo.next = item;
    this.ultimo = item;
  }
}

Para agregar elementos, primero tendremos que crear la lista mediante una instancia de la clase ListaEnlazada. A continuación agregamos algunos elementos:

const lista = new ListaEnlazada();
 
lista.agregar('a');
lista.agregar('b');
lista.agregar('c');

Cómo contar los elementos de la lista

Ahora vamos agregar un nuevo método  a la clase ListaEnlazada llamado numElementos que nos devuelva el número de elementos de la lista:

class ListaEnlazada
{
  // Aquí los métodos que ya hemos definido
 
  numElementos = () => {

    let contador = 0;
    let elemento = this.primero;
 
    if (!elemento) return 0;
    else contador = 1;  
 
    while (elemento.siguiente) {
      elemento = elemento.siguiente;
      contador++;
    }
    return contador;
  }
}

Lo que hacemos en el método numElementos es devolver cero si no existe un primer elemento. Si existe, contamos un elemento, y seguidamente recorremos la lista, agregando una unidad a la variable contador por cada nuevo elemento encontrado. Vamos a utilizar el método con un ejemplo:

const lista = new ListaEnlazada();
 
lista.agregar('a');
console.log(lista.numElementos()); // 1
 
lista.agregar('b');
lista.agregar('c');
console.log(lista.numElementos()); // 3

Cómo obtener un elemento de la lista

Vamos a crear un método que nos permita obtener un elemento de la lista a partir del valor del mismo. Para ello agregaremos el método buscar, que recorrerá la lista hasta dar con el elemento cuyo valor coincida con el que estamos buscando:

class ListaEnlazada
{
  //...
 
  buscar = (valor) => {
 
    let contador = 0;
    let elemento = this.primero;
    
    if (!elemento) return null;
 
    while ((elemento = elemento.siguiente)) {
      if (elemento.valor === valor) {
        return elemento;
      }
    }
    return null;
  }
}

Lo que hemos hecho es recorrer la lista hasta encontrar el elemento cuyo valor coincida con el que buscamos. Si no está en la lista, devolvemos null. Vamos a ver cómo utilizar este método:

const lista = new ListaEnlazada();
 
lista.agregar('a');
lista.agregar('b');
lista.agregar('c');
 
const elemento = lista.buscar('b');
console.log(elemento.valor); // b

Cómo insertar elementos en la lista

Ya hemos visto cómo insertar elementos al final de la lista, aunque por ahora no podemos insertarlos en una determinada posición. A continuación vamos a crear un método llamado insertar que agregue un elemento en la posición especificada. El método aceptará un indice y un valor como parámetros:

class ListaEnlazada {
  //...
  insertar = (indice, valor) => {

    if (indice < 0 || indice > this.numElementos()) {
      return;
    }

    const nuevoElemento = new Elemento(valor);
    let elementoActual = this.primero;
    let anterior;

    if (indice === 0) {
      nuevoElemento.siguiente = elementoActual;
      this.primero = nuevoElemento;
      return;
    }
 
    let i = 0;
    while (i++ < indice) {
      elementoAnterior = elementoActual;
      elementoActual = elementoActual.siguiente;
    }
 
    nuevoElemento.siguiente = elementoActual;
    elementoAnterior.siguiente = nuevoElemento;
  }
}

Primero hemos comprobado que el índice sea válido, es decir; el valor del parámetro indice no deberá ser menor que 0 ni mayor que el número de elementos de la lista. Seguidamente creamos un nuevo elemento y lo almacenamos en la variable nuevoElemento.

Si insertamos el nuevo el elemento en la cabeza de la lista, asignamos el elemento que actualmente está de primero en la lista como elemento siguiente del que estamos insertando, y los establecemos como primer elemento de la lista. De lo contrario, recorremos la lista iterando por sus elementos el número de veces indicado por el parámetro indice. Una vez llegamos a la posición deseada, asignamos el elemento que actualmente está en dicha posición como elemento siguiente del que insertamos y, del mismo modo, asignaremos el elemento que insertamos como elemento siguiente del elemento anterior de la lista.

A continuación vamos a ver cómo insertar un elemento:

const lista = new ListaEnlazada();
 
lista.agregar('a');
lista.agregar('b');
lista.agregar('d');
lista.insertar(2, 'c');

const elemento = lista.buscar('c');
console.log(elemento.valor); // c

Crea más tipos de listas

Y con esto ya hemos creado los métodos más comunes que existen en las implementaciones de listas enlazadas de otros lenguajes de programación. También podríamos crear listas doblemente enlazadas, que cuya única diferencia reside en que sus elementos también contienen una referencia al elemento que los precede.

---