Desvendando Arrays e Listas encadeadas

Este é o primeiro de uma série de artigos, feito não só para programadores, mas também para curiosos, onde desvendaremos os “segredos” de alguns algoritmos e estrutura de dados, com vários e vários exemplos!
Não vou me aprofundar na implementação (códigos) dos mesmos, mas focaremos no principal, o entendimento.

Vamos começar relembrando, bem superficialmente, o conceito de Memória…imagine que você foi para a academia treinar e precisa guardar as suas coisas no armário antes de começar seus treinos. E algumas gavetas estão disponíveis!

Cada gaveta pode guardar apenas um elemento, e você deseja guardar sua mochila e seu capacete, então você pede para o responsável pelo armário duas gavetas e guarda (insere) seus pertences e ele te retorna a chave dos armários cada uma com sua respectiva numeração. Pronto! É mais ou menos assim que a memória do seu computador funciona, ele se parece com um grande conjunto de gavetas, e cada gaveta tem seu endereço. Fácil não é mesmo?

Cada vez que queremos armazenar um item na memória, pedimos ao gerenciador de memória um pouco de espaço e ele nos dá um endereço no qual podemos armazenar nosso item.

Agora que relembramos como se comporta uma memória, vamos ao ponto desse artigo…

Arrays e Listas encadeadas.

Algumas vezes, precisamos armazenar uma lista de elementos na memória. Vamos supor que estamos desenvolvendo um aplicativo para gerenciar nossos afazeres. E se torna necessário armazenar nossos afazeres como uma lista na memória.

Devemos usar um Array ou uma Lista encadeada? Vamos abordar primeiro o Array, pois assim fica mais fácil a compreensão.

Usar um Array significa que todas as nossas tarefas estão armazenadas contiguamente (uma ao lado da outra) na memória.

Vamos supor que queremos inserir mais uma tarefa. Mas agora a próxima gaveta está ocupada por coisas de uma outra pessoa!

É como se você estivesse indo ao jogo do Atlético Mineiro com seus amigos e encontrasse um lugar para sentar, mas outro amigo chegou e não tem mais lugar para ele. Todos precisariam se mover e encontrar um lugar onde todos coubessem, sem ninguém sobrar sozinho. No caso da lista de tarefas, requisitamos ao computador uma área da memória em que coubesse todas as nossas tarefas, e então as movemos para lá.

Se por acaso, um terceiro amigo chegasse, vocês ficariam sem lugar novamente e todos seriam obrigados a se ordenar mais uma vez! Que incômodo não é mesmo?

Seguindo essa linha de pensamento, adicionar itens a um array será muito lento. Um jeito fácil de resolver isso é “reservando lugares”, mesmo que tenhamos cinco itens na lista, podemos solicitar ao computador dez espaços (gavetas), só para “garantir”. Sendo assim, podemos adicionar dez itens na lista sem precisar mover nada. Vislumbramos então, uma boa maneira de contornar nosso problema, mas precisamos ficar atentos às desvantagens:

• Podemos não precisar dos espaços extras que reservamos, então nossa memória será desperdiçada. Não estamos utilizando a memória, mas ninguém mais pode, o famoso “dono da bola”.
• Também podemos precisar adicionar mais de dez itens a nossa lista de tarefas, então teremos de mover os itens de qualquer forma.

Embora, de certa maneira, seja uma boa forma de contornar o nosso problema, não é uma solução perfeita.

E é aqui que entram as Listas encadeadas, com a missão de resolver nosso problema de adição de itens.

Nas listas encadeadas, nossos itens podem estar em qualquer lugar da memória. Cada item armazena o endereço do próximo item da lista, ligando um monte de endereços aleatórios de memória.

É uma espécie de caça ao tesouro. Vamos ao primeiro endereço e ele nos diz “Vá até o endereço X que o próximo item será encontrado”, então vamos até o endereço X e ele diz “O próximo item poderá ser encontrado no endereço Y” e assim por diante.

Lista encadeada

Adicionar um item a uma lista ordenada é fácil: colocamos em qualquer lugar da memória e armazenamos o endereço do item anterior!

Voltando ao problema do jogo do Atlético Mineiro, usar uma lista encadeada seria como dizer “vamos nos dividir e assistir ao jogo”. Se existir espaço na sua memória, você terá espaço para sua lista encadeada.

Mas agora, você deve estar se perguntando “Se as listas encadeadas são muito melhores para inserções, para que servem os arrays?”

Arrays vs Listas

Todo mundo já se deparou, em algum momento, com websites que nos apresentam listas “top 10” de um Xpto assunto. Estes websites utilizam uma tática, um tanto “trapaceira”, para conseguir mais clicks e por consequência mais visualizações. Ao em vez de nos apresentar toda a lista em uma única página, é colocado um item em cada página e nos obrigam a clicar em “próximo” para ler o item seguinte.

