Artículo original escrito por Sarah Chima Atuonwu
Artículo original How to Implement a Linked List in JavaScript
Traducido y adaptado por Gibrán Pelayo

Si estás aprendiendo estructura de datos, la lista enlazada es una estructura de datos que deberías conocer. Si no la entiendes del todo o no sabes cómo se implementa en JavaScript, este artículo está aquí para ayudarte.

Aquí hablaremos sobre lo que es una lista enlazada, en qué es diferente de un arreglo, y cómo se implementa en JavaScript. Empecemos.

¿Qué es una lista enlazada?

Una lista enlazada es una estructura de datos lineal similar a un arreglo. Sin embargo, a diferencia de los arreglos, los elementos no son almacenados en una ubicación de la memoria o índice en particular. Más bien, cada elemento es un objeto separado que contiene un puntero/apuntador o enlace al siguiente objeto en esa lista.

Cada elemento (comúnmente llamados nodos) contiene otros dos: el dato almacenado y un enlace al siguiente nodo. El dato puede ser de cualquier tipo válido. Puedes ver esto ilustrado en el diagrama de abajo.

Image of a linked list

El punto de entrada a una lista enlazada es llamado la cabecera. La cabecera es una referencia al primer nodo en la lista enlazada. El último nodo en la lista apunta a nulo. Si una lista está vacía, la cabecera es una referencia nula.

En JavaScript, una lista enlazada se ve así:

const lista = {
    cabecera: {
        valor: 6
        siguiente: {
            valor: 10                                             
            siguiente: {
                valor: 12
                siguiente: {
                    valor: 3
                    siguiente: null	
                    }
                }
            }
        }
    }
};

Una ventaja de las listas enlazadas

  • Los nodos pueden ser fácilmente removidos o agregados a una lista enlazada sin tener que reorganizar la estructura de datos entera. Esta es una ventaja que tiene sobre los arreglos.

Desventajas de las listas enlazadas

  • Las operaciones de búsqueda son lentas en las listas enlazadas. A diferencia de los arreglos, el acceso aleatorio a elementos de datos no está permitido. Se accede a los nodos de manera secuencial empezando desde el primer nodo.  
  • El uso de memoria es mayor que en los arreglos debido al almacenamiento de los punteros/apuntadores.

Tipos de listas enlazadas

Hay tres tipos de listas enlazadas:

  • Listas enlazadas individuales: Cada nodo contiene solo un puntero/apuntador al siguiente nodo. Esto es de lo que hemos estado hablando hasta ahora.
  • Listas doblemente enlazadas: Cada nodo contiene dos punteros/apuntadores; un puntero/apuntador al siguiente nodo, y otro al nodo anterior.
  • Listas circulares enlazadas: Son una variación de la lista enlazada en donde el último nodo apunta al primer nodo o a otro nodo antes de ese, formando así un bucle.

Implementación de un nodo de lista en JavaScript

Como se mencionó antes, un nodo de lista contiene dos elementos, el dato y el puntero/apuntador al siguiente nodo. Podemos implementar un nodo de lista en JavaScript de la siguiente manera: 

class NodoLista {
    constructor(dato) {
        this.dato = dato
        this.siguiente = null                
    }
}

Implementación de una lista enlazada en JavaScript

El código de abajo muestra la implementación de una clase de lista enlazada con un constructor. Nota que si el nodo de cabecera no es pasado, la cabecera se inicializa a nulo. 

class ListaEnlazada {
    constructor(cabecera = null) {
        this.cabecera = cabecera
    }
}

Poniéndolo todo junto

Vamos a crear una lista enlazada con la clase que hemos creado. Primero, creamos dos nodos de lista, nodo1 y nodo2 y un puntero/apuntador del nodo 1 al nodo 2.

let nodo1 = new NodoLista(2)
let nodo2 = new NodoLista(5)
nodo1.siguiente = nodo2

A continuación crearemos una Lista Enlazada con el nodo1.

let lista = new ListaEnlazada(nodo1)

Intentemos acceder a los nodos de la lista que hemos creado. 

console.log(lista.cabecera.siguiente.dato) //devuelve 5

Algunas funciones de listaEnlazada

A continuación, implementaremos cuatro funciones de ayuda para la lista enlazada, los cuales son:

  1. magnitud()
  2. vaciar()
  3. obtenerUltimo()
  4. obtenerPrimero()

1. magnitud()

Esta función devuelve el número de nodos presentes en la lista enlazada. 

magnitud() {
    let contador = 0; 
    let nodo = this.cabecera;
    while (nodo) {
        contador++;
        nodo = nodo.siguiente
    }
    return contador;
}

2. vaciar()

Esta función vacía la lista. 

vaciar() {
    this.cabecera = null;
}

3. obtenerUltimo()

Esta función devuelve el último nodo de la lista enlazada.

obtenerUltimo() {
    let ultimoNodo = this.cabecera;
    if (ultimoNodo) {
        while (ultimoNodo.siguiente) {
            ultimoNodo = ultimoNodo.siguiente
        }
    }
    return ultimoNodo;
}

4. obtenerPrimero()

Esta función devuelve el primer nodo de la lista enlazada.

obtenerPrimero() {
    return this.cabecera;
}

Resumen

En ese artículo, discutimos qué es una lista enlazada y cómo se puede implementar en JavaScript. También discutimos los diferentes tipos de listas enlazadas, así como sus ventajas y desventajas en general.

Espero que hayas disfrutado esta lectura.

¿Quieres ser notificado cuando publique un nuevo artículo? Da clic aquí.