En 2009, me reté a mí mismo a escribir una entrada de blog por semana durante todo el año. Había leído que la mejor manera de ganar más tráfico en un blog era publicar de forma constante. Un post por semana parecía un objetivo realista debido a todas las ideas de artículos que tenía, pero resultó que me faltaban 52 ideas. Rebusqué en algunos capítulos a medio escribir de lo que acabaría siendo JavaScript profesional y encontré mucho material sobre temas clásicos de la informática, como las estructuras de datos y los algoritmos. Tomé ese material y lo convertí en varios posts en 2009 y (y algunos en 2012), y recibí muchos comentarios positivos sobre ellos.

Ahora, en el décimo aniversario de esos posts, he decidido actualizar, volver a publicar y ampliarlos con JavaScript en 2019. Ha sido interesante ver qué ha cambiado y qué no, y espero que los disfrutéis.

¿Qué es una lista enlazada?

Una lista enlazada es una estructura de datos que almacena múltiples valores de forma lineal. Cada valor de una lista enlazada está contenido en su propio nodo, un objeto que contiene los datos junto con un enlace al siguiente nodo de la lista. El enlace es un puntero a otro objeto nodo o null si no hay un nodo siguiente. Si cada nodo tiene sólo un puntero a otro nodo (más frecuentemente llamado next) entonces la lista se considera una lista enlazada simple (o simplemente lista enlazada) mientras que si cada nodo tiene dos enlaces (normalmente previous y next) entonces se considera una lista doblemente enlazada. En este post, me centraré en las listas enlazadas simples.

¿Por qué usar una lista enlazada?

El principal beneficio de las listas enlazadas es que pueden contener un número arbitrario de valores mientras usan sólo la cantidad de memoria necesaria para esos valores. Preservar la memoria era muy importante en los ordenadores más antiguos donde la memoria era escasa. En aquella época, un array incorporado en C requería que se especificara cuántos elementos podía contener el array y el programa reservaba esa cantidad de memoria. Reservar esa memoria significaba que no podía ser utilizada por el resto del programa o por cualquier otro programa que se ejecutara al mismo tiempo, incluso si la memoria nunca se llenaba. En las máquinas con poca memoria, se podía agotar fácilmente la memoria disponible utilizando arrays. Las listas enlazadas se crearon para solucionar este problema.

Aunque originalmente estaban pensadas para una mejor gestión de la memoria, las listas enlazadas también se hicieron populares cuando los desarrolladores no sabían cuántos elementos contendría finalmente un array. Era mucho más fácil utilizar una lista enlazada y añadir valores según fuera necesario que adivinar con precisión el número máximo de valores que podría contener una matriz. Como tal, las listas enlazadas se utilizan a menudo como la base de las estructuras de datos incorporadas en varios lenguajes de programación.

El tipo incorporado de JavaScript Array no se implementa como una lista enlazada, aunque su tamaño es dinámico y siempre es la mejor opción para empezar. Es posible que pase toda su carrera sin necesidad de utilizar una lista enlazada en JavaScript, pero las listas enlazadas siguen siendo una buena manera de aprender a crear sus propias estructuras de datos.

El diseño de una lista enlazada

La parte más importante de una lista enlazada es su estructura de nodos. Cada nodo debe contener algún dato y un puntero al siguiente nodo de la lista. He aquí una representación sencilla en JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; }}

En la clase LinkedListNode, la propiedad data contiene el valor que debe almacenar el elemento de la lista enlazada y la propiedad next es un puntero al siguiente elemento de la lista. La propiedad next comienza como null porque aún no se conoce el siguiente nodo. A continuación, puede crear una lista enlazada utilizando la clase LinkedListNode de la siguiente manera:

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

El primer nodo de una lista enlazada se llama normalmente la cabeza, por lo que el identificador head en este ejemplo representa el primer nodo. El segundo nodo se crea y se asigna a head.next para crear una lista con dos elementos. Se añade un tercer nodo asignándolo a head.next.next, que es el puntero next del segundo nodo de la lista. El puntero next del tercer nodo de la lista sigue siendo null. La siguiente imagen muestra la estructura de datos resultante.

