Cómo implementar una lista vinculada en JavaScript

Si está aprendiendo sobre estructuras de datos, una lista enlazada es una estructura de datos que debe conocer. Si realmente no lo entiende o cómo se implementa en JavaScript, este artículo está aquí para ayudarlo.

En este artículo, analizaremos qué es una lista vinculada, en qué se diferencia de una matriz y cómo implementarla en JavaScript. Empecemos.

¿Qué es una lista vinculada?

Una lista vinculada es una estructura de datos lineal similar a una matriz. Sin embargo, a diferencia de las matrices, los elementos no se almacenan en una ubicación o índice de memoria en particular. Más bien, cada elemento es un objeto separado que contiene un puntero o un enlace al siguiente objeto de esa lista.

Cada elemento (comúnmente llamado nodos) contiene dos elementos: los datos almacenados y un enlace al siguiente nodo. Los datos pueden ser de cualquier tipo de datos válido. Puede ver esto ilustrado en el diagrama a continuación.

Imagen de una lista vinculada

El punto de entrada a una lista vinculada se llama cabeza. El encabezado es una referencia al primer nodo de la lista vinculada. El último nodo de la lista apunta a nulo. Si una lista está vacía, el encabezado es una referencia nula.

En JavaScript, una lista vinculada se ve así:

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

Una ventaja de las listas vinculadas

  • Los nodos se pueden eliminar o agregar fácilmente de una lista vinculada sin reorganizar toda la estructura de datos. Esta es una ventaja que tiene sobre las matrices.

Desventajas de las listas vinculadas

  • Las operaciones de búsqueda son lentas en listas enlazadas. A diferencia de las matrices, no se permite el acceso aleatorio de elementos de datos. Se accede a los nodos de forma secuencial a partir del primer nodo.
  • Utiliza más memoria que las matrices debido al almacenamiento de los punteros.

Tipos de listas vinculadas

Hay tres tipos de listas vinculadas:

  • Listas vinculadas individualmente : cada nodo contiene solo un puntero al siguiente nodo. De esto es de lo que hemos estado hablando hasta ahora.
  • Listas doblemente enlazadas : cada nodo contiene dos punteros, un puntero al siguiente nodo y un puntero al nodo anterior.
  • Listas enlazadas circulares : las listas enlazadas circulares son una variación de una lista enlazada en la que el último nodo apunta al primer nodo o cualquier otro nodo anterior a él, formando así un bucle.

Implementación de un nodo de lista en JavaScript

Como se indicó anteriormente, un nodo de lista contiene dos elementos: los datos y el puntero al siguiente nodo. Podemos implementar un nodo de lista en JavaScript de la siguiente manera:

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

Implementación de una lista vinculada en JavaScript

El siguiente código muestra la implementación de una clase de lista vinculada con un constructor. Observe que si no se pasa el nodo principal, el encabezado se inicializa en nulo.

class LinkedList { constructor(head = null) { this.head = head } }

Poniendolo todo junto

Creemos una lista vinculada con la clase que acabamos de crear. En primer lugar, creamos dos nodos de la lista, node1y node2y un puntero del nodo 1 al nodo 2.

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

A continuación, crearemos una lista vinculada con node1.

let list = new LinkedList(node1)

Intentemos acceder a los nodos de la lista que acabamos de crear.

console.log(list.head.next.data) //returns 5

Algunos métodos LinkedList

A continuación, implementaremos cuatro métodos auxiliares para la lista vinculada. Son:

  1. Talla()
  2. claro()
  3. obtener ultimo()
  4. getFirst ()

1. tamaño ()

Este método devuelve el número de nodos presentes en la lista vinculada.

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; } 

2. claro ()

Este método vacía la lista.

clear() { this.head = null; }

3. getLast ()

Este método devuelve el último nodo de la lista vinculada.

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst ()

Este método devuelve el primer nodo de la lista vinculada.

getFirst() { return this.head; }

Resumen

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

Espero que hayas disfrutado leyéndolo.

¿Quieres recibir una notificación cuando publique un artículo nuevo? Haga clic aquí.