Artigo original: How to Implement a Linked List in JavaScript

Se você está aprendendo estruturas de dados, uma lista vinculada é uma estrutura de dados que você deve conhecer. Se você realmente não a entende ou como ela é implementada em JavaScript, este artigo está aqui para ajudar você.

Neste artigo, discutiremos o que é uma lista vinculada, como ela é diferente de um array e como implementá-la em JavaScript. Vamos começar.

O que é uma lista vinculada?


Uma lista vinculada é uma estrutura de dados linear semelhante a um array. No entanto, ao contrário dos arrays, os elementos não são armazenados em um local da memória ou índice. Em vez disso, cada elemento é um objeto separado, que contém um ponteiro ou um link para o próximo objeto dessa lista.

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

Group_14_5_bvpwu0

O ponto de entrada para uma lista vinculada é chamado de head (cabeça/cabeçalho). Head é uma referência ao primeiro nó na lista vinculada. O último nó da lista aponta para null. Se a lista estiver vazia, head é uma referência nula.

Em JavaScript, uma lista vinculada pode ter a seguinte aparência: 

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 de ou adicionados a uma lista vinculada sem reorganizar toda a estrutura de dados. Esta é uma vantagem que elas tem sobre os arrays.

Desvantagens das listas vinculadas

As operações de pesquisa são lentas em listas vinculadas. Ao contrário dos arrays, o acesso aleatório aos dados dos elementos não é permitido. Os nós são acessados sequencialmente a partir do primeiro nó.

Elas também usam mais memória do que os arrays por causa do 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 : A lista vinculada circular é uma variação de uma lista vinculada na qual o último nó aponta para o primeiro nó ou qualquer outro nó anterior, formando um laço.

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) //retorna 5

Alguns métodos das listas vinculadas

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

  1. size()
  2. clear()
  3. getLast()
  4. getFirst()

1. size() (ou tamanho)

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

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

2. clear() (ou limpar)

Este método esvazia a lista.

clear() {
    this.head = null;
}

3. getLast() (ou obter o último)

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() (ou obter o primeiro)

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 a autora publicar um novo artigo? Clique aqui.