Entendendo Arrays e Listas

Certamente, durante o estudo de qualquer linguagem de programação, você irá esbarrar em duas das estruturas de dados básicas porém primordiais: Arrays e Listas. Talvez a dificuldade em entender essas estruturas de forma concreta seja uma experiência comum compartilhada por todos os iniciantes na programação, grupo no qual me incluo. Neste artigo, espero ajudar você, que assim como eu, teve ou tem dúvidas sobre essas estruturas e suas diferenças.

Se você quiser uma resposta simples, porém funcional, a palavra-chave é flexibilidade. A principal diferença entre essas duas estruturas está em quão dinâmico e flexível você pode trabalhar com elas. Enquanto os arrays sofrem da famosa 'síndrome de Gabriela':

'Eu nasci assim, eu cresci assim e vou viver sempre assim..."

Já que uma vez que o array é criado e seu tamanho escolhido, ele não pode ser alterado. Portanto, se você instanciou o seu array com 10 índices, ele permanecerá com esse tamanho fixo até ser descartado, sem encolher ou aumentar.

Trabalhar com listas tem uma abordagem bem diferente. Elas possuem dinamismo e flexibilidade no seu uso, permitindo adicionar e remover elementos à vontade, sem impor obstáculos. Elas têm tamanho dinâmico.

Talvez você esteja pensando: "Então é simples, é só usar listas para armazenar e recuperar meus elementos e terei o melhor dos mundos". Na verdade, não é bem assim. Como mencionei antes, essa é a forma simples de responder à diferença entre essas estruturas. Os detalhes do comportamento em diferentes situações influenciam muito a escolha entre elas, e são esses detalhes que quero explicar para que, quando você se deparar com a necessidade de usar alguma delas, possa escolher conscientemente, levando em consideração suas vantagens e desvantagens.

Memória e seu funcionamento

Primeiramente é importante que você entenda mesmo que de forma superficial, o funcionamento da memória. Pra isso usarei o que na minha opinião é o melhor e mais claro exemplo possível, do qual primeiro escutei na aula sobre variáveis do grande Gustavo Guanabara, então vamos lá.

Imagine que você tem uma cômoda onde cada gaveta só pode armazenar um item:

Você guarda dois itens :

Bhargava, A. Y. Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos.

Pronto, você tem ali armazenado o conteúdo desejado para ser usado num futuro próximo, quando precisar. Grosso modo, é assim que a memória lida com variáveis no seu computador quando você está escrevendo seu algoritmo.

Você pede ao computador um lugar onde o elemento pode ser armazenado e o mesmo lhe retorna o endereço do slot disponível para uso:

E quando se trata de Arrays e Listas? Como o computador lida com isso?

Existe uma grande diferença em como ambas se alocam na memória, lembra da falta de flexibilidade dos arrays? Aqui mora a razão desse comportamento.

Vamos supor que quero criar um array de 5 posições:

Os slots com círculo significam que a memória está livre, e os vermelhos significam que são memórias já em uso.

Perceba que os 5 elementos foram alocados de forma contígua (um ao lado do outro), o que permite que a estrutura conheça os valores e seus índices respectivamente. E se eu quisesse adicionar mais um elemento? O espaço ao lado está ocupado, então, se eu quiser adicionar esse sexto elemento, terei que realocar todo o array para um endereço de memória onde todos os elementos possam ficar lado a lado.

Para deixar mais claro, imagine que você vá ao cinema com 5 amigos. Vocês encontram uma fileira onde todos podem sentar juntos, 5 cadeiras uma ao lado da outra. De última hora, um colega chega atrasado. Você não quer deixar seu amigo isolado, certo? Então, todos precisam se levantar e encontrar uma fileira com 6 lugares disponíveis. E se mais um colega atrasado chegar? Tudo se repete. Percebe como é custoso?

O mesmo acontece com arrays. Você pode até pensar: "Então seria melhor alocar 10 espaços de uma vez, por garantia, já que planejo usar 5". Mas, e se você não usar? Seriam 5 slots reservados inutilmente, já que, uma vez reservados, ninguém mais pode utilizá-los.

E com as Listas? Como funciona?

Para mostrar isso eu irei alocar os mesmos 5 elementos com só que dessa vez usando uma lista:

Veja como é diferente! Nas listas, ao alocar um elemento em um slot de memória, ele aponta para o endereço de memória do próximo valor contido na lista. O primeiro elemento armazena seu valor e aponta para o endereço de memória do segundo elemento, que faz o mesmo com o terceiro, e assim por diante. Por isso, trabalhar com listas é mais dinâmico: para adicionar um novo elemento em qualquer posição, basta que o valor anterior aponte para o novo elemento, e pronto! Ele já faz parte da estrutura.

Complexidade e notação Big O

Agora que temos uma breve noção de como a memória funciona ao lidar com listas e arrays, podemos dar o próximo passo: entender a complexidade dessas estruturas usando a notação Big O. Mas o que é a notação Big O?

A notação Big O descreve o desempenho de um algoritmo, estimando quantas operações ele realiza no pior cenário possível para alcançar o resultado esperado.

De forma mais técnica, a notação Big O é uma forma de descrever a complexidade de algoritmos, focando no seu tempo de execução e como esse aumenta em relação ao tamanho da entrada. Ela fornece uma estimativa do pior caso, ignorando constantes e termos de menor ordem. Este é um tópico bastante complexo, que renderia facilmente dois ou mais artigos extensos só sobre ele. Recomendo que você procure mais materiais, pois aqui explicarei apenas o essencial para entender o nosso tópico principal.

Por que não simplificamos e usamos o tempo de execução em milissegundos ou segundos? Imagine que eu diga que um algoritmo levou 1 minuto e 30 segundos para ser executado. Certo, mas em qual computador esse algoritmo foi executado? Qual processador foi utilizado? Algum outro processo estava rodando ao mesmo tempo? O computador estava minerando Bitcoin?

Percebe por que essa não é uma forma ideal de medir a performance de um algoritmo? Existem muitas variáveis de ambiente que podem fazer esse tempo variar bastante entre execuções.

Para avaliar o desempenho de arrays e listas, precisamos conhecer apenas as complexidades O(1), que significa que no pior caso o algoritmo realiza apenas uma operação (instantânea) para atingir o resultado esperado, e O(n), que significa que o algoritmo realiza n operações (sendo n o tamanho da entrada de dados) para atingir o resultado.

Nos arrays, temos uma complexidade O(1) para a leitura de elementos, devido à sua alocação contígua na memória, o que permite conhecer a posição de todos os elementos pelos seus índices. Suponha que você tenha um array de 2000 posições e queira acessar o índice 753: o array sabe exatamente onde ele está e o retorna em uma única operação. Mas, e para inserções? Aqui, a complexidade é O(n), porque, para adicionar um novo valor, todos os elementos precisam ser realocados, um a um.

Nas listas, ocorre o inverso. Como a lista não sabe onde estão os valores, para acessar uma posição aleatória, é necessário percorrer os elementos um por um até encontrar o desejado. O pior cenário seria se o elemento estivesse na última posição, exigindo uma complexidade O(n). Para inserções, porém, a lista tem vantagem: como os elementos não precisam estar contíguos, basta atualizar os ponteiros, o que resulta em uma complexidade O(1).

Conclusão

Com tudo o que vimos, podemos perceber que ambas as estruturas possuem vantagens e desvantagens, dependendo da complexidade de suas operações. Portanto, basta analisar a situação e fazer a pergunta simples:

Neste caso o que será mais comum? Inserções e deleções? Ou somente leitura?

Com essa resposta e com o conhecimento deste artigo, você poderá escolher conscientemente qual estrutura, array ou lista, será a mais eficiente para a sua necessidade.