Entendendo Algoritmos - CAP 2. Como usar arrays e listas encadeadas na prática

Este mês estou participando do clube de leitura #devslendo (Mais informações aqui) em que o livro escolhido é o Entendendo Algoritmos. No capítulo 2, são apresentados o array e a lista encadeada. O capítulo por si só é muito claro e direto. O objetivo deste post é trazer exemplos de implementações práticas em diferentes linguagens.

Para testar os exemplos aqui apresentados você pode utilizar o site replit. Basta criar um novo REPL selecionando a linguagem desejada.

Um pouquinho sobre Array

Não tenho a intenção de falar muito sobre o array. Acredito que ele seja mais familiar para a maioria das pessoas, e a implementação é introduzida nos primeiros passos de várias linguagens. No entanto, se é novidade para você, aqui vai um exemplo de array em C:

#include<stdio.h>
#include<conio.h>
int main(void)
{
  float notas[5] = {7, 8, 9.5, 9.9, 5.2};
  // declarando e inicializando o vetor notas

  printf("Exibindo os Valores do Vetor \n\n");
  printf("notas[0] = %.1f\n", notas[0]); // imprime 7
  printf("notas[1] = %.1f\n", notas[1]); // imprime 8
  printf("notas[2] = %.1f\n", notas[2]); // imprime 9.5
  printf("notas[3] = %.1f\n", notas[3]); // imprime 9.9
  printf("notas[4] = %.1f\n", notas[4]); // imprime 5.2

  getch();
  return 0;
}

Podemos pensar no vetor (também conhecido como array) como uma variável com páginas, onde sempre começamos da página 0 e podemos ir até o número de páginas que determinamos quando o declaramos. Essa é uma restrição importante sobre o array; na maioria das linguagens, você precisa definir o tamanho dele assim que o declara. No caso acima, se tentássemos atribuir ou imprimir um valor para a posição 5, que corresponderia à sexta nota, receberíamos uma exceção de índice fora dos limites do vetor, pois nesse caso o limite é a posição 4. Essa exceção em inglês é comumente traduzida como: index out of bounds exception.

Listas Encadeadas

Vou tentar ser o mais sucinto possível, sem deixar de abordar detalhes importantes para que possamos compreender a implementação das listas encadeadas em cada um dos exemplos.

Em todos os exemplos utilizarei o mesmo conceito de caixas, onde, ao abrirmos essa caixa, iremos validar se existe uma chave através do atributo temChave. Enquanto não encontramos, continuaremos abrindo as próximas caixas, ou, até não houver mais caixas.

Decidi escrever o nome das variáveis e os comentários em português para que os exemplos fossem mais acessíveis. Além disso, utilizei um laço de repetição para não dar spoilers sobre o Capítulo 3 do livro, que trata de recursividade.

Começando pelo exemplo que acredito ser o mais simples, utilizando POO, através de uma Classe que possui a si mesma como um dos tipos de atributo.

Exemplo em POO utilizando JAVA

//Estrutura das caixas
class Caixa {
  boolean temChave;
  Caixa proximaCaixa;
}

class Main {
  public static void main(String[] args) {
    //Criando as Caixas
    Caixa primeiraCaixa = new Caixa();
    primeiraCaixa.temChave = false;
    Caixa segundaCaixa = new Caixa();
    segundaCaixa.temChave = false;
    Caixa terceiraCaixa = new Caixa();
    terceiraCaixa.temChave = true;
    Caixa quartaCaixa = new Caixa();
    quartaCaixa.temChave = false;

    // Criando lista encadeada
    primeiraCaixa.proximaCaixa = segundaCaixa;
    segundaCaixa.proximaCaixa = terceiraCaixa;
    terceiraCaixa.proximaCaixa = quartaCaixa;

    Caixa caixaAberta = primeiraCaixa;

    //inicializamos com 1 porque começamos com a primeira caixa aberta
    int contador = 1;

    // Abrindo as caixas enquanto houver não encontrar a chave, ou até acabarem as caixas
    while(!caixaAberta.temChave && caixaAberta != null){
      contador++; // contador = contador + 1;
      caixaAberta = caixaAberta.proximaCaixa;
    }

    System.out.println(contador);
  } 
}

O retorno do código acima será 3, porque mesmo que exista uma caixa dentro da terceira, ela tem a chave, portanto, cumpre a nossa condição.

A magia acontece no trecho caixaAberta = caixaAberta.proximaCaixa;. Onde a caixaAberta passa a ser a próxima caixa, que por sua vez, possui uma próxima caixa, e por aí vai.

Exemplo em POO utilizando Python

class Caixa:
    def __init__(self, tem_chave, proxima_caixa=None):
        self.tem_chave = tem_chave
        self.proxima_caixa = proxima_caixa

# Criando as Caixas
primeira_caixa = Caixa(False)
segunda_caixa = Caixa(False)
terceira_caixa = Caixa(True)
quarta_caixa = Caixa(True)

