O mapa do avançado: estruturas guardam, algoritmos agem

Duas famílias que se cruzam

Uma boa forma de guardar o curso na cabeça é enxergar dois grupos de aulas que conversam o tempo todo. De um lado, as estruturas de dados: formas de guardar a informação. A pilha guarda com a regra do último a entrar, primeiro a sair. A fila guarda com a regra do primeiro a entrar, primeiro a sair. A lista ligada guarda numa corrente de nós. A árvore guarda em hierarquia, com raiz e ramos. A tabela hash guarda para encontrar por chave quase instantaneamente. O grafo guarda relações, uma rede de pontos conectados. Cada estrutura é boa para um jeito de acessar os dados, e conhecer esse cardápio é meio caminho para escolher bem.

Do outro lado estão os algoritmos: os métodos que agem sobre a informação guardada. A busca em largura explora uma rede por camadas. A busca em profundidade vai fundo primeiro e volta quando trava. A ordenação eficiente arruma listas enormes com poucos passos. A memoização guarda resultados já calculados para não refazer trabalho. O backtracking tenta um caminho e recua quando não dá. Repare que muitos algoritmos precisam de uma estrutura para funcionar: a busca em largura anda de mãos dadas com a fila, a busca em profundidade com a pilha. Estrutura e algoritmo formam pares naturais.

A ordem da trilha: do simples ao mais geral

As estruturas não aparecem em ordem aleatória no curso. Elas seguem uma progressão do modelo mais simples ao mais geral, onde cada uma prepara a seguinte. Começamos pela pilha e pela fila, que são listas com uma regra de acesso restrita e fácil de entender. Depois vem a lista ligada, que mostra os dados como uma corrente de nós conectados. Dessa ideia de nós conectados nasce a árvore, que é uma hierarquia de nós, cada um com filhos. E, generalizando ainda mais, chega o grafo: uma rede de nós conectados sem a restrição de hierarquia, onde qualquer ponto pode se ligar a qualquer outro, inclusive formando ciclos. A árvore, aliás, é um caso particular de grafo. Ir do simples ao geral faz cada conceito se apoiar no anterior.

A dupla certa resolve o problema

O grande objetivo por trás desse mapa é treinar seu olhar para juntar as duas famílias diante de um problema real. Precisa achar o caminho mais curto num labirinto? Isso pede um grafo (a estrutura das ligações) com uma busca em largura (o algoritmo que explora por camadas). Precisa desfazer ações num editor de texto? Uma pilha resolve, porque desfazer é sempre o último a entrar, primeiro a sair. Precisa encontrar um cadastro por nome numa base gigante, na hora? Uma tabela hash. Precisa arrumar uma lista enorme? Um algoritmo de ordenação eficiente. Note que a pergunta certa nunca é só qual estrutura ou só qual algoritmo, e sim qual dupla. Quando o problema aparece e sua cabeça já sugere a combinação, você aprendeu a projetar.