Pode explicar o que é uma lista ligada e como ela funciona?

Uma lista ligada é uma estrutura de dados composta por nós, onde cada nó contém dados e uma referência ao próximo nó na lista. Ao contrário dos arrays, as listas ligadas não requerem um bloco de memória contíguo e permitem inserir e remover elementos de forma eficiente.

Principais tipos de listas ligadas:

• Lista ligada simples: cada nó contém apenas uma referência ao próximo nó.
• Lista duplamente ligada: cada nó contém referências tanto ao próximo como ao anterior.

Exemplo de lista ligada simples em JavaScript (Node.js):

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  add(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
}

Listas ligadas são úteis quando é necessário alterar dinamicamente o tamanho da estrutura e fazer inserções/removals frequentes de elementos.