La estructura de una lista enlazada permite recorrer todos los datos siguiendo el puntero next de cada nodo. He aquí un ejemplo sencillo de cómo recorrer una lista enlazada e imprimir cada valor en la consola:

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

Este código utiliza la variable current como puntero que se mueve por la lista enlazada. La variable current se inicializa a la cabeza de la lista y el bucle while continúa hasta que current sea null. Dentro del bucle, se imprime el valor almacenado en el nodo current y luego se sigue el puntero next hasta el siguiente nodo.

La mayoría de las operaciones de listas enlazadas utilizan este algoritmo de recorrido o algo similar, por lo que entender este algoritmo es importante para entender las listas enlazadas en general.

La clase LinkedList

Si estuvieras escribiendo una lista enlazada en C, podrías detenerte en este punto y considerar tu tarea completa (aunque usarías una estructura en lugar de una clase para representar cada nodo). Sin embargo, en lenguajes orientados a objetos como JavaScript, es más habitual crear una clase para encapsular esta funcionalidad. He aquí un ejemplo sencillo:

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

La clase LinkedList representa una lista enlazada y contendrá métodos para interactuar con los datos que contiene. La única propiedad es una propiedad símbolo llamada head que contendrá un puntero al primer nodo de la lista. Se utiliza una propiedad símbolo en lugar de una propiedad cadena para dejar claro que esta propiedad no está pensada para ser modificada fuera de la clase.

Añadir nuevos datos a la lista

Añadir un elemento a una lista enlazada requiere recorrer la estructura para encontrar la ubicación correcta, crear un nuevo nodo e insertarlo en su lugar. El único caso especial es cuando la lista está vacía, en cuyo caso simplemente se crea un nuevo nodo y se asigna a head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

El método add() acepta un único argumento, cualquier dato, y lo añade al final de la lista. Si la lista está vacía (this es null) entonces se asigna this igual al nuevo nodo. Si la lista no está vacía, entonces necesitas recorrer la lista ya existente para encontrar el último nodo. El recorrido ocurre en un bucle while que comienza en this y sigue los enlaces next de cada nodo hasta encontrar el último nodo. El último nodo tiene una propiedad next igual a null, por lo que es importante detener el recorrido en ese punto y no cuando current es null (como en la sección anterior). A continuación, puede asignar el nuevo nodo a esa propiedad next para añadir los datos en la lista.

La complejidad del método add() es O(n) porque debe recorrer toda la lista para encontrar la ubicación para insertar un nuevo nodo. Puedes reducir esta complejidad a O(1) rastreando el final de la lista (normalmente llamado cola) además de la cabeza, lo que te permite insertar inmediatamente un nuevo nodo en la posición correcta.

Recuperar datos de la lista

Las listas enlazadas no permiten el acceso aleatorio a su contenido, pero aún puedes recuperar datos en cualquier posición dada recorriendo la lista y devolviendo los datos. Para ello, añadirás un método get() que acepta un índice basado en cero de los datos a recuperar, así:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

El método get() primero comprueba que index es un valor positivo, de lo contrario devuelve undefined. La variable i se utiliza para llevar la cuenta de la profundidad del recorrido en la lista. El bucle en sí es el mismo recorrido básico que has visto antes con la condición añadida de que el bucle debe salir cuando i sea igual a index. Esto significa que hay dos condiciones bajo las cuales el bucle puede salir:

1. current es null, lo que significa que la lista es más corta que index.
2. i es igual a index, lo que significa que current es el nodo en la posición index.

Si current es null entonces se devuelve undefined y en caso contrario se devuelve current.data. Esta comprobación asegura que get() nunca lanzará un error por un index que no se encuentre en la lista (aunque se podría decidir lanzar un error en lugar de devolver undefined).

La complejidad del método get() va desde O(1) cuando se elimina el primer nodo (no es necesario recorrerlo) hasta O(n) cuando se elimina el último nodo (se requiere recorrer toda la lista). Es difícil reducir la complejidad porque siempre se requiere una búsqueda para identificar el valor correcto a devolver.

Eliminar datos de una lista enlazada

Eliminar datos de una lista enlazada es un poco complicado porque hay que asegurarse de que todos los punteros next siguen siendo válidos después de eliminar un nodo. Por ejemplo, si quieres eliminar el segundo nodo de una lista de tres nodos, tendrás que asegurarte de que la propiedad next del primer nodo apunta ahora al tercer nodo en lugar de al segundo. Al omitir el segundo nodo de esta manera, se elimina efectivamente de la lista.

