Singly Linked List(Lista Interligada Unica) em JavaScript

Linked List ou em português Lista Interligada é uma estrutura de dados linear. Cada elemento(Node ou em português Nó) da lista contém dois elementos - os dados e a referência para o próximo nó. Um dos maiores potenciais da Lista Interligada é que o seu tamanho pode variar, ao contrário de um Array.

A referência é simplesmente o endereço físico de onde encontra-se armazenado o próximo nó na RAM.

Existem 4 tipos de Listas Interligadas, que são:

• Singly Linked List: Neste tipo de Lista Interligada, cada nó armazena os dados e a referência para o próximo nó.
• Circular Singly Linked List: Neste, a única diferença é que o último nó da lista aponta sempre para o primeiro como referência.
• Doubly Linked List: Neste, cada nó contém três elementos, a referência do nó anterior, os dados, e a referência do próximo nó da lista.
• Circular Doubly Linked List: Em relação ao tipo anterior, neste, a única diferença é que o último nó da lista aponta sempre para o primeiro como referência.

Propriedades da Lista Interligada:

• Node(Nó): Contém dados e referência para o próximo nó.

• Head: Contém referência do primeiro nó da lista.

• Tail: Contém referência do último nó da lista.

• Length: Número exacto de nós na lista.

Neste artigo, veremos a implementação de uma Singly Linked List.

Na ilustração acima, podemos ver que cada nó tem uma referência. Em uma Lista Interligada Simples, o último nó da fila tem a referência à null pois o mesmo não aponta para nenhum outro nó.

Criação de um Nó

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

Um nó é nada mais do que um objecto com duas propriedades, value que armzenaráqualquer tipo de dados que queiramos, e next que armazenará a referência para o próximo nó. Para isto, criamos um nó usando uma class em Javascript.

Criando a Lista

class ListaInterligada {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

A recém lista criada, contém as três propriedas acima listadas.

Vamos agora criar a função responsável por adicionar novos Nós à lista.

class ListaInterligada {
    // código anterior ocultado aqui
  add(value) {
    let node = new Node(value); // instanciamos um novo Nó
    let currentNode = this.head;

    // Caso a lista esteja vazia
    // adicionaremos o novo Nó no topo dela
    if (!currentNode) {
      this.head = node;
      this.tail = node;
      this.length++;
      return node;
    } else {
      // Caso a lista contenha elementos
      // adicionaremos o novo Nó no final da mesma
      while (currentNode.next) {
        currentNode = currentNode.next
      }
      currentNode.next = node;
      this.tail = node;
      this.length++;
      return node;
    }
  }
}

Instanciando a Lista Interligada e adicionando Nós à mesma

let lista = new ListaInterligada();
lista.add(5);
lista.add(9);
lista.add(15);

console.log(lista)
/*
{
  "head": {
    "value": 5,
    "next": {
      "value": 9,
      "next": {
        "value": 15,
        "next": null
      }
    }
  },
  "tail": {
    "value": 15,
    "next": null
  },
  "length": 3
}
*/

Ao imprimirmos a lista no console, podemos ver que ela contém três Nós e todos eles estão ligados entre si.

Estamos quase la, e se agora quiséssemos remover um dos Nós da lista?

Pois então, isto é completamente possível.

Removendo Nós da Lista

class ListaInterligada {
  // códigos anteriores ocultados aqui
  remove(location) {
    if (location === 0) {
      // caso queiramos remover o primeiro elemento
      this.head = this.head.next;
      this.length--;
      if (this.length === 0) {
        // e caso não haja mais elementos na lista
        this.tail = null;
      }
    }
    // caso o indice seja maior que o número de elementos na lista
    // removeremos o último elemento da mesma
    else if (location >= this.length) {
      let currentNode = this.head;
      for (let i = 0; i < this.length - 1; i++) {
        currentNode = currentNode.next; // currentNode sera o penúltimo elemento da lista
      }
      // caso este seja o último elemento da lista
      if (currentNode === this.head) {
        this.tail = this.head = null;
        this.length--;
        return;
      } else {
        currentNode.next = null;
        this.tail = currentNode;
        this.length--;
      }
    } else {
      // caso queiramos remover um Nó que não seja o último nem o primeiro
      let currentNode = this.head;
      for (let i = 0; i < location - 1; i++) {
        // atravessamos a lista até encontrarmos o elemento a ser removido
        currentNode = currentNode.next;
      }
      currentNode.next = currentNode.next.next; // removemos o elemento desejado
      this.tail = currentNode;
      this.length--;
    }
  }
}

Note que ao removermos nós da lista, estamos simplesmente a cortar o ligação que eles têm entre si, em seguida, o Garbage Collector(em português Coletor de Lixo) fará uma limpeza e então apagará da RAM os nós que não tenham nenhuma ligação.

Iterando a Lista

class ListaInterligada {
  // códigos anteriores ocultados aqui
  traverse() {
    let currentNode = this.head;
    for (let i = 0; i < this.length; i++) {
      console.log(currentNode.value);
      currentNode = currentNode.next;
    }
  }
}

No código acima, iteramos na lista e para cada nó presente na mesma, imprimimos o seu valor. Note que a propriedade this.length corresponde ao número de nós que a lista contém!
A mesma lógica aplicada no código acima, pode ser utilizada para implementar uma função para procurar nós específicos na lista.