Estrutura de dados de Lista Ligada

Arrays (ou listas) provavelmente são a estrutura de dados mais comum usada para armazenar uma coleção de elementos

Cada linguagem tem a própria implementação de arrays

Essa estrutura de dados é muito conveniente e oferece uma sintaxe prática com [] para acessar seus elementos. No entanto, ela apresenta uma desvantagem: o tamanho do array é fixo (na maioria das linguagens), e inserir ou remover itens do início ou do meio do array é custoso, pois os elementos têm de sofrer um deslocamento

Apesar de que o Javascript tem métodos na classe Array que farão isso para nós, é isso que acontece internamente também

As listas ligadas armazenam uma coleção sequencial de elementos; no entanto, de modo diferente dos arrays, nas listas ligadas os elementos não são posicionados de forma contínua na memória

Cada elemento é constituído de um nó que armazena o elemento propriamente dito, além de uma referência, também conhecida como ponteiro ou ligação que aponta para o próximo elemento

Uma das vantagens de uma lista ligada em relação a um array convencional é que não é necessário deslocar os elementos quando eles são adicionados ou removidos. Entretanto, precisamos usar ponteiros quando trabalhamos com uma lista ligada, e, por esse motivo, é preciso prestar atenção especial na implementação desse tipo de lista

Em um array, podemos acessar diretamente qualquer elemento em qualquer posição; em uma lista ligada, se quisermos acessar um elemento no meio, será necessário partir do início (cabeça ou head) e iterar pela lista até encontrarmos o elemento desejado

Criando a classe LinkedList

Agora que já sabemos o que é uma lista ligada, vamos começar a implementar a nossa estrutura de dados

Primeiro de tudo, precisamos de uma função para nos ajudar na comparação dos elementos:

function defaultEquals(a, b) {
  return a === b
}

E uma classe para criação do nosso nó ou Node:

class NodeList {
  constructor(element) {
    this.element = element
    this.next = undefined
  }
}

Agora vamos criar o esqueleto da nossa classe LinkedList

class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.count = 0
    this.head = undefined
    this.equalsFn = equalsFn
  }
}

Na estrutura de dados LinkedList, começamos declarando a propriedade count, que armazena o número de elementos que temos na lista

Implementaremos também um método chamado indexOf, o qual servirá para encontrar um elemento específico na lista

Para uma comparação de igualdade entre os elementos da lista, usaremos uma função chamada internamente como equalsFn, vamos deixar disponível para que quem for usar essa classe consiga passar uma função de comparação personalizada, mas por padrão vamos seguir assim

Como essa estrutura de dados é dinâmica, precisamos armazenar também uma referência ao primeiro elemento. Para isso, podemos armazenar a referência de this em uma variável que chamaremos de head

Para representar a cabeça (head) e outros elementos da lista, vamos utilizar nossa classe NodeList,

essa classe representa o item que queremos adicionar na lista, e um atributo next, que é o ponteiro que faz a ligação para o próximo nó da lista

Aqui está todos os métodos que vamos implementar na nossa classe LinkedList e suas responsabilidades

• push(element): esse método adiciona um novo elemento no final da lista

• insertAt(element, position): esse método insere um novo elemento em uma posição específica da lista

• getElementAt(index): esse método devolve o elemento que está em uma posição específica da lista. Se o elemento não estiver na lista, undefined será devolvido

• remove(element): esse método remove um elemento da lista

• indexOf(element): esse método devolve o índice do elemento na lista. Se o elemento não estiver na lista, -1 será devolvido

• removeAt(position): esse método remove um item de uma posição específica da lista

• isEmpty(): esse método devolve true se a lista ligada não contiver nenhum elemento, e false se o tamanho da lista for maior que 0

• size(): esse método devolve o número de elementos contidos na lista

• getHead(): esse método devolve o primeiro elemento da lista

Inserindo elementos no final da Lista

Ao adicionar um elemento no final de um objeto LinkedList, podemos ter dois cenários:

• Um que a lista está vazia e estamos adicionando o seu primeiro elemento

• Outro em que a lista não está vazia e estamos concatenando elementos a ela

Implementação do método push:

push(element) {
  const node = new NodeList(element)
  let current
  if (this.head === undefined) {
    this.head = node
  } else {
    current = this.head
    while(current.next !== undefined) {
      current = current.next
    }
    current.next = node
  }
  this.count++
}

A primeira tarefa é criar um novo NodeList passando element como o seu valor

Vamos implementar o primeiro cenário: adicionar um elemento quando a lista está vazia

Quando criamos um objeto LinkedList, head (cabeça) apontará para undefined, se o elemento head for undefined significa que a lista está vazia, isso é sinal de que estamos adicionando o primeiro elemento à lista

Então tudo que temos a fazer é atribuir o node a head. O próximo elemento NodeList será automaticamente undefined