Por exemplo, “Os 10 melhores vilões de filmes”, não estarão listados em uma única página, em vez disso, começará pelo #10 (Alien) e seguiremos clicando em “próximo” até chegarmos no tão esperado #1(Darth Vader). Convenhamos, é extremamente chato ter que ficar clicando, mas para o site, essa técnica fornece dez páginas inteiras para incluir anúncios e gerar ainda mais $$$.

Como nem tudo são flores, listas encadeadas tem um problema similar. Suponhamos que você queira ler o último item de uma lista encadeada. Você não pode fazer isso porque não sabe seu endereço, então é preciso ir ao item #1 para pegar o endereço do item #2, ir ao item #2 e pegar o endereço do item #3 e assim por diante, até conseguir o endereço do último item. Listas encadeadas são ótimas se sua intenção é ler todos os itens da sua lista, para encontrar o seu item desejado, mas se você quiser ler apenas um item de seu interesse…elas são horríveis!

Com o array é diferente, pois você sabe o endereço de cada item. Por exemplo, suponhamos que seu array tenha dez itens e você sabe que o primeiro está no endereço 0. Qual é o endereço do décimo elemento?

Está no endereço 9!

Os arrays são ótimos se é de seu interesse ler elementos aleatórios, pois pode encontrar qualquer elemento instantaneamente. Na lista encadeada, os elementos estão separados um do outro, então não é possível calcular instantaneamente a posição de um elemento na memória, sendo necessário ir ao primeiro elemento para então encontrar o endereço do segundo elemento, fazendo isso até chegar ao elemento desejado.

O que nos faz necessário agora, entender a terminologia…

Os elementos em um array são numerados. Numeração essa que começa no 0 e não no 1. Neste array, por exemplo, o número 02 está na posição 1 e o número 01 está na posição 0.

Isso costuma confundir bastante a cabeça de novos programadores, mas quase todas as linguagens de programação começaram os arrays numerando o primeiro elemento como 0. Se você é novo nesse mundo, não se preocupe, logo você se acostuma!

A posição de um elemento também é chamada de índice, portanto, você pode se deparar com “o número 02 está na posição 1” e também “o número 02 está no índice 1”

Chegamos agora a um ponto que nos faz necessário quantificar e comparar tempos de execução para operações, para podermos comparar e tomar nossas decisões corretamente, temos que entender de Notação Big O.

Em resumo se trata de uma notação especial que diz o quão rápido é um algoritmo. Abaixo temos cinco tempos de execução Big O, que você encontrará bastante, ordenados do mais rápido para o mais lento:

• O (log n), também conhecido como tempo logarítmico;
• O(n), conhecido como tempo linear;
• O(n * log n);
• O(n²);
• O(n!);

Não vou me aprofundar mais do que isso, para não ficar quilométrico esse artigo, mas aqui está um link com uma explicação mais sucinta sobre o assunto: https://medium.com/@valadaresotavio/https-medium-com-otaviopvaladares-entendendo-o-big-o-9cb55297d2f8

Abaixo está o tempo de execução para operações comuns de arrays e Listas encadeadas:

Vamos fazer um exercício mental agora, vamos supor que você esteja criando um aplicativo para acompanhar suas finanças! (ignorando o fato de que você está tão fodido quanto eu e que temos algo para acompanhar kk)

1. Compras de supermercado
2. Mensalidade da academia
3. Mensalidade da Faculdade

Todos os dias você anotará tudo o que você gastou e onde gastou. No final do mês, você deverá revisar os seus gastos e resumir o quanto gastou. Logo, terá um monte de inserções e poucas leituras! Você deverá usar um array ou uma lista para implementar este aplicativo?

Neste caso, você está adicionando despesas todos os dias e lendo apenas uma vez no mês. Arrays tem leitura rápida O(1), mas inserção lenta O(n). Listas encadeadas tem leitura lenta O(n) e rápida inserção O(1). Como você terá bem mais inserções do que leituras, faz mais sentido usar uma lista encadeada. Além disso, listas encadeadas tem leituras lentas apenas quando acessamos elementos aleatórios na lista. Nesse caso, como leremos todos os elementos da lista, a lista encadeada também terá uma boa leitura! Se tornando assim, a sua melhor opção.

Até então, fizemos inserções apenas no começo da lista, mas e quanto a inserções no meio da lista?

Imagine agora que sua lista de tarefas se pareça mais com um calendário. Antes, você adicionava os itens ao final da lista e agora quer adicionar suas tarefas na ordem em que elas devem ser realizadas.

O que seria melhor para inserir elementos no meio de uma lista: arrays ou listas encadeadas?

Usando listas encadeadas, basta mudar o endereço para o qual o elemento anterior está apontando.

