Ao longo da minha leitura do Entendendo Algoritmos, eu tenho revisitado muitos conceitos e técnicas que eu já havia me esquecido que existiam e algumas que eu nunca consegui entender (até agora haha). Dentro desse post (e em mais alguns outros q vão vir ao longo da minha leitura) eu vou trazer esses conceitos sob uma análise de estudos pessoais.

O que eu preciso saber sobre 'memória'?

Bem... o mais simples de tudo é que a memória armazena informações. Mas, como ela faz isso?

Imagine que você quer ir no cinema assistir o último lançamento. Ao comprar seu ingresso, tem uma seleção de assentos disponíveis para você escolher. Você seleciona o seu, finaliza a compra e recebe o código do seu assento.

A memória funciona da mesma maneira! Você precisa armazenar algo, dentre os espaços disponíveis um é selecionado e você recebe um código falando qual espaço foi o escolhido.

O código retornado é chamado de endereço.

O espaço escolhido é chamado de slot.

Arrays x Listas Encadeadas

Agora que entendemos 'memória' vamos nos aprofundar um pouco em 'Listas'.

Simplificando, 'Listas' é quando você precisa armazenar mais de um elemento na memória. Por exemplo, ao invés de você ir só ao cinema, vai você e mais 3 amigos. Um único assento já não dá para todo mundo, vão precisar de mais!

Mas, qual tipo de 'Lista' eu escolho? Um Array ou uma Lista Encadeada?

Bem... depende de qual problema você quer resolver.

Vamos entender melhor!

Arrays

Quando utilizamos um array, significa que colocamos todas as nossas informações em slots um do lado do outro (contiguamente). Como se no cinema, sentasse você e seus amigos na mesma fileira, um do lado do outro.

Mas isso acaba virando um problema quando aparece mais 2 amigos de surpresa e não tem mais espaço na fileira. Então, se ainda quiserem ficar todos juntos, todo mundo vai ter que mudar de lugar. E, isso demora.

Mas tem duas formas de resolver esse problema. O primeiro é comprando ingressos a mais (reservando locais extras na memória). Mas, caso ninguém extra apareça, vai ser um disperdício. Ou pior, se aparecer mais gente do que você havia antecipado. Vai ter que mover todo mundo de novo.

E a outra maneira é sentar em locais separados um dos outros. Assim todo mundo consegue ver o filme, sem precisar ficar movendo de fileira caso mais alguém apareça. Portanto, fazer uso de uma lista encadeada.

Listas encadeadas

As listas encadeadas podem estar em qualquer lugar da memória. Cada um dos itens armazena o local do item seguinte e dessa forma, eles estão conectados em cadeia.

Com elas, você não precisa ficar movendo seus itens caso precise armazenar mais coisas do que havia previsto.

Observações importantes

Listas encadeadas são boas quando:

• Você quer ler todos os itens da sua lista;
• Você quer priorizar inserção/deleção do que leitura;
• Você precisa inserir algo no meio da lista.

Arrays são bons quando:

• Você quer acessar itens aleatórios da sua lista;
• Você quer priorizar leitura do que inserção.

Ordenação por seleção

Vamos para a prática!

Imagine que você tem uma lista de livros, e você categorizou eles com notas de 0 à 10. Você gostaria de ordenar essa lista do seu livro favorito, para o menos favorito.

Uma forma de fazer isso é pegando seu livro mais bem avaliado e colocando em uma outra lista. E fazendo isso até sua primeira lista não ter mais itens. No final, você vai ter uma lista ordenada pelo critério que você queria.

O tempo para isso ser executado é de O(n²).

A ordenação por seleção vai resolver o seu problema, mas ele não é um algoritmo rápido.

Como implementar?

Referências

• Entendendo Algoritmos
• Desvendando Arrays e Listas Encadeadas