Desse modo, temos o primeiro cenário coberto. Vamos passar para o segundo, que consiste em adicionar um elemento no final da lista quando ela não está vazia

Para adicionar um elemento no final da lista, inicialmente devemos localizar o último elemento

Lembre-se de que temos somente uma referência ao primeiro elemento, portanto é necessário iterar pela lista até encontrarmos o último item

Para isso, precisamos de uma váriavel que aponte para o item atual (current) na lista

Quando percorremos a lista com uma laço, sabemos que alcançamos o seu final quando o ponteiro current.next for undefined. Então, tudo que temos que fazer é ligar o ponteiro next do elemento current (que é o último) ao nó que queremos adicionar na lista

Ao criar uma instância de NodeList, seu ponteiro next sempre será undefined. Não tem problema nisso, pois sabemos que esse será o último item da lista

E, por fim, não podemos nos esquecer de incrementar o tamanho da lista para que possamos ter controle sobre ela e obter facilmente o seu tamanho

Removendo elementos de uma posição específica da Lista

Vamos agora ver como podemos remover elementos da LinkedList

Implementaremos dois métodos:

• O primeiro remove um elemento de uma posição específica (removeAt)

• O segundo é baseado no valor do elemento

Vamos ver o segundo método um pouco mais pra frente

Como no caso do método push, há dois cenários para remover elementos de uma lista

• O primeiro é aquele em que removemos o primeiro elemento

• O segundo é aquele em que removemos qualquer elemento que não seja o primeiro

O código do removeAt é esse:

removeAt(index) {
  if (index >= 0 && index < this.count) {
    let current = this.head
    if (index === 0) {
      this.head = current.next
    } else {
      let previous
      for (let i = 0; i < index; i++) {
        previous = current
        current = current.next
      }
      previous.next = current.next
    }
    this.count--
    return current.element
  }
  return undefined
}

Vamos explorar esse código passo a passo

Como o método receberá o index (posição) do nó que deve ser removido, precisamos verificar se index é válido

Uma posição válida variará de index 0 (inclusive) até o tamanho da lista, count - 1 pois index começa do zero

Se a posição não for válida, devolveremos undefined, o que significa que nenhum elemento foi removido da lista

Se quisermos remover o primeiro elemento, basta fazer head apontar para o segundo elemento da lista

Fazemos uma referência ao primeiro elemento da lista usando a variável current; também usaremos esse valor para iterar pela lista

Assim, a variável current é uma referência ao primeiro elemento da lista

Se atribuirmos head para current.next, estaremos removendo o primeiro elemento

Vamos agora supor que queremos remover o último item ou um item do meio da lista

Para isso, devemos iterar pelos nós da lista até chegarmos à posição desejada

Um detalhe importante: a variável current sempre fará referência ao elemento atual da lista que estivermos percorrendo com o laço

Devemos também ter uma referência ao elemento que estiver antes de current; vamos chamar de previous

Depois de iterar até a posição desejada, a variável current armazenará o nó que queremos remover da lista

Assim, para remover o nó current, tudo que temos que fazer é ligar previous.next a current.next

Desse modo, o nó current ficará perdido na memória do computador e estará disponível para limpeza do coletor de lixo (garbage collector)

Percorrendo a lista até alcançar a posição desejada

No método removeAt, devemos percorrer a lista com um laço até alcançar o index (posição) desejado

O código para alcançar o index desejado com um laço é comum nos métodos da classe LinkedList

Por esse motivo, podemos refatorar e extrair a sua lógica em um método para que ele seja reutilizado em lugares diferentes

Desse modo, vamos criar o método getElementAt:

getElementAt(index) {
  if (index >= 0 && index < this.count) {
    let node = this.head
    for (let i = 0; i < index && node !== undefined; i++) {
      node = node.next
    }
    return node
  }
  return undefined
}

Somente para garantir que percorremos a lista com um laço até encontrarmos uma posição válida, devemos verificar se o index passado como parâmetro é uma posição válida

Se uma posição inválida for passada como parâmetro, devolveremos undefined, pois a posição não existirá na LinkedList

Em seguida, inicializaremos a variável node com o primeiro elemento, que é head - essa variável será usada para fazer a iteração pela lista

Também podemos renomear a variável node para current se quisermos manter o padrão usado nos outros métodos da classe LinkedList

Agora, percorremos a lista com um laço até alcançar o index desejado

Ao sair do laço, o elemento node referenciará o elemento na posição index

Refatorando o método removeAt

Podemos refatorar o método removeAt e usar o método getElementAt

if (index === 0) {
  lógica para a primeira posição
} else {
  const previous = this.getElementAt(index - 1)
  current = previous.next
  previous.next = current.next
}

Inserindo um elemento em qualquer posição

