Implementando uma lista vinculada em JavaScript

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.