# Criando lista encadeada
primeira_caixa.proxima_caixa = segunda_caixa
segunda_caixa.proxima_caixa = terceira_caixa
terceira_caixa.proxima_caixa = quarta_caixa

caixa_aberta = primeira_caixa

# Inicializamos com 1 porque começamos com a primeira caixa aberta
contador = 1

# Abrindo as caixas enquanto houver não encontrar a chave, ou até acabarem as caixas
while caixa_aberta is not None and not caixa_aberta.tem_chave:
    contador += 1
    caixa_aberta = caixa_aberta.proxima_caixa

print(contador)

O exemplo é muito parecido, mudando levemente a sintaxe utilizada. Nesse momento, vamos apenas contemplar a diferença na limpeza e elegância do Python sem {}();. Eu gosto hihi

Exemplo em Programação Estruturada utilizando C

#include <stdio.h>
#include <stdbool.h>

// Definição da estrutura Caixa
typedef struct Caixa {
    bool temChave;
    struct Caixa* proximaCaixa;
} Caixa;

int main() {
    // Criando as Caixas
    Caixa caixas[4];
    //Inicializando cada caixa com a referência da próxima "& "
    caixas[0] = (Caixa){false, &caixas[1]};
    caixas[1] = (Caixa){false, &caixas[2]};
    caixas[2] = (Caixa){true, &caixas[3]};
    caixas[3] = (Caixa){true, NULL};

    Caixa* caixaAberta = &caixas[0];

    // Inicializamos com 1 porque começamos com a primeira caixa aberta
    int contador = 1;

    // Abrindo as caixas enquanto houver não encontrar a chave, ou até acabarem as caixas
    while (caixaAberta != NULL && !caixaAberta->temChave) {
        contador++; 
        caixaAberta = caixaAberta->proximaCaixa;
    }

    printf("%d\n", contador);

    return 0;
}

Deixei o exemplo ligeiramente diferente. Note que dessa vez estou utilizando uma struct em C no lugar da classe, e as Caixas são representadas por um vetor de 4 posições. Ao contrário do que fiz no Java, inicializo as caixas já com a referência da próxima. Isso é possível porque utilizamos ponteiros e guardamos o endereço de memória daquela variável ao invés do valor. Para não me estender muito nesse universo, irei deixar esse link, para que você possa conhecer mais sobre ponteiros.
O Vetor nesse caso é apenas para simplificar os nomes das caixas, ao invés de primeiraCaixa, segundaCaixa e etc, utilizei um vetor com caixa[1], caixa[2], caixa[n]...
Apesar disso, continuo usando a referência dentro de cada caixa, para chegar na caixa seguinte, através do caixaAberta = caixaAberta->proximaCaixa;.

Porém o resultado permanece 3, pois a execução é a mesma da anterior.

Exemplo em Programação Funcional utilizando Clojure

Deixei o meu preferido para o final. Não se assuste e nem se frustre por não entender esse código logo de cara.
Existem várias particularidades no dialeto LISP, que são diferentes das linguagens baseadas em C, como C#, Java, JavaScript e até mesmo Python.
Você também estranhará o uso de hífen, ponto de interrogação e dois pontos, mas isso é comum nas convenções do Clojure.

; criando um mapa chave e valor para cada caixa
(def quarta-caixa {:tem-chave? false
                  :proxima-caixa nil});

(def terceira-caixa {:tem-chave? true
                  :proxima-caixa quarta-caixa});

(def segunda-caixa {:tem-chave? false
                  :proxima-caixa terceira-caixa});

(def primeira-caixa {:tem-chave? false
                    :proxima-caixa segunda-caixa});

; função que abre as caixas
(defn abrir-caixa 
  [caixa contador]
  ; Se tem chave imprime o contador, senão abre a próxima caixa e incrementa 1 ao contador
  (if (:tem-chave? caixa)
    (print contador)
    (recur (:proxima-caixa caixa) (inc contador))))

; incializa a operação pela primeira caixa
(abrir-caixa primeira-caixa 1)

Nesse exemplo não tive como fugir da recursividade, uma vez que o Clojure é principalmente baseado em funções.

Clojure é uma linguagem interpretada que executa suas aplicações com base na JVM (máquina virtual Java). Portanto, não podemos utilizar um símbolo que ainda não foi criado. Por isso, comecei pelas caixas internas para referenciá-las na caixa anterior.
Sim, os comentários de uma linha utilizam o caractere ; hihi.

Mesmo não entendendo completamente, nada te impede de abrir o replit e fazer alterações no código acima para ver o que acontece hihi

Ficamos por aqui

Espero que os exemplos possam ter te ajudado a visualizar um pouco as listas na prática. Apesar dos exemplos em C e Clojure, acredito que compreender bem o primeiro exemplo em Java ou Python já é mais do que suficiente para entender como as listas encadeadas funcionam e como manipulá-las.

Agradeço a todos que chegaram até aqui e peço, por favor, que me ajudem com seu feedback. Comentem se os exemplos foram claros ou se sentiram falta de algum ponto que não abordei. Ficarei feliz em ajudá-los!