Estruturas básicas que todo desenvolvedor deve conhecer

Last change in quinta-feira, 03 de dezembro de 2020

Esta é a segunda parte do post, sobre estrutura de dados, neste post buscarei me aprofundar um pouco mais nos casos de uso, complexidade de busca, exclusão e inserção de cada estrutura, além de mostrar algumas implementações.

Array List (Lista)

ArrayLists é a estrutura de dados mais usado pelo público em geral, tanto pela facilidade como praticidade que a mesma oferece para resolver os mais diversos problemas. Gostaria de frisar aqui que tantos as listas como as listas encadeadas, ambas são utilizadas para construir outras estruturas um pouco mais complexas. Basicamente uma lista nada mais é do que um vetor, o que isso significa? Um vetor tem um tamanho definido, por exemplo, mesmo quando instanciamos um ArrayList em Java ou em outras linguagens, ainda que não definimos o tamanho da mesma, é definido um tamanho inicial para a mesma, normalmente quando atingimos o número máximo, automaticamente é criado um novo vetor com o dobro de tamanho que passará todos os itens para o novo vetor que agora tem diversas posições livres. É importante perceber que isso tem um preço.

Qual seria exatamente o preço? Cada vez que for necessário criar um novo vetor e passar as informações de um para o outro, isso leva O (N), ou seja, todos os itens serão percorridos e adicionados ao novo vetor, ainda que a linguagem tenha abstraído isso, é isso que se passa por debaixo dos panos, esse é um ponto importante a ser lembrado quando falamos de Arraylist. Se você não entendeu a Big O Notation O (N), sugiro que volte na primeira parte do post.

É importante saber que, ao instanciar uma lista um vetor também é instanciado, as posições na memórias são reservadas um após o outro, dito isso, vamos supor que temos a necessidade de mudar a ordem dos elementos diversas vezes. Talvez um ArrayList não seja o melhor caso de uso, pois cada vez que você precisar inserir um item na quarta posição por exemplo, se a lista está preenchida com 10 posições, será necessário empurrar todos os índices começando da quarta posição até a nona posição, o que pode se tornar algo complicado se tivermos muitos itens.

Repare que o to-do list, tem um tamanho de 3, o próximo index ou espaço na memória já está em uso por algum outro objeto, como citado, anteriormente, se precisarmos de um array de tamanho 5, os três primeiros itens terão que vir para um lugar onde tenha no mínimo 5 espaços livres consecutivos, provavelmente na última linha, normalmente é dobrado o tamanho do array, mas isso pode variar de acordo com a implementação.

Linked List (Listas Ligadas)

Qual seria a principal diferença de um Arraylist para uma Linked List? Diferentemente do Arraylist, Linkedlist não reservam os espaços de maneira consecutivas, ou seja, é um pouco mais flexível quanto a isso, o que cada nó de uma lista guarda é um ponteiro ou referência no caso do Java (há uma sútil diferença nesse caso) para o próximo nó, normalmente as Linked List guardam também o primeiro e o último nó. Uma Linked List pode ser usada quando há mudança constante de posições entre os itens, pois o mesmo teria um custo de O (1), ou seja, tempo constante, em outras palavras, seria extremamente barato, pois seria necessário apenas alterar a referência dos nós. Um ponto a ser levado em consideração é que, não existe busca binária nesse caso, pois os elementos não estão dispostos sequencialmente na memória, busca binária foi explicado anteriormente no primeiro post de sobre estrutura de dados. (link) Ou seja, a busca média normalmente é em O (N), pois será necessário passar por cada nó até achar o item desejado. Importante lembrar que não é possível acessar uma posição específica nessa estrutura de dados.

Stack (Pilhas)

Pilha é uma estrutura interessante. LIFO (Last in First Out – Último a Entrar e Primeiro a Sair), isso é a forma que é tratado os objetos que entram numa pilha. Existe um erro comumente conhecido como StackOverFlow que é basicamente quando é excedido a quantidade de memória da pilha de chamadas alocadas pela JVM. Existem alguns problemas comuns na computação onde o uso da pilha se encaixa perfeitamente na solução.

Nesta imagem é possível ver os principais métodos de uma pilha e como é seu funcionamento na prática.

Queue (Fila)

Pode ser implementada tanto com uma linkedlist quanto com uma lista comum, porém é interessante frisar o que já foi falado anteriormente, o problema da lista em comparação com a lista encadeada, N se tem um ganho maior de flexibilidade quando se usa a linked list, já que os objetos podem ser alocados de maneira relativamente aleatória na memória, sem a necessidade que estejam todos em sequência. Enquanto as pilhas têm um comportamento de LIFO, na fila temos o comportamento de FIFO (First In First Out) é utilizado em serviços de mensageria para manter uma ordem de resposta e também para dar prioridade literalmente como uma fila.

Esta imagem mostra o funcionamento da fila.

As filas tem algumas implementações bem poderosas, como ActiveMQ, RabbitMQ, entre outras, são usadas normalmente em micro serviços e terá post sobre as mesmas e também sobre arquitetura em breve, então fiquem ligados.

Segue abaixo as notações assintóticas das estruturas de dados citadas acima.

As estruturas de dados básicas apresentadas acima são a base de outras estruturas de dados, por esta razão foram apresentadas primeiro. Em breve sairá outros posts sobre outras estruturas de dados que fazem uso da mesma e de outras técnicas conhecidas na ciência da computação, fique ligado no blog e não perca os novos posts!