Estruturas de dados como Hooks, um guia: Linked List
Tags: javascript, react, codenewbie, computerscience
Published: 2021-09-29 02:39:31

> “Programadores medianos se preocupam meramente com o código. Programadores excelentes se preocupam com estruturas de dados e suas relações.” — Linus Torvalds

Eu amo algoritmos e estruturas de dados, quando estava na faculdade eu fui monitor de estruturas de dados ( basicamente ajudava alunos novos a entender o assunto e o professor a corrigir exercícios ). Se quiser saber mais sobre minha história você pode conferir meu [post fazendo um review dos últimos anos](https://dev.to/assuncaocharles/um-review-de-quase-10-anos-como-dev-48fc). Eu também costumo passar algumas horas do meu tempo livre brincando com os amigos no [clash of code](https://www.codingame.com/blog/clash-of-code-time-has-come-for-clash/).

É, eu sei, bem nerd 🤓. Então como uma forma de ressuscitar esse meu antigo prazer, eu decidi criar uma série de posts implementando estruturas de dados em javascript e para fazer isso ficar mais divertido e no hype vamos fazer isso tudo como [react hooks](https://reactjs.org/docs/hooks-intro.html)

Vamos ver várias estruturas de dados aqui, mas quis começar com uma das mais simples e comuns `Linked List` ( lista encadeada ).

Para quem ainda não sabe muito bem como funciona a lista encadeada confere aqui o que o [Wikipedia](https://en.wikipedia.org/wiki/List_(abstract_data_type)) diz sobre:

> Em ciência da computação, a lista ou sequência é uma abstração de tipo de dado que representa um número mensurável de valores ordenados.

Se isso não ajudou muito, você pode apenas imaginar uma sequência de dados onde um dado está conectado com o próximo, pro exemplo:

```javascript
1 -> 2 -> 3 -> 4 -> 5 -> null
```
Considerando uma lista como essa, podemos chamar cada número de `node` ( nó ) e dar um nome especial para o primeiro e último, respectivamente `head` and `tail` ( cabeça e cauda ). 

Todo o código que vamos ver aqui está disponível [nesse CodeSandbox](https://codesandbox.io/s/uselinkedlist-940id?file=/src/App.js). Junto com uma pequena aplicação para visualizar nosso trabalho. 

![Linked List Gif](http://g.recordit.co/x2q0CNDONl.gif)

Chega de teoria, vamos botar a mão na massa... 

__DISCLAIMER: O objetivo aqui é ser o mais didático possível para iniciantes, então estou bem ciente que o código aqui pode não ser padrão de qualidade de produção. Também estou tentando evitar algumas mágicas do JS e coisas mais complexas como recursão para manter o mais simples possível. ;)__

## API

No final, o que queremos é atingir um contrato ( API ) parecido com o código a seguir:

```javascript
const { 
    list,
    tail,
    size,
    add,
    remove,
    removeAt,
    indexOf,
    dataAt, 
} = useList();
```  
Nossa lista é apenas uma sequência de `nodes` então precisamos representar isso. Vamos dizer que queremos poder usar um `node` da seguinte forma:

```javascript
const node = new Node(1); // 1 ou qualquer outro tipo de data que você queira manter na sua lista
```

# Partes fundamentais

### Node

Nossa lista vai ser construída com `nodes` e nos vamos fazer operar funções nos `nodes` então faz todo sentido que criar nossa representação de `Node` seja a primeira coisa a se fazer...

```javascript
function Node(data) {
  this.data = data;
  this.next = null;
}

// 1,2,3 Testando...

const node = new Node(1);
console.log(node); // { data: 1, next: null } 
```

### Ações

Vamos usar um [reducer simples](https://reactjs.org/docs/hooks-reference.html#usereducer) nativo do `React` para manipular nossa `list` e para isso funcionar precisamos ter uma ideia clara do que pode ser executado, então vamos definir as possíveis ações que podem acontecer na nossa `list`:

```javascript
const actions = {
  ADD: "[LIST] - ADD",
  REMOVE: "[LIST] - REMOVE",
  REMOVE_AT_INDEX: "[LIST] - REMOVE_AT_INDEX",
  REVERT: "[LIST] - REVERT"
}
```

### O hook 

Nosso hook é uma função bem simples que apenas mantem o estado usando [useState](https://reactjs.org/docs/hooks-reference.html#useReducer) e expõem algumas funções para permitir manipular o estado, então a gente vai começar com algo parecido com o seguinte:

```javascript

export function useList() {
    const [{ list, tail, size }, dispatch] = useReducer(listReducer, {
         tail: null,
         list: null,
         size: 0
    });

    const add = (data) => {
        dispatch({ type: actions.ADD, data });
    }

    ...

    return { add, ..., list, tail, size }
}
```

### Reducer

Precisamos definir nosso reducer, o que vai ser bem simples, basicamente contendo manipulação do estado baseado nas ações que definimos anteriormente.

```javascript
const listReducer = (state, action) => {
    switch (action.type) {
        ...
        default:
            return state;
	}
};
```

### Métodos base

Precisaremos de algumas funções para poder executar algumas operaçÕes na `list`, então vamos começar construindo-as:

#### `add`

Temos que poder adicionar novos `nodes` na `list` e, como disse anteriormente, manter a referência da `tail` para que nossa operação de `add` seja **O(1)** 🤟🏻. Nossa função vai receber o dado para ser adicionado, a `list` atual e nossa `tail`.

```javascript
const add = (data, { list, tail, size }) => { ... } 
```

Vamos conferir se já existe o primeiro `node` na nossa `list` ou se vamos ter que criar o primeiro. Se é o primeiro elemento da `list` apenas vamos criar um `Node` e fazer com que nossa `list` seja aquele `node`. Nossa condição vai ser algo semelhante à:  

```javascript
if (!list) {
    let newList = new Node(data);
    let newTail = newList;
    return { list: newList, tail: newTail };
}
```

Se já tivermos algo na `list`, significa apenas que devemos adicionar algo depois da `tail` ( que é sempre nosso último elemento ) e então fazer com que o próximo elemento depois da nossa `tail` atual passe a ser a nova `tail`. Colocando tudo isso em código vai ficar mais ou menos assim:

```javascript
const add = (data, { list, tail, size }) => {
    if (!list) {
        let newList = new Node(data);
        let newTail = newList;
	return { list: newList, tail: newTail, size: size + 1 };
    } else {
        tail.next = new Node(data);
        tail = tail.next;
        return { list, tail, size: size + 1 };
    }
};
```

E agora a gente tem que adicionar o que fizemos no reducer.

```javascript
case actions.ADD:
    return { ...state, ...add(action.data, state) };
```

#### `remove`

Esse vai parecer um pouco mais complicado, mas não se preocupe, é apenas umas linhas a mais de código e a gente vai dar conta 😉. 

A gente só pode remover um `node` se a nossa `list` não está vazia, então vamos colocar todo nosso código dentro dessa condição:

```javascript
const remove = (data, { list, tail, size }) => {
    if (list) {
        ....
    }
}
```
Se estamos tentando remover o primeiro `node` tudo que precisamos fazer é com que o começo da nossa `list` passe a ser o atual segundo elemento e se o próximo item não existia vamos ter que "limpar" nossa `tail` também. 

```javascript
if (list.data === data) {
    const newList = list.next;
    return { list: list.next, tail: !newList ? null : tail, size: size - 1 };
} 
```

Se esse não era o caso, vamos ter que "andar" na nossa lista até encontrarmos o `node` que queremos remover. Vamos dizer que queremos remover o `node` **X**, começamos olhando o início da lista pulando para o próximo até chegar em **X** e quando isso acontecer fazemos com que o `node` anterior de **X** agora aponte para o `node` depois de **X** o que seria `X.next` e assim cortando o **X** da `list`

```javascript
    // Vamos usar esse para percorrer na list 
    let currentNode = list;
    // Vamos sempre manter uma referência do no anterior
    // Para que possamos mudar para onde ele vai apontar
    // Quando encontrarmos o node que queremos remover.
    let prev = null;
    // vamos caminhar na lista até encontrar o que queremos
    // ou até chegarmos no fim
    while (currentNode.data !== data && currentNode.next) {
        prev = currentNode;
        currentNode = currentNode.next;
    }
    // Se o node atual é o node que queremos remover...
    if (currentNode.data === data) {
        // Vamos primeiro verificar se estamos tentando 
        // remover nossa tail atual e se sim nossa tail
        // vai se tornar no node anterior
        if (currentNode === tail) {
            prev.next = null;
            tail = prev;
        } else { 
            // Se não, apenas fazemos nosso node anterior
            // apontar para o próximo
            prev.next = currentNode.next;
        }
        return { list, tail, size: size - 1 };
    }
```

No final, nosso método `remove` vai ficar assim: 

```javascript
const remove = (data, { list, tail, size }) => {
    if (list) {
        if (list.data === data) {
            const newList = list.next;
            return { list: list.next, tail: !newList ? null : tail, size: size - 1 };
	} else {
	    let currentNode = list;
	    let prev = null;
	    while (currentNode.data !== data && currentNode.next) {
                prev = currentNode;
		currentNode = currentNode.next;
	    }
	    if (currentNode.data === data) {
	        if (currentNode === tail) {
		    prev.next = null;
		    tail = prev;
		} else {
		    prev.next = currentNode.next;
		}
		return { list, tail, size: size - 1 };
	    }
	}
    }
};
```

É um pouco mais complicado porque estamos mantendo referência da `tail` mas é um preço que vale a pena pagar. No pior cenário esse método vai passar por todos os possíveis `nodes` da nossa `list` então podemos dizer que ele é **O(N)** 🤷🏻‍♂️.

Agora vamos apenas adicionar nosso método no nosso reducer:

```javascript
    case actions.REMOVE:
        return { ...state, ...remove(action.data, state) };
```

#### `indexOf`

Algumas vezes vamos querer saber em qual posição específica um dado se encontra, para isso vamos utilizar o método `indexOf`. Nossa `list` vai ser baseada em index 0, basicamente como um array. O que precisamos fazer é percorrer a `list` até encontrarmos nosso dado procurado e se chegarmos ao final e não encontrarmos vamos retornar `-1`. O método vai ser bem simples de entender e não precisamos adicionar ele no reducer já que ele não vai alterar nosso estado.

```javascript
    const indexOf = (data) => {
        // Começamos sempre do index 0
        let currentIndex = 0;
        let currentNode = list;
        // Enquanto existir um node para percorrer e
        // ainda não encontramos nosso dado
        // vamos aumentar nosso currentIndex e ir para o
        // próximo node
        while (currentNode && currentNode.data !== data) {
            currentNode = currentNode.next;
            currentIndex++;
        }
        // Encontramos o dado? Se sim, retorne o index
        // se não, retorne `-1`
        return currentNode?.data === data ? currentIndex : -1;
    };
```

Apenas um detalhe final sobre esse método: para podermos encontrar um dado é possível que tenhamos que olhar todos os nodes até o final o que faz o `indexOf` ser **O(N)**.

#### `revert`

Esse é bem comum de ser perguntando em uma entrevista de emprego. É bem legal de resolver usando recursão, mas vamos manter o simples e fazer iterativo. Vamos ter que passar por cada `node` e mudar seu próximo, isso faz do nosso método **O(N)**. O objetivo aqui é se tivermos uma `list` como:

```javascript
1 -> 2 -> 3 -> null
```

Depois de usar o `revert` esperamos ter:

```javascript
3 -> 2 -> 1 -> null
```

Então a primeira coisa como no método anterior é conferir se a `list` não está vazia e se não estiver vamos manter referência para o `node` atual e o anterior. Enquanto existir `nodes` para percorrer vamos trocar o anterior com o atual, parece confuso? Vamos ver o código:

```javascript
const revertList = (list) => {
    if (list) {
        let prev = null;
        let currentNode = list;
        // Vamos lembrar que temos que prestar atenção 
        // com a tail
        let tail = null;
        while (currentNode) {
            // Salve o restante da list por enquanto
            let restList = currentNode.next;
            // faça o node atual apontar para o anterior
            currentNode.next = prev;
            // substitua o anterior pelo atual
            prev = currentNode;
            // e se o nosso anterior agora aponta
            // para o fim ( null ) 
            // significa que ele é nossa nova tail 
            if (prev.next === null) {
                tail = prev;
            }
            // pegue o resto da list e continue fazendo 
            // o mesmo processo
            currentNode = restList;
	}
        return { list: prev, tail };
    }
};

``` 

Agora vamos apenas adicionar o método no nosso reducer: 

```javascript
    case actions.REVERT:
        return { ...state, ...revertList(state.list) };
```

#### `stringify`

E por último, temos que ter alguma forma de visualizar nossa `list` não é? Vamos criar um método bem simples que vai percorrer a lista e combinar o poder dos arrays para não ter que ficar conferindo se temos um próximo elemento ou não.

```javascript
    const listDataArray = [];
    let currentNode = list;
    while (currentNode) {
        listDataArray.push(currentNode.data);
        currentNode = currentNode.next;
    }
    return listDataArray.join(' -> ');
```

--------

Isso é tudo pessoal, com certeza podemos nos divertir um pouco mais com a estrutura de dados `list` e implementar outros métodos ( eu até implementei alguns outros no CodeSandbox ) mas esse tutorial ficou grande de mais já e imagino que agora você já tem uma ideia básica de como a `Linked List` funciona correto?

Se curtiu, ficou com qualquer dúvida ou quer dar uma sugestão de qual pode ser nossa próxima estrutura de dado pode ficar a vontade para falar comigo no meu [instagram](https://www.instagram.com/charlesassuncaooficial/) onde eu também compartilho mais dicas de programação.