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(n2).
A ordenação por seleção vai resolver o seu problema, mas ele não é um algoritmo rápido.
Como implementar?
Top comments (1)
Eu não gosto muito do exemplo do cinema para a lista encadeada, já que vocês sentariam todos espalhados, porém ao se percorrer pessoa por pessoa vocês estariam todos na sequência. Mas uma possibilidade é considerar a saída, de forma que as pessoas sentam em qualquer cadeira disponível, mas saem da sala em ordem que não tem a ver com as posições da cadeira.
Só um detalhe para ser um pouco mais preciso, listas encadeadas não são tão boas para inserir itens no meio da lista, na verdade, as implementações de listas duplamente encadeadas usadas hoje em dia são melhores para inserir e remover itens nas pontas (começo ou fim), já que elas precisam ler item por item de uma das pontas até chegar na posição desejada, e no meio são
n/2itens que precisam ser lidos. Enquanto arrays são bons para inserir e remover itens apenas no final, e isso que faz as listas encadeadas serem melhores quando se compara as duas estrutura. Mas essa ideia de listas encadeadas serem boas para adicionar e remover itens nas pontas, tornam elas ótimas como implementações para filas e pilhas.Como um extra, gosto da documentação do Rust, que lista os melhores casos de uso para cada estrutura de dados e diz a complexidade de cada operação para comparação.
Some comments have been hidden by the post's author - find out more