Já para arrays, você deve mover os itens que estão abaixo do endereço de inserção. E se não houver espaço, pode ser que seja necessário mover tudo para um novo local! Por isso, listas encadeadas são melhores caso você queira inserir um elemento no meio de uma lista.

Até aqui, falamos apenas de inserções, mas e as deleções?

E se você quiser deletar um elemento? Novamente, é mais fácil usando listas encadeadas, pois é necessário mudarmos apenas o endereço para o qual o elemento anterior está apontando. Já nos arrays, é preciso mover os demais elementos quando um deles é removido.

Abaixo estão os tempos de execução para as operações mais comuns em arrays e listas encadeadas.

Vale a pena alertar que inserções e deleções terão o tempo de execução O(1) somente se pudermos acessar instantaneamente o elemento a ser deletado.

Lucas, qual é o mais usado: arrays ou listas? Obviamente, vai depender do caso em que se aplicam. Entretanto, os arrays são mais comuns porque permitem acesso aleatório. Existem dois tipos de acessos: o Aleatório e o Sequencial.

Acesso Sequencial: Significa ler os elementos, um a um, começando pelo primeiro. Listas encadeadas só podem lidar com acesso sequencial. Se você quiser ler o quinto elemento de uma lista encadeada, primeiro precisará ler os quatro elementos antecedentes para chegar não endereço do décimo elemento.

Acesso Aleatório: Permite que você pule direto para o quinto elemento. Vários casos requerem o acesso aleatório, o que faz os arrays serem mais utilizados, Arrays e listas encadeadas são usados para implementar outras estruturas de dados (explicarei alguns deles em outros artigos).

Mas “peraí” que não acabou, é hora de mais exercícios! (Eu disse que iam ter vários kk)

Vamos supor agora que você esteja criando um aplicativo para anotar os pedidos dos clientes de seu restaurante. Seu aplicativo precisa de uma lista de pedidos. Os garçons adicionam os pedidos a essa lista e os cozinheiros retiram os pedidos dessa lista. Funciona como uma fila. Os garçons colocam os pedidos no final da fila e os chefes retiram os pedidos no começo dela para prepararem os pratos. (Estudaremos mais afundo os conceitos de fila em outro artigo)

Você usaria um array ou uma lista encadeada para implementar essa lista? Isso mesmo, você que disse que é um array errou! Pois muitas inserções estão acontecendo a todo momento, sendo essa uma das vantagens das Listas encadeadas, você não precisa pesquisar ou ter acesso aleatório, pois o cheff sempre pegara o primeiro da fila!

Chega de desenvolver aplicativos, agora vamos analisar um experimento. Imagine que o Instagram guarde uma lista de usuários. Quando uma pessoa X tenta acessar a plataforma, uma busca é feita pelo nome do usuário (claro que não é dessa forma, é um experimento hipotético) e se o nome da pessoa X está na lista, ela pode acessar a plataforma. O instagram tem diariamente milhares de acessos, existindo assim uma grande quantidade de buscas nessa lista. Para fazer essa busca, do nome do usuário, você usaria um array ou uma lista encadeada?

Resposta: Um array ordenado. Arrays nos fornecem acesso aleatório, então você pode selecionar um elemento no meio da lista instantaneamente. Não sendo possível com lista encadeada. Para ter acesso a um elemento central de uma lista encadeada, deve-se iniciar pelo primeiro elemento e ir seguindo os endereços até chegar ao elemento desejado.

Na verdade, o Instagram não usa arrays e nem listas encadeadas para armazenar suas informações. Vamos para mais um rápido exercício mental: Imagine uma estrutura de dados híbrida, constituída de um array de listas ordenadas. Você tem um array com 10 slots e cada slot aponta para uma lista ordenada. Por exemplo, o slot de index O do array aponta para uma lista encadeada que contém todos os usuários que começam seus nomes com a letra A. O segundo slot, de index 1, aponta para uma lista encadeada com os nomes de usuários que começam com a letra B, e assim por diante.

Comparando essa estrutura híbrida com arrays e listas encadeadas, para Buscas será mais lenta que arrays e mais rápidas que listas encadeadas. Para inserções será mais rápido do que arrays e mesma velocidade que as listas encadeadas. Portanto é mais lenta para buscas que os arrays, no entanto, será mais rápida ou igual as listas encadeadas para tudo.

Falaremos mais adiante, em outros artigos, sobre outras estruturas. No mais, isso deve ter te dado uma ideia mais concreta sobre como é possível construir estruturas de dados mais complexas a partir das estruturas mais simples.

Arrays e listas encadeadas são blocos fundamentais para que qualquer programador possa desenvolver seu papel! Servindo de fundação para estruturas mais complexas, que nos permitem presenciar e degustar dessa nova era altamente tecnológica com dados sendo inseridos, deletados e ordenados milhares de vezes por segundo!