Agora vamos implementar o método insertAt, que possibilita inserir um element em qualquer posição.

Vamos dar uma olhada na implementação do método

insertAt(element) {
  if (index >= 0 && index <= this.count) {
    const node = new NodeList(element)
    if (index === 0) {
      const current = this.head
      node.next = current
      this.head = node
    } else {
      const previous = this.getElementAt(index - 1)
      const current = previous.next
      node.next = current
      previous.next = node
    }
    this.count++
    return true
  }
  return false
}

Como estamos lidando com posições (índices), devemos verificar se os valores não estão fora do intervalo, exatamente como fizemos no método removeAt

Se o valor estiver fora do intervalo, devolveremos false para informar que nenhum item foi adicionado a lista

Se a posição for válida, trataremos os diferentes cenários

• O primeiro é aquele em que precisamos adicionar o element no início da lista, isto é, na primeira posição

• O segundo é adicionar element no meio ou no final da lista

Em primeiro lugar, devemos percorrer a lista com um laço até que a posição desejada seja alcançada

Nesse caso, avançaremos até index - 1, isto é, uma posição antes do local em que queremos inserir o novo node

Ao sair do laço, a variável previous referenciará um elemento antes do index em que queremos inserir o novo elemento, e a variável current referenciará um element após a posição em que gostaríamos de inserir o novo elemento

Nesse caso, queremos adicionar o novo item entre previous e current

Portanto, em primeiro lugar, devemos fazer uma ligação entre o novo elemento (node) e current e, então, precisamos alterar a ligação entre previous e current

Devemos fazer previous.next apontar para node em vez de apontar para current

Se tentarmos adicionar um novo element na última posição, previous será uma referência ao último item da lista, e current será undefined

Nesse caso, node.next apontará para current, previous.next apontará para node e teremos um novo **element** na lista

Vamos agora falar um pouco sobre inserir o novo element no meio da lista

Nesse caso, estamos tentando inserir o novo element (node) entre os elementos previous e current

Inicialmente, devemos definir o valor do ponteiro node.next para current

Em seguida, temos de definir o valor de previous.next para node

Por fim, teremos um novo element na lista

Método indexOf: devolvendo a posição de um elemento

O próximo método que vamos implementar é o método indexOf

Esse método recebe o valor de um elemento e devolve a sua posição caso ele seja encontrado

Do contrário, -1 será devolvido

Vamos criar nosso código:

indexOf(element) {
  let current = this.head
  for (let i = 0; i < this.count && current !== undefined; i++) {
    if (this.equalsFn(element, current.element)) {
      return i
    }
    current = current.next
  }
  return -1
}

Como sempre, precisamos de uma variável que nos ajude a iterar pela lista; essa variável é current,

e o seu primeiro valor é head

Em seguida, iteramos pelos elementos, começando de head (índice 0) até que o tamanho da lista (a variável count) seja alcançado

Somente por garantia, podemos verificar se a variável current é undefined a fim de evitar erros em tempo de execução

Em cada iteração, verificaremos se o elemento que estamos procurando é o lemento no nó current

Nesse caso, usaremos a função de igualdade que passamos para o construtor da classe LinkedList

O valor default de equalsFn é esse:

function defaultEquals(a, b) {
  return a === b
}

Portanto, seria o mesmo que usar element === current.element

No entanto, se o elemento for um objeto complexo, vamos permitir a passagem de uma função de comparação personalizada atráves do construtor da classe LinkedList

Se o elemento que estamos procurando for o element em current, devolveremos a sua posição

Se não for, iteramos para o próximo nó da lista

O laço não será executado se a lista estiver vazia ou se alcançarmos o final dela

Se o valor não for encontrado, devolveremos -1

Removendo um elemento da Lista

Com o método indexOf criado, podemos implementar outros métodos, por exemplo, o método remove

remove(element) {
  const index = this.indexOf(element)
  return this.removeAt(index)
}

Já temos implementado um método que remove um elemento de uma posição específica removeAt

Agora que temos o método indexOf, se passarmos o valor do elemento, podemos determinar sua posição e chamar o método removeAt passando a posição encontrada

Será muito mais simples, além de mais fácil, caso haja necessidade de modificar o código do método removeAt

Métodos isEmpty, size e getHead

Os métodos que vamos criar agora são bem simples

Vamos começar pelo método size

O método size devolve o número de elementos da lista

size() {
  return this.count
}

O método isEmpty devolverá true se não houver nenhum elemento na lista, e false caso contrário

isEmpty() {
  return this.size() === 0
}

E por último, temos o método getHead

getHead() {
  return this.head
}

Por fim, terminamos nossa criação de uma Lista Ligada ou Linked List.

O caminho foi longo mas acho que se você chegou até aqui, você definitivamente conseguiu aprender algo :)