Cómo implementar una estructura de datos de lista vinculada en JavaScript?

JavaScript es un lenguaje de programación web que se utiliza para que nuestras páginas web y aplicaciones web sean dinámicas e interactivas al darles la capacidad de pensar y actuar. Como cualquier otro lenguaje de programación, JavaScript nos ofrece matrices que son una colección de diferentes elementos almacenados en una sola variable. La limitación de una matriz es que se almacena consecutivamente en una memoria particular en nuestro sistema, por lo tanto, para resolver este problema, utilizamos una lista vinculada.

Lista enlazada

Las listas vinculadas son como matrices, excepto que en una lista vinculada, los elementos no se guardan en una ubicación o índice de memoria específico y cada elemento es un objeto independiente separado que está conectado al siguiente elemento al tener un puntero o enlace a ese elemento.

Cada lista vinculada contiene un cabezal (primer nodo), longitud (tamaño de la lista vinculada) y una propiedad de cola (último nodo), y cada elemento en una lista vinculada se llama nodo y cada nodo tiene un valor almacenado en ella y el enlace al siguiente nodo. Si el nodo actual es la cola, el enlace será nulo que no apunta a ningún otro nodo. La lista vinculada no contiene índices a diferencia de matrices que tienen índices e.g 0,1,2 ... y así sucesivamente.

Las listas vinculadas en JavaScript se pueden demostrar de la siguiente manera:

// Lista enlazada
const LinkedList =
// Cada nodo tiene un valor y un puntero
// El primer puntero es el encabezado
cabeza:
Valor: 6
próximo:
Valor: 10
próximo:
Valor: 12
próximo:
Valor: 3
Siguiente: NULL





;

La ventaja de la lista vinculada es que los elementos (nodos) se agregan y eliminan fácilmente de la lista vinculada sin ajustar toda la lista vinculada. La desventaja de una lista vinculada es que necesita más memoria para el almacenamiento, ya que ahora tenemos un puntero adicional que estamos almacenando junto con el valor del elemento.

Las listas vinculadas son de tres tipos que se describen a continuación:

• La lista vinculada individualmente tiene solo un puntero que apunta al nodo al lado.
• El doblemente vinculado se basa en dos puntos en los que el primero apunta al nodo que está detrás de él y el segundo apunta al nodo al lado.
• La lista circular vinculada cuya cola contiene un puntero a la cabeza y, por lo tanto, forma un ciclo.

Implementación de la lista vinculada

Primero creemos un nodo que tenga dos propiedades un valor y un puntero para el cual crearemos una clase con el nombre de Listnode que tiene estas dos propiedades:

class ListNode
constructor (valor)
este.valor = valor
este.Siguiente = NULL

Ahora que sabemos cómo crear un nodo, creemos una lista vinculada donde el valor predeterminado del cabezal será nulo:

clase LinkedList
constructor (head = null)
este.cabeza = cabeza

Ahora inicializemos la lista vinculada con dos nodos y agregemos un puntero desde el cabezal o el nodo 1 al segundo nodo:

var nodo1 = new ListNode (3);
var nodo2 = new ListNode (4);
nodo1.next = node2;

El siguiente paso es inicializar la lista vinculada con Node1 de la siguiente manera:

var list = new LinkedList (node1);

Todo el código se proporciona a continuación con registro de consola el valor nodo2:

// Creación de nodo
class ListNode
constructor (valor)
// Valor de inicialización del constructor y el siguiente puntero
este.valor = valor
este.Siguiente = NULL


clase LinkedList
// Constructor de lista vinculada
constructor (head = null)
este.cabeza = cabeza


// Inicialización de nodos creados
var nodo1 = new ListNode (3);
var nodo2 = new ListNode (4);
nodo1.next = node2;
// Inicialización de la lista vinculada
var list = new LinkedList (node1);
// mostrando la salida del segundo nodo
consola.Registro (lista.cabeza.próximo.valor) // 4

Métodos de la lista vinculada

Ahora que hemos terminado con la implementación de la lista vinculada, jugemos o manipulemos la lista vinculada mediante la implementación de más métodos para utilizar las listas vinculadas (métodos auxiliares):

El primer método ayudante que definiremos es el tamaño() Método en la clase Lista enlazada que devolverá la longitud de la lista vinculada:

size = () =>
Dejar contar = 0;
Deje que nodo = esto.cabeza;
// bucle para iterar sobre la lista vinculada
while (nodo)
contar ++;
nodo = nodo.próximo

recuento de retorno;

Primero en este código, estamos declarando una variable ficticia contar almacenar 0 en él y luego almacenar el puntero de la cabeza en el nodo variable. Luego declaramos un bucle que iterará sobre la lista vinculada e incrementará el contar variable.

El próximo método auxiliar será el getFirst () Método donde se devolverá el puntero de la cabeza:

getFirst = () =>
devolver esto.cabeza.valor;

También podemos obtener el último nodo de la lista vinculada de la siguiente manera:

getLast = () =>
Deja que LastNode = esto.cabeza;
if (lastNode)
Mientras (LastNode.próximo)
LastNode = LastNode.próximo


Return LastNode.valor

El código completo ahora se proporciona a continuación al mostrar la salida del segundo valor del nodo, el tamaño de la lista vinculada, el primer valor del nodo y el último valor del nodo en el mismo orden:

// Creación de nodo
class ListNode
constructor (valor)
este.valor = valor
este.Siguiente = NULL


// Creación de la lista vinculada
clase LinkedList
constructor (head = null)
este.cabeza = cabeza

size = () =>
Dejar contar = 0;
Deje que nodo = esto.cabeza;
// bucle para iterar sobre la lista vinculada
while (nodo)
contar ++;
nodo = nodo.próximo

recuento de retorno;

getFirst = () =>
devolver esto.cabeza.valor;

getLast = () =>
Deja que LastNode = esto.cabeza;
if (lastNode)
Mientras (LastNode.próximo)
LastNode = LastNode.próximo


Return LastNode.valor


// Inicialización de nodos creados
var nodo1 = new ListNode (3);
var nodo2 = new ListNode (4);
nodo1.next = node2;
// Inicialización de la lista vinculada
var list = new LinkedList (node1);
// mostrando la salida del segundo nodo
consola.log ("Valor de segundo nodo:", Lista.cabeza.próximo.valor) // 4
// Mostrando el tamaño de la lista vinculada
consola.Log ("Tamaño de la lista vinculada:", Lista.tamaño());
// Mostrando el valor del primer nodo
consola.Log ("Primer valor de nodo:", lista.getFirst ());
// mostrando el último valor de nodo
consola.Log ("Último valor del nodo:", lista.obtener ultimo());

Conclusión

Después de las matrices, una lista vinculada es la segunda estructura de datos más utilizada en cualquier lenguaje de programación. Una lista vinculada es como una matriz que almacena una colección de diferentes elementos con la diferencia es que cada elemento (nodo) de una lista vinculada es un objeto que contiene un valor del elemento y un puntero que apunta al siguiente nodo, vinculando cada elemento y La segunda diferencia es que los elementos no se guardan en una ubicación de memoria específica en una lista vinculada.

En esta publicación, vimos qué listas vinculadas son, las ventajas y desventajas de las listas vinculadas, los tipos de listas vinculadas y cómo implementar la estructura de datos de listas vinculadas en JavaScript.