Implementando Lista Ligada (Linked List) com NodeJS e Javascript
Lista ligada em JavaScript do zero: nós, inserção, remoção e quando ela vence o array. Tutorial prático e direto com Node.js.
Jonathan Juliani
Engenheiro de Software Sr - Full Stack · WithClutch Inc. | Juliani Tecnologia
Estruturas de DadosJavaScript
Inserir no de um array grande custa caro — o runtime desloca índices. troca acesso O(1) por índice por inserção/remoção O(1) quando você já tem o nó. Episódio 3 da série.
As listas ligadas (linked-lists) são uma estrutura de dados fundamental, oferecendo uma maneira flexível e eficiente de armazenar e manipular coleções de elementos.
Em NodeJS e/ou JavaScript é interessante pra gente compreender e saber implementar listas ligadas, isso pode otimizar algumas operações de dados, especialmente quando inserir e remover itens toda hora (frequentemente) é necessário. Vamos ver aqui a implementação e os benefícios das listas ligadas em JavaScript, com insights valiosos para o desenvolvimento de aplicações dinâmicas.
Fundamentos das Listas Ligadas
Uma lista ligada é composta por nós, onde cada nó contém dados e uma referência (ou “link”) para o próximo nó da sequência. Isso é diferente dos arrays normais, outra coisa é que as listas ligadas não requerem um bloco contínuo de memória, permitindo inserções e remoções de elementos com eficiência sem a necessidade de reorganizar toda a coleção.
Implementando Listas Ligadas em JavaScript / NodeJS
Então bora ir direto ao ponto, lista ligada, ta ai o código (versão simples), crie um arquivo linked-list.js e já sabe, mão na massa:
código
class ListNode { constructor(data) { this.data = data this.next = null }}class LinkedList { constructor() { this.head = null } // Método para adicionar elementos no início addFirst(data) { let newNode = new ListNode(data) newNode.next = this.head this.head = newNode } // Método para adicionar elementos no final addLast(data) { let newNode = new ListNode(data) if (!this.head) { this.head = newNode return } let tail = this.head while (tail.next !== null) { tail = tail.next } tail.next = newNode } // Métodos para remover elementos, buscar elementos, etc.}
Agora vamos testar, depois do addLast inclui esse código:
código
printList() { let current = this.head; while (current !== null) { console.log({ current: current.data, next: current.next }); current = current.next; } }
E aí vamos executar tudo isso colocando o código abaixo (fora da classe LinkedList):
código
const testList = () => { const list = new LinkedList() list.addFirst(1) list.addFirst(2) list.addFirst(3) list.addLast(4) list.addLast(5) list.addLast(6) list.printList()}testList()
Executando o node em 3, 2, 1…:
código
node linked-list.js
Você deve ver algo mais ou menos parecido com isso:
Olha que legal, a head imprimiu o número 3que foi o último addFirst executado. E o último item foi o 6 que foi também o último addLast executado. Pronto você já sabe como implementar uma lista-ligada (linked-list) agora dá pra brincar com um router por exemplo.
Jon, e lista duplamente ligadas?
Basicamente nas listas duplamente ligadas além do next, você tem o previous (mano pensa que aqui é qualquer nome, a gente fala next e previous, mas podia ser bananas e morangos, desde que, você entenda o conceito e que outros entendam também). Esse previous é o que vai apontar pró nó anterior (quando ele existir).
Consegue implementar ai usando o código acima e a imagem acima de base?
Se não, deixa um comentário que faço uma implementação seguindo essa base e expandindo pra listas duplamente ligadas.
Aplicações Práticas: Onde Listas Ligadas vão bem?
Gerenciamento Dinâmico de Coleções
Listas ligadas são ideais para aplicações que exigem gerenciamento dinâmico de coleções de dados, como a implementação de filas e pilhas, onde a inserção e remoção de elementos são operações comuns.
Melhorando a Performance em Aplicações de Tempo Real
Em sistemas de tempo real, onde a eficiência de memória e velocidade de processamento são críticas, listas ligadas oferecem uma alternativa flexível e eficiente a arrays ou outras estruturas de dados estáticas.
Edge cases: perder a head e loop infinito
Esquecer de atualizar head no addFirst ou ao remover o primeiro nó deixa a lista “órfã” — você perde tudo antes do novo topo.
"Tá Jon, como sei se criei ciclo na lista?"
Dois nós apontando pro mesmo next ou next do último voltando pro meio — travessia nunca termina. Em debug, use Set de nós visitados.
