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
}