Como implementar uma estrutura de dados da lista vinculada em JavaScript?

JavaScript é uma linguagem de programação da web usada para tornar nossas páginas da web e aplicativos da web dinâmicos e interativos, dando -lhes a capacidade de pensar e agir. Como qualquer outra linguagem de programação, o JavaScript nos oferece matrizes, que são uma coleção de elementos diferentes armazenados em uma única variável. A limitação de uma matriz é que ela é armazenada consecutivamente em uma memória específica em nosso sistema, portanto, para resolver esse problema, usamos uma lista vinculada.

Lista vinculada

As listas vinculadas são como matrizes, exceto que em uma lista vinculada, os itens não são salvos em um local ou índice de memória específico e cada elemento é um objeto independente separado que está conectado ao próximo elemento, com um ponteiro ou link para esse elemento.

Cada lista vinculada contém uma cabeça (primeiro nó), comprimento (tamanho da lista vinculada) e uma propriedade de cauda (último nó), e cada elemento em uma lista vinculado é chamado de nó e todo nó tem um valor armazenado nele e o link para o próximo nó. Se o nó atual for a cauda, ​​o link será nulo que não está apontando para nenhum outro nó. A lista vinculada não contém índices, diferentemente das matrizes que possuem índices e.g 0,1,2 ... e assim por diante.

As listas vinculadas no JavaScript podem ser demonstradas da seguinte forma:

// Lista vinculada
const LinkedList =
// Todo nó tem um valor e ponteiro
// O primeiro ponteiro é o cabeçalho
cabeça:
Valor: 6
próximo:
Valor: 10
próximo:
Valor: 12
próximo:
Valor: 3
Próximo: NULL





;

A vantagem da lista vinculada é que os elementos (nós) são facilmente adicionados e removidos da lista vinculada sem ajustar toda a lista vinculada. A desvantagem de uma lista vinculada é que ela precisa de mais memória para armazenamento, pois agora temos um ponteiro extra que estamos armazenando junto com o valor do elemento.

As listas vinculadas são de três tipos que são descritos abaixo:

• A lista individual vinculada tem apenas um ponteiro apontando para o nó ao lado dele.
• O duplamente vinculado é baseado em dois pontos em que o primeiro aponta para o nó que está por trás dele e o segundo aponta para o nó ao lado.
• A lista ligada circular cuja cauda contém um ponteiro para a cabeça e, portanto, forma um ciclo.

Implementação da lista vinculada

Vamos primeiro criar um nó que tenha duas propriedades um valor e um ponteiro para o qual criaremos uma classe com o nome de ListNode Isso tem essas duas propriedades:

classe listNode
construtor (valor)
esse.valor = valor
esse.próximo = nulo

Agora que sabemos como criar um nó, vamos criar uma lista vinculada em que o valor padrão da cabeça será nulo:

classe LinkedList
construtor (cabeça = nulo)
esse.cabeça = cabeça

Vamos agora inicializar a lista vinculada com dois nós e adicione um ponteiro da cabeça ou nó 1 ao segundo nó:

var node1 = new ListNode (3);
var node2 = new ListNode (4);
node1.próximo = node2;

A próxima etapa é inicializar a lista vinculada com o Node1 da seguinte maneira:

var lista = new LinkedList (node1);

O código inteiro é fornecido abaixo com o console registrando o valor do node2:

// criando um nó
classe listNode
construtor (valor)
// Valor inicial do construtor e o próximo ponteiro
esse.valor = valor
esse.próximo = nulo


classe LinkedList
// construtor de lista vinculada
construtor (cabeça = nulo)
esse.cabeça = cabeça


// Inicializando nós criados
var node1 = new ListNode (3);
var node2 = new ListNode (4);
node1.próximo = node2;
// Inicializando a lista vinculada
var lista = new LinkedList (node1);
// mostrando a saída do segundo nó
console.log (lista.cabeça.próximo.valor) // 4

Métodos de lista vinculados

Agora que terminamos a implementação da lista vinculada, vamos reproduzir ou manipular a lista vinculada implementando mais métodos para fazer uso das listas vinculadas (Métodos Helper):

O primeiro método auxiliar que definiremos é o tamanho() Método na classe LinkedList que retornará a duração da lista vinculada:

tamanho = () =>
deixe count = 0;
Deixe o nó = este.cabeça;
// loop para iterar a lista vinculada
while (nó)
contagem ++;
nó = nó.próximo

contagem de retorno;

Neste código primeiro, estamos declarando uma variável dummy contar armazenando 0 nele e depois armazenando o ponteiro da cabeça no nó variável. Em seguida, declaramos um loop que itera sobre a lista vinculada e incrementará o contar variável.

O próximo método auxiliar será o getfirst () Método em que o ponteiro da cabeça será devolvido:

getfirst = () =>
devolver isso.cabeça.valor;

Também podemos obter o último nó da lista vinculada da seguinte maneira:

getLast = () =>
Deixe LastNode = este.cabeça;
if (lastNode)
while (lastNode.próximo)
lastNode = lastNode.próximo


Retorne o LastNode.valor

O código inteiro agora é fornecido abaixo, mostrando a saída do segundo valor do nó, o tamanho da lista vinculada, o valor do primeiro nó e o último valor do nó na mesma ordem:

// criando um nó
classe listNode
construtor (valor)
esse.valor = valor
esse.próximo = nulo


// Criando lista vinculada
classe LinkedList
construtor (cabeça = nulo)
esse.cabeça = cabeça

tamanho = () =>
deixe count = 0;
Deixe o nó = este.cabeça;
// loop para iterar a lista vinculada
while (nó)
contagem ++;
nó = nó.próximo

contagem de retorno;

getfirst = () =>
devolver isso.cabeça.valor;

getLast = () =>
Deixe LastNode = este.cabeça;
if (lastNode)
while (lastNode.próximo)
lastNode = lastNode.próximo


Retorne o LastNode.valor


// Inicializando nós criados
var node1 = new ListNode (3);
var node2 = new ListNode (4);
node1.próximo = node2;
// Inicializando a lista vinculada
var lista = new LinkedList (node1);
// mostrando a saída do segundo nó
console.log ("Segundo Nó Valor:", Lista.cabeça.próximo.valor) // 4
// mostrando o tamanho da lista vinculada
console.log ("Tamanho da lista vinculada:", lista.tamanho());
// mostrando o primeiro valor do nó
console.log ("primeiro nó valor:", lista.getfirst ());
// mostrando o último valor do nó
console.log ("Último valor do nó:", lista.Obtenha o último());

Conclusão

Após as matrizes, uma lista vinculada é a segunda estrutura de dados mais usada em qualquer linguagem de programação. Uma lista vinculada é como uma matriz que armazena uma coleção de elementos diferentes, com a diferença que todos os elementos (nó) de uma lista vinculada são um objeto que contém um valor do elemento e um ponteiro apontando para o próximo nó, portanto, vinculando todos os elementos e A segunda diferença é que os itens não são salvos em um local de memória específico em uma lista vinculada.

Neste post, vimos o que são as listas vinculadas, as vantagens e desvantagens das listas vinculadas, os tipos de listas vinculadas e como implementar a estrutura de dados da lista vinculada no JavaScript.