“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. Eu também costumo passar algumas horas do meu tempo livre brincando com os amigos no clash of code.

É, 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

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 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:

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. Junto com uma pequena aplicação para visualizar nosso trabalho.

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:

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:

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...

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 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:

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 e expõem algumas funções para permitir manipular o estado, então a gente vai começar 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 manipulação do estado baseado nas ações que definimos anteriormente.

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.

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 à:

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:

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 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:

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.

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

    // 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:

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:

    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.

    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:

1 -> 2 -> 3 -> null

Depois de usar o revert esperamos ter:

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:

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:

    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.

    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 onde eu também compartilho mais dicas de programação.