Programadores medianos se preocupam meramente com o cdigo. Programadores excelentes se preocupam com estruturas de dados e suas relaes.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 exerccios ). Se quiser saber mais sobre minha histria voc pode conferir meu post fazendo um review dos ltimos anos. Eu tambm costumo passar algumas horas do meu tempo livre brincando com os amigos no clash of code.

, eu sei, bem nerd . Ento como uma forma de ressuscitar esse meu antigo prazer, eu decidi criar uma srie 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

Vamos ver vrias estruturas de dados aqui, mas quis comear com uma das mais simples e comuns Linked List ( lista encadeada ).

Para quem ainda no sabe muito bem como funciona a lista encadeada confere aqui o que o Wikipedia diz sobre:

Em cincia da computao, a lista ou sequncia uma abstrao de tipo de dado que representa um nmero mensurvel de valores ordenados.

Se isso no ajudou muito, voc pode apenas imaginar uma sequncia de dados onde um dado est conectado com o prximo, pro exemplo:

1 -> 2 -> 3 -> 4 -> 5 -> null

Considerando uma lista como essa, podemos chamar cada nmero de node ( n ) e dar um nome especial para o primeiro e ltimo, respectivamente head and tail ( cabea e cauda ).

Todo o cdigo que vamos ver aqui est disponvel nesse CodeSandbox. Junto com uma pequena aplicao para visualizar nosso trabalho.

Chega de teoria, vamos botar a mo na massa...

DISCLAIMER: O objetivo aqui ser o mais didtico possvel para iniciantes, ento estou bem ciente que o cdigo aqui pode no ser padro de qualidade de produo. Tambm estou tentando evitar algumas mgicas do JS e coisas mais complexas como recurso para manter o mais simples possvel. ;)

API

No final, o que queremos atingir um contrato ( API ) parecido com o cdigo a seguir:

const {     list,    tail,    size,    add,    remove,    removeAt,    indexOf,    dataAt, } = useList();

Nossa lista apenas uma sequncia de nodes ento precisamos representar isso. Vamos dizer que queremos poder usar um node da seguinte forma:

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 construda com nodes e nos vamos fazer operar funes nos nodes ento faz todo sentido que criar nossa representao de Node seja a primeira coisa a se fazer...

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 } 

Aes

Vamos usar um reducer simples nativo do React para manipular nossa list e para isso funcionar precisamos ter uma ideia clara do que pode ser executado, ento vamos definir as possveis aes que podem acontecer na nossa list:

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

O hook

Nosso hook uma funo bem simples que apenas mantem o estado usando useState e expem algumas funes para permitir manipular o estado, ento a gente vai comear com algo parecido com o seguinte:

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 manipulao do estado baseado nas aes que definimos anteriormente.

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

Mtodos base

Precisaremos de algumas funes para poder executar algumas operaes na list, ento vamos comear construindo-as:

add

Temos que poder adicionar novos nodes na list e, como disse anteriormente, manter a referncia da tail para que nossa operao de add seja O(1) . Nossa funo vai receber o dado para ser adicionado, a list atual e nossa tail.

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 condio vai ser algo semelhante :

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 ento fazer com que o prximo elemento depois da nossa tail atual passe a ser a nova tail. Colocando tudo isso em cdigo vai ficar mais ou menos assim:

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.

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

remove

Esse vai parecer um pouco mais complicado, mas no se preocupe, apenas umas linhas a mais de cdigo e a gente vai dar conta .

A gente s pode remover um node se a nossa list no est vazia, ento vamos colocar todo nosso cdigo dentro dessa condio:

const remove = (data, { list, tail, size }) => {    if (list) {        ....    }}

Se estamos tentando remover o primeiro node tudo que precisamos fazer com que o comeo da nossa list passe a ser o atual segundo elemento e se o prximo item no existia vamos ter que "limpar" nossa tail tambm.

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

Se esse no 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, comeamos olhando o incio da lista pulando para o prximo 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

    // Vamos usar esse para percorrer na list     let currentNode = list;    // Vamos sempre manter uma referncia 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 no, apenas fazemos nosso node anterior            // apontar para o prximo            prev.next = currentNode.next;        }        return { list, tail, size: size - 1 };    }

No final, nosso mtodo remove vai ficar assim:

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 referncia da tail mas um preo que vale a pena pagar. No pior cenrio esse mtodo vai passar por todos os possveis nodes da nossa list ento podemos dizer que ele O(N) .

Agora vamos apenas adicionar nosso mtodo no nosso reducer:

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

indexOf

Algumas vezes vamos querer saber em qual posio especfica um dado se encontra, para isso vamos utilizar o mtodo 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 no encontrarmos vamos retornar -1. O mtodo vai ser bem simples de entender e no precisamos adicionar ele no reducer j que ele no vai alterar nosso estado.

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

Apenas um detalhe final sobre esse mtodo: para podermos encontrar um dado possvel 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 recurso, mas vamos manter o simples e fazer iterativo. Vamos ter que passar por cada node e mudar seu prximo, isso faz do nosso mtodo O(N). O objetivo aqui se tivermos uma list como:

1 -> 2 -> 3 -> null

Depois de usar o revert esperamos ter:

3 -> 2 -> 1 -> null

Ento a primeira coisa como no mtodo anterior conferir se a list no est vazia e se no estiver vamos manter referncia para o node atual e o anterior. Enquanto existir nodes para percorrer vamos trocar o anterior com o atual, parece confuso? Vamos ver o cdigo:

const revertList = (list) => {    if (list) {        let prev = null;        let currentNode = list;        // Vamos lembrar que temos que prestar ateno         // com a tail        let tail = null;        while (currentNode) {            // Salve o restante da list por enquanto            let restList = currentNode.next;            // faa 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 mtodo no nosso reducer:

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

stringify

E por ltimo, temos que ter alguma forma de visualizar nossa list no ? Vamos criar um mtodo bem simples que vai percorrer a lista e combinar o poder dos arrays para no ter que ficar conferindo se temos um prximo elemento ou no.

    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 mtodos ( eu at implementei alguns outros no CodeSandbox ) mas esse tutorial ficou grande de mais j e imagino que agora voc j tem uma ideia bsica de como a Linked List funciona correto?

Se curtiu, ficou com qualquer dvida ou quer dar uma sugesto de qual pode ser nossa prxima estrutura de dado pode ficar a vontade para falar comigo no meu instagram onde eu tambm compartilho mais dicas de programao.