Implementando uma lista vinculada em JavaScript

Se você está aprendendo estruturas de dados, uma lista vinculada é uma estrutura de dados que você deve conhecer. Se você realmente não entende ou como é implementado em JavaScript, este artigo está aqui para ajudá-lo. Neste artigo, discutiremos o que é uma lista vinculada, como ela é diferente de uma matriz e como implementar em JavaScript. Vamos começar.

O que é uma lista vinculada?

Uma lista vinculada é uma estrutura de dados linear semelhante a uma matriz. No entanto, diferentemente das matrizes, os elementos não são armazenados em um local ou índice de memória específico. Em vez disso, cada elemento é um objeto separado que contém um ponteiro ou um link para o próximo objeto nessa lista.

Cada elemento (geralmente chamado de nós) contém dois itens: os dados armazenados e um link para o próximo nó. Os dados podem ser de qualquer tipo de dados válido. Você pode ver isso ilustrado no diagrama abaixo.

O ponto de entrada para uma lista vinculada é chamado de cabeça. A cabeça é uma referência ao primeiro nó na lista vinculada. O último nó da lista aponta para nulo. Se uma lista estiver vazia, o cabeçalho será uma referência nula.

Em JavaScript, uma lista vinculada fica assim:

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

Uma vantagem das Listas Vinculadas

• Os nós podem ser facilmente removidos ou adicionados de uma lista vinculada sem reorganizar toda a estrutura de dados. Essa é uma vantagem que possui sobre matrizes.

Desvantagens de listas vinculadas

• As operações de pesquisa são lentas nas listas vinculadas. Diferentemente das matrizes, o acesso aleatório dos elementos de dados não é permitido. Os nós são acessados ​​sequencialmente a partir do primeiro nó.
• Ele usa mais memória do que matrizes devido ao armazenamento dos ponteiros.

Tipos de listas vinculadas

Existem três tipos de listas vinculadas:

• Listas vinculadas individualmente : Cada nó contém apenas um ponteiro para o próximo nó. É disso que falamos até agora.
• Listas duplamente vinculadas : Cada nó contém dois ponteiros, um ponteiro para o próximo nó e um ponteiro para o nó anterior.
• Listas vinculadas circulares : Lista vinculada circular é uma variação de uma lista vinculada na qual o último nó aponta para o primeiro nó ou qualquer outro nó antes de formar um loop.

Implementando um nó da lista em JavaScript

Como afirmado anteriormente, um nó da lista contém dois itens: os dados e o ponteiro para o próximo nó. Podemos implementar um nó de lista em JavaScript da seguinte maneira:

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

Implementando uma lista vinculada em JavaScript

O código abaixo mostra a implementação de uma classe de lista vinculada com um construtor. Observe que, se o nó principal não for passado, ele será inicializado como nulo.

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

Juntando tudo

Vamos criar uma lista vinculada com a classe que acabamos de criar. Primeiro, criamos dois nós da lista, node1 e node2 e um ponteiro do nó 1 para o nó 2.

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

Em seguida, criaremos uma lista vinculada com o node1.

let list = new LinkedList(node1)

Vamos tentar acessar os nós na lista que acabamos de criar.

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

Alguns métodos LinkedList

Em seguida, implementaremos quatro métodos auxiliares para a lista vinculada. Eles são:

1. Tamanho()
2. Claro()
3. Obtenha o último()
4. getFirst ()

1. tamanho ()

Este método retorna o número de nós presentes na lista vinculada.

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

2. claro ()

Este método esvazia a lista.

clear() {    this.head = null;}

3. getLast ()

Este método retorna o último nó da lista vinculada.

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

4. getFirst ()

Este método retorna o primeiro nó da lista vinculada.

getFirst() {    return this.head;}

Sumário

Neste artigo, discutimos o que é uma lista vinculada e como ela pode ser implementada em JavaScript. Também discutimos os diferentes tipos de listas vinculadas e suas vantagens e desvantagens.

Espero que tenham gostado de ler.

Deseja ser notificado quando eu publicar um novo artigo? Clique aqui.