Implementando Lista Ligada (Linked List) com NodeJS e Javascript

Inserir no meio de um array grande custa caro — o runtime desloca índices. Lista ligada 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.

O que você vai aprender:

• Nó com data e next
• addFirst, addLast e percorrer a lista
• Diferença para array no dia a dia
• Ideia de lista duplamente ligada (previous)

Pré-requisitos: arrays (ep. 2) e o resumo da série.

Linked list em JavaScript: nós e ponteiros

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:

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:

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):

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…:

node linked-list.js

Você deve ver algo mais ou menos parecido com isso:

node linked-list.js
 
{
  current: 3,
  next: ListNode { data: 2, next: ListNode { data: 1, next: [ListNode] } }
}
{
  current: 2,
  next: ListNode { data: 1, next: ListNode { data: 4, next: [ListNode] } }
}
{
  current: 1,
  next: ListNode { data: 4, next: ListNode { data: 5, next: [ListNode] } }
}
{
  current: 4,
  next: ListNode { data: 5, next: ListNode { data: 6, next: null } }
}
{ current: 5, next: ListNode { data: 6, next: null } }
{ current: 6, next: null }

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.

TL;DR — Linked list

Próximos passos

• Pilha (ep. 4): LIFO em cima de array ou lista — Implementando Pilhas
• Fila (ep. 5): FIFO — muitas filas usam lista ligada no dequeue — Implementando Filas

Antes de fechar

Já implementou doubly linked list ou usou lista no histórico do browser? Comenta — e se achou bug no código do post, fala que a gente corrige.