La operación de eliminación es en realidad dos operaciones:

1. Encontrar el índice especificado (el mismo algoritmo que en get())
2. Eliminar el nodo en ese índice

Encontrar el índice especificado es lo mismo que en el método get(), pero en este bucle también hay que rastrear el nodo que viene antes de current porque habrá que modificar el puntero next del nodo anterior.

También hay cuatro casos especiales a considerar:

1. La lista está vacía (no es posible recorrerla)
2. El índice es menor que cero
3. El índice es mayor que el número de elementos de la lista
4. El índice es cero (eliminando la cabeza)

En los tres primeros casos, la operación de eliminación no puede completarse, por lo que tiene sentido lanzar un error; el cuarto caso especial requiere reescribir la propiedad this. Este es el aspecto de la implementación de un método remove():

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

El método remove() comprueba primero dos casos especiales, una lista vacía (this es null) y un index que es menor que cero. Se lanza un error en ambos casos.

El siguiente caso especial es cuando index es 0, lo que significa que se está eliminando la cabeza de la lista. La nueva cabeza de lista debe ser el segundo nodo de la lista, por lo que puede establecer this igual a this.next. No importa si sólo hay un nodo en la lista porque this terminaría siendo igual a null, lo que significa que la lista está vacía después de la eliminación. La única pega es almacenar los datos de la cabeza original en una variable local, data, para que pueda ser devuelta.

Con tres de los cuatro casos especiales resueltos, ahora se puede proceder con un recorrido similar al que se encuentra en el método get(). Como se mencionó anteriormente, este bucle es ligeramente diferente en que la variable previous se utiliza para realizar un seguimiento del nodo que aparece justo antes de current, ya que esa información es necesaria para eliminar propiamente un nodo. De manera similar a get(), cuando el bucle sale current puede ser null, indicando que el índice no fue encontrado. Si esto sucede, se lanza un error, de lo contrario, previous.next se establece en current.next, eliminando efectivamente current de la lista. Los datos almacenados en current se devuelven como último paso.

La complejidad del método remove() es la misma que la de get() y oscila entre O(1) cuando se elimina el primer nodo y O(n) cuando se elimina el último nodo.

Hacer la lista iterable

Para poder utilizar el bucle de JavaScript for-of y la desestructuración de arrays, las colecciones de datos deben ser iterables. Las colecciones incorporadas en JavaScript como Array y Set son iterables por defecto, y puedes hacer tus propias clases iterables especificando un método generador Symbol.iterator en la clase. Yo prefiero implementar primero un método generador values() (para que coincida con el método que se encuentra en las clases de colección incorporadas) y luego hacer que Symbol.iterator llame a values() directamente.

El método values() sólo necesita hacer un recorrido básico de la lista y yield los datos que contiene cada nodo:

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

El método values() está marcado con un asterisco (*) para indicar que es un método generador. El método recorre la lista, utilizando yield para devolver cada dato que encuentra. (Observe que el método Symbol.iterator no está marcado como generador porque devuelve un iterador del método generador values().)

Usando la clase

Una vez completada, puedes usar la implementación de la lista enlazada así:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

Esta implementación básica de una lista enlazada puede completarse con una propiedad size para contar el número de nodos de la lista, y otros métodos conocidos como indexOf(). El código fuente completo está disponible en GitHub en mi proyecto Computer Science in JavaScript.

Conclusión

Las listas enlazadas no son algo que probablemente utilices todos los días, pero son una estructura de datos fundamental en la informática. El concepto de utilizar nodos que apuntan unos a otros se utiliza en muchas otras estructuras de datos están incorporados en muchos lenguajes de programación de alto nivel. Una buena comprensión de cómo funcionan las listas enlazadas es importante para una buena comprensión general de cómo crear y utilizar otras estructuras de datos.

Para la programación en JavaScript, casi siempre es mejor utilizar las clases de colección incorporadas como Array en lugar de crear las propias. Las clases de colección incorporadas ya han sido optimizadas para su uso en producción y están bien soportadas en todos los entornos de ejecución.