Singly Linked List(Lista Interligada Unica) em JavaScript
Tags: datastructure, estruturadedados, linkedlist
Published: 2019-09-20 09:34:49

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

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

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

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

#### <b>Propriedades da Lista Interligada:</b>

- <u>Node(Nó):</u> Contém dados e referência para o próximo nó.

- <u>Head:</u> Contém referência do primeiro nó da lista.

- <u>Tail:</u> Contém referência do último nó da lista.

- <u>Length:</u> Número exacto de <b>nós</b> na lista.

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

<img src="https://s3-us-west-2.amazonaws.com/faustino.dev/single-linked-list.png" width="650" height="350" />

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

#### Criação de um Nó

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

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

#### Criando a Lista

```javascript
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 <b>Nós</b> à lista.

```javascript
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 <b>Nós</b> à mesma

```javascript
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 <b>Nós</b> e todos eles estão ligados entre si.

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

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

#### Removendo <b>Nós</b> da Lista

```javascript
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 <b>nós</b> da lista, estamos simplesmente a cortar o ligação que eles têm entre si, em seguida, o Garbage Collector(em português <b><i>Coletor de Lixo</i></b>) fará uma limpeza e então apagará da RAM os <b>nós</b> que não tenham nenhuma ligação.

#### Iterando a Lista

```javascript
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 <b>nó</b> 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 <b>nós</b> específicos na lista.