Voltei 😛  Depois de um longo recesso do blog, estou de volta (e espero permanecer na ativa durante todo esse ano).

Decidi começar esse ano falando sobre um tópico muito importante para todos os que se dizem desenvolvedores de software: Estrutura de Dados!  Na verdade vou falar sobre um ponto muito específico de estrutura de dados, mas antes vamos dar uma geral sobre estrutura de dados em si.

Primeiro de tudo, o que é estrutura de dados? Uma estrutura de dados é uma forma de organizar e armazenar dados, de forma que eles possam (os dados) ser usados de forma eficiente. Atenção para a palavrinha EFICIENTE, daqui a pouco retornaremos a ela.

Como sabemos (ou deveríamos saber), existem diversas formas de estrutura de dados, cada uma com suas particularidades, pontos positivos e negativos. Se você conhece as estruturas de dados existentes, saiba que não é suficiente saber isso. É obrigação nossa saber qual a melhor estrutura de dados para ser utilizada em cada momento e para cada tipo de situação ou cenário. E é exatamente aí que a palavra EFICIENTE entra. Você precisa saber qual a mais eficiente para determinadas situações. Isso que vai diferenciar você de um programados comum.

Nesse post eu queria falar sobre duas estruturas muito usadas: as LinkedLists e os Arrays Dinâmicos.

Linked List é uma estrutura de dados onde os registros de dados estão organizados de forma que um elemento tem uma referência para o próximo elemento (ou uma referência para o nó de anterior e também para o nó posterior no caso das listas duplamente ligadas). Essa estrutura é importantíssima, e ela que provê uma implementação simples para outras estruturas de dados abstratas como fila, pilha e outras.

Já os arrays dinâmicos são arrays que possuem tamanho variável, e que assim como os arrays, possibilitam o acesso aleatório a qualquer elemento desse array. Um exemplo de array dinâmico é o nosso ArrayList de Java.

Bom, vamos agora ao que interessa, qual dos dois é mais eficiente? Quais pontos positivos de cada um deles? Quais os pontos negativos deles?

Um Array dinâmico é uma estrutura de dados que aloca os elementos continuamente na memória, e guarda o número atual de elementos. Se o espaço reservado for excedido, ele é realocado (e possivelmente copiado), o que é uma operação custosa.

As Linked Lists possuem algumas vantagens sobre os arrays dinâmicos. A inserção de um elemento em uma posição aleatória é uma operação de tempo constante, enquanto que uma inserção em uma posição aleatória em um array dinâmico vai demandar em média mover metade do array, e no pior caso (inserir na primeira posição) vai demandar mover o array inteiro.

Outra vantagem das Linked Lists é que vários elementos podem ser inseridos ao mesmo tempo (só dependendo da memória disponível), enquanto que o array dinâmico possivelmente iria ultrapassar o espaço reservado para ele (e aí teria o custo adicional de mover o array) e poderia até não ser possível realizar a operação caso a memória estivesse muito fragmentada e não fosse possível alocar o espaço do array dinâmico.

Por outro lado, arrays dinâmicos (e arrays normais) possibilitam o acesso a qualquer elemento com um tempo constante, enquanto que as LinkedLists possbilitam o acesso sequencial (e no caso das listas simples encadeadas só possibilita a navegação na lista em uma direção).  Isso faz com que as linked lists não sejam tão adequadas para aplicações onde é preciso acessar elementos pelo índice rapidamente.

Uma outra desvantagem das Linked Lists é o espaço extra de memória que tem que ser alocada para as referências, por isso que não justifica criar linked lists para tipos pequenos e simples como character ou valores booleanos (porque o tamanho do espaço da referência é maior que o do próprio elemento), e os arrays por outro lado só gastam o espaço de memória do próprio array, sem ter o overhead de armazenar referências.

Nesse tempo de fartura de hardware, talvez nem precisemos nos preocupar com questões de baixo nível como essas, mas é importante conhecer e ficar atento pois talvez você esbarre em um cenário onde você precise utilizar a estrutura de dados mais eficiente!

No final das contas, cada situação que vai dizer qual a estrutura de dados mais adequada para o momento.

(PS. pretendo escrever mais alguns posts ainda sobre alguns tópicos importantes de estrutura de dados)