Estruturas de Dados

Obs: leia via desktop.

Intro

Talvez um dos assuntos mais batidos no mundo da programação. Mas esse ponto tem uma explicação muito pertinente, a importância e o impacto que a utilização correta de Estruturas de Dados tem no desenvolvimento de software. Aqui pretendo apenas introduzir alguns tópicos a respeito, exemplificar e tentar trazer nitidez para quem ainda se vê confuso no assunto.

Em um nível mais baixo, todo dado armazenado por um programa é representado como uma sequência de bits (0s e 1s). No entanto, esses bits por si só não possuem significado — o que dá sentido a eles é a forma como escolhemos interpretá-los.

É aí que entram os tipos de dados. Um mesmo conjunto de bits pode representar um número inteiro, um caractere ou até parte de uma estrutura mais complexa, dependendo do tipo associado. Além disso, cada tipo possui um tamanho e um formato bem definidos na memória.

Mas apenas definir tipos não é suficiente. Em aplicações reais, raramente lidamos com dados isolados — precisamos organizar múltiplos valores e manipulá-los de forma eficiente.

É nesse ponto que entram as estruturas de dados: elas definem não apenas como os dados são armazenados na memória, mas também quais operações são eficientes sobre eles (como acessar, inserir, remover ou buscar valores).

Para dar ordem a essa abstração, categorizamos as estruturas pela forma como armazenam e processam informações. Entender como elas se comportam fica muito mais simples quando as dividimos por grupos. Neste artigo, focaremos nas duas distinções que mais impactam o dia a dia do desenvolvedor: a estratégia de Alocação e a Linearidade da estrutura.

Alocação

Imagino eu que todo e qualquer programador ou pessoa que esteja lendo esse post tenha uma rasa noção a respeito de Memória. Caso não, recomendo leitura.

No que diz respeito a Alocação de Memória em Estrutura de Dados pode-mos dividir em duas as diferentes formas:

• Alocação Estática ou Tamanho Estático;
• Alocação Dinâmica ou Tamanho Dinâmico (Máquina de Ponteiros).

Alocação Estática

Neste artigo, utilizaremos o termo alocação estática para nos referirmos a estruturas cuja capacidade é definida previamente, antes de seu uso. Isso significa que a memória necessária é reservada antecipadamente para comportar todos os elementos esperados. Em geral, esse modelo envolve o uso de um bloco contíguo de memória e de uma quantidade fixa de posições para armazenamento de dados. Um exemplo clássico de estrutura com essas características são os Arrays

Antes de exemplificar como Estruturas de Dados fazem uso dessa propriedade, permita-me demostrar o que seria conhecer o tamanho de um dado/tipo. Tomemos como exemplo um u32 em Rust (u32 é a notação para inteiro sem sinal de 32 bits). Este tipo possui um tamanho definido 32 bits ou 4 bytes.

Sendo assim, para cada vez que um dado deste tipo é instânciado um bloco com tamanho de 4 bytes é alocado na memória para comportar essa informação. Experimente mudar o valor abaixo e ver como a representação se comporta.

A Esquerda os byte e bits que representam o número em questão. Sendo que cada linha representa um byte e cada 0 ou 1 representa um bit. A direita a maneira como, nos próximos exemplos, pretendo representar a alocação de memória.

Perceba que quão menor o número menos bytes são necessários para representá-lo. O número 42 precisa apenas de 1 byte para ser definido, mas ainda que apenas o primeiro byte contenha informação significativa caso este número seja instânciado como um u32 ele ocupará na memória os 4 bytes respectivos ao tipo.

Através deste tipo podemos representar todos os números de 0 até 4.294.967.295 . Perceba que para o menor caso todos os bits estarão em 0 e para o maior todos estarão em 1.

E como isso nos ajuda?

É bem simples, sabendo o tamanho de cada dado e tendo uma rasa noção da quantidade de dados que serão contidos, podemos facilmente definir um tamanho para comportar esses dados em sua totalidade.

Ainda que os dados venham a ser adicionados ao longo do tempo podemos alocar memória suficiente em uma única operação. Dai o nome Alocação ou Tamanho Estático, pois a ideia é que este tamanho não vá variar de acordo com o tempo, ao menos não é o ideal.

Exemplificando de forma rasa, supondo que desejamos instanciar um Array que comportará dados do tipo u32, esperando que o Array abrigue 5 posições deste tipo de dado. Se para cada posição precisamos de 4 bytes, então basta pedir ao sistema operacional por uma porção de memória de 20 bytes para este Array e teremos espaço suficiente.

Exemplo prático

Vamos simular. Como seria alocar um Array e definir valores para cada item dele. Neste exemplo entenda cada bloco abaixo como um conjunto de 4 bytes, cada um para representar um valor no Array.

Por que esse tipo de alocação pode ser útil?

Em decorrência da alocação sequêncial podemos realizar acessos a quaisquer posições desta estrutura em tempo constante, sem a necessidade de percorrer toda estrutura para chegar na posição desejada.

Para acessar posição de número n desse Array. A partir do endereço do Array desloca-se n - 1 vezes o tamanho em bytes de cada elemento e então lê-se a quantidade de bytes respectiva ao tamanho do elemento.

Supondo um Array de u32 (4 bytes, 32 bits) de endereço 0x7fff94f3f410 para ler a 3ª posição nos deslocamos 8 bytes e chegamos ao endereço 0x7fff94f3f418 e então basta ler 4 bytes a partir deste endereço.

Com todas as posições cheias e se precisasemos de mais um espaço?

O processo de “expandir” a capacidade desta estrutura envolve realizar nova alocação de memória. O que naturalmente foge da premissa da Estrutura de alocar toda a memória que será utilizada previamente e ao decorrer da utilização não necessitar de solicitar ao sistema por mais memória.

Para comportar um ou mais novos elementos, uma nova sequência de memória deve ser alocada, considerando a nova capacidade desejada. Então os dados presentes na atual estrutura devem ser transferidos para a nova alocação e então insere-se o novo elemento.

O que pode acontecer ao tentar?

Depende. Há inumeras variáveis que podem determinar o resultado dessa tentativa, podendo ser desde a linguagem utilizada até mesmo o sistema em que o processo irá executar.

Para entender melhor isso, temos que traduzir essa a operação de “adicionar” esse novo elemento ao Array ao que de fato se trata. Quando adicionamos um valor a uma determinada posição nada mais estamos fazendo do que escrever na verdade trata-se de uma solicitação para escrever num endereço que teoricamente não pertence ao nosso programa.

Vejamos alguns exemplos de códigos que exemplificam isso e os seus respectivos retornos na tentativa de execução. (Removi parte da verbosidade das linguagens e preferi por apenas colocar no exemplo o código que aborda a questão).

Exemplo em Rust:

  let mut array: [u32; 5] = [0; 5];
  array[5] = 6;

λ cargo run
   Compiling ...
error: this operation will panic at runtime
 --> src/main.rs:12:3
  |
7 |   array[5] = 6;
  |   ^^^^^^^^ index out of bounds: the length is 5 but the
index is 5
  |

Esse exemplo não passou da etapa de compilação, o programa nem chegou a ser executado e o compilador identificou que a execução deste código irá resultar em erro e por essa razão não prosseguiu.

E se tentassemos fazer isso em uma linguagem como C?

Exemplo em C:

  int array[5];
  array[5] = 6;

λ gcc example.c && ./a.out
*** stack smashing detected ***: terminated

Em C esse programa compila e ao executá-lo um erro como o demostrado assima é esperado, mas não é garantido. Em C esta ação tem comportamento indefinido e comportamento indefinido nem sempre resulta em erros imediatos.

Em alguns sistemas acessar memória levemente fora do intervalo alocado pode não causar problema algum devido ao layout de memória. Logicamente pra isso a memória em questão não deve pertencer a nenhuma outro processo ou variável do mesmo escopo.

E se tentassemos fazer isso em Javascript?

let arr = Array(5);
arr[5] = 6;
console.log(arr);

λ node example.js
[ <5 empty items>, 6 ]

Em javascript esse código executa sem erro algum. O “Array” é instânciado com 5 posições, ao passo que uma sexta é solicitada a linguagem automaticamente realiza por baixo dos panos as operações necessárias para se adequar e seguir com a execução normalmente.

Se utilizarmos Nodejs como runtime para execução do nosso código Javascript podemos adotar um exemplo utilizando uma estrutura melhor adequada há um Array o Uint8Array que é uma subclasse de TypedArray. Chegamos então ao simples exemplo:

let arr = new Uint8Array(5);
arr[5] = 6;
console.log(arr);

Ao executarmos este código também não obteremos erro.

λ node example.js
Uint8Array(5) [ 0, 0, 0, 0, 0 ]

Porém neste cenário o Nodejs por baixo dos panos não irá realizar o trabalho necessário para criar uma nova estrutura. O que particularmente me parece mais adequado tendo em consideranção o comportamento experado de um Array.

Neste caso é de certa forma injusta a comparação de Javascript com as demais linguagens citadas a cima. Não entrarei nos meritos do porque, mas no geral ambas as linguagens anteriores se propõem a ser linguagens de mais baixo nível, permitindo que os desenvolvedores possam escrever código que seja mais próximo da máquina. Enquanto Javascript é uma linguagem de alto nível que permite que os desenvolvedores escrevam código sem a necessidade de complexidades de baixo nível, porém oferecendo menor controle sobre o algumas questões como memória.

Mas e se dentro do uso desejado não sabemos a quantidade de items que serão comportados e/ou o tamanho destes items?

Neste caso o melhor a se fazer é não utilizar uma Estrutura que faz-uso deste tipo de alocação. Há também Estruturas de Dados qualificadas como de Alocação Dinâmica ou Tamanho Dinâmico. Vejamos mais a respeito.

Alocação Dinâmica

Em contrapartida a alocação estática, nem sempre sabemos quanto de memória será necessário para que todos os dados sejam alocados. A Alocação Dinâmica lida com estes casos e não possui estrutura completamente fixa e pode mudar de acordo com as operações realizadas em tempo de execução.

Mas de que modo a alocação varia?

Majoritariamente uma estrutura que se apoia no modelo de alocação dinâmica trabalha com Nós ou Nodes estes que por sua vez vão conter os dados em tipos primitivos, ou também, muito comumente os Nós são alocados com estruturas de tamanho estático. Além dos dados estes Nós contém ponteiors para endereçar outros nós. Assim a medida que há necessidade de alocar dados estes nós são construidos em mémoria e adereçados à estrutura que no fim trabalha como uma máquiana de ponteiros.

O que seria uma “Maquina de Ponteiros”?

Comumente Estruturas de Dados de Alocação dinâmica são ditas como “Maquina de Ponteiros”. Isso ocorre porque toda a estrutura é construida através de ponteiros. Assim como no exemplo anterior, do Array onde os dados são armazenados em blocos de memória e inseridos no endereço da estrutura na posição desejada no caso da alocação dinâmica também são armazenados em blocos de memória, porém os caso blocos/elemento também armazenaum ou mais ponteiros. Ponteiros armazenam endereços de memória de outros nós para permitir a navegação entre nós.

Ao contrário da simulação anterior, em que toda a memória foi alocada previmanete, na alocação dinâmica a memória é alocada conforme a necessidade. Na instânciação da estrutura apenas uma alocação é necessária a do primeiro ponteiro normalmente chamado de HEAD ou ROOT. Esse ponteiro é usado para apontar para o primeiro elemento da lista quando ele for construído. E assim sucessivamente sempre que um novo elemento for inserido, o ponteiro do último elemento será atualizado para apontar para o novo elemento inserido.

Exemplo prático

Vamos agora simular um exemplo de Lista Encadeada. Nesse exemplo entenda cada bloco abaixo como um conjunto de 4 bytes para representar um valor e 8 bytes para representar um ponteiro, totalizando 12 bytes por elemento. O tamanho do ponteiro varia de acordo com a arquiteutra do sistema operacional (neste exemplo o sistema operacional trabalha com uma arquitetura de 64 bits).

Por que esse tipo de alocação pode ser útil?

Como dito anteriormente, nem sempre sabemos quanto de memória será necessário para que todos os dados sejam alocados. Perceba que neste exemplo a medida que mais “espaço” foi necessário mais “espaço” foi alocado.

Há desvantagens no uso de estruturas de alocação dinâmica?

Apesar de prover liberdade quanto ao tamanho. Essa liberdade tem um custo. Ao passo que na Alocação Estática o tamanho de cada dado alocado era de 4 bytes para o mesmo dado no exemplo tivemos a alocação de 12 bytes.

Outro contraponto, na Alocação Estática podemos fazer acesso aleatório à memória. Dado um Array podemos acessar qualquer posição de memória em tempo constante. No caso da Alocação Dinâmica para chegar a um Nó qualquer precisamos navegar pelos ponteiros até chegar no nó desejado.

Exemplificando de forma suscinta uma fila implementada utilizando uma Lista encadeada

Uma fila segue o padrão FIFO (First in First Out, primeiro a entrar primeiro a sair).

Sendo assim todo o processo de inserção deve ser realizado ao final da Lista encadeada. E todo processo de remoção deve ser realizado ao começo da Lista encadeada.

Otimizações podem ser feitas para melhorar a performance deste exemplo. Como adicionar uma referência na estrutura para o último elemento. Então a estrutra contária com ROOT e TAIL por exemplo. Ao inserir um elemento na Lista encadeada, basta atualizar o ponteiro nó na referência de TAIL para apontar para o novo elemento inserido e após atualizar o ponteiro TAIL para apontar para o novo elemento inserido.

Dessa forma tanto as inserções quanto as remoções são feitas em tempo constante. Sem a necessidade de percorrer toda a Lista encadeada para chegar ao elemento desejado.

Comparativo

Ambas as estruturas tem suas particularidades e casos de uso bem definidos. A diferença entre a alocação altera também a forma como a estruutra é implementada. A alocação dinâmica é mais flexível e pode ser utilizada para representar estruturas mais complexas. Já a alocação estática é mais rígida e é mais adequada para representar estruturas mais simples.

Não somente dessa forma podemos variar na implementação de uma estrutura de dados. Outra forma que também é utilizada para categorização é quanto a Linearidade. Vejamos no próximo tópico a respeito.

Linearidade

Em sequência as diferentes formas de categorizar Estruturas de Dados temos quanto a Linearidade.

No que diz respeito a Linearidade em Estrutura de Dados pode-mos dividir em duas as diferentes formas:

• Linear;
• Não Linear.

Vejamos um pouco mais a respeito de cada uma das formas antes de debater seu impacto.

Linear

Como é dito pelo proprío nome trata-se do tipo de Esturtura de Dados onde os elementos são arranjados de forma sequêncial/linear. Alguns exemplos de estruturas lineares são Arrays, Pilhas, Filas e Listas Encadeadas.

Uma maneira de facilmente identificar uma Estrutura Linear é visualizando como os dados são percorridos. Para toda e qualquer instância de uma Estrutura Linear é possível percorrer todos os elementos da estrutura uma única vez em uma única passagem.

Observe a visualização abaixo:

Perceba que nesse exemplo toda a estrutura pode ser percorrida através de uma única passagem. Começando pelo ROOT e percorrendo até chegar ao último Nó que carrega o valor 3.

E por que usar uma estrutura linear?

Estruturas Lineares são simples e eficientes. Excelentes escolhas para casos emq ue os dados devem ser acessados e processados de forma sequêncial. Operações como agendamento de tarefas através de Filas e implementação da funcionalidade de Desfazer através de Pilhas são exemplos de utilizações de Estruturas Lineares.

Não Linear

Em oposição as Estruturas Lineares neste caso os elementos são arranjados de forma não sequêncial/linear. Exemplos de estruturas não lineares são Grafos, Árvores, Árvores Binárias, Heaps e Tries.

Não é possível percorrer todos os elementos da estrutura uma única vez em uma única passagem para toda e qualquer instância de uma Estrutura Não Linear. Um exemplo no caso de uma Árvore com 3 Nós, uma raiz e duas folhas. A árvore não pode ser percorrida através de uma única passagem a partir da raiz.

Um exemplo que quebra essa regra é o de um Grafo Cíclico apesar de Grafos serem Estruturas Não Lineares, no caso particular do Grafo Cíclico é possível percorrer os elementos através de uma única passagem. Porém trata-se de uma exceção a regra

Note que ao percorrer o grafo acíclico os Nós de valores 1 e 2 são percorridos mais de uma vez. Isso ocorre pois estes Nós são a única conexão dos Nós de valores 4 e 5, então para acessá-los é necessário passar uma vez pelos anteriores e após acessá-los é necessário retornar aos anteriores para dar sequência ao percorrimento da estrutura.

E por que usar uma estrutura não linear?

São muito utilizados para representar dados complexos com hierarquia ou conexões não lineares. Normalmente oferecem busca mais rápida que estruturas lineares. São essênciais para modelar problemas do mundo real. Sistemas de arquivos de sistemas operacionais, redes sociais e navegação através de mapas são exemplos de uso de Estruturas Não Lineares.

Comparativo

Assim como com a distinção entre Estruturas de Dados de Alocação Estática e Alocação Dinâmica as particularidades de cada tipo são bem expressivas. Porém quanto a linearidade a distinção entre casos de uso é menos clara.

Note que apenas para o elemento 0 o caso Linear encontra o valor mais rapidamente, para os casos 1 e 2 a mesma quantidade de saltos é feita, para os demais casos o caso Não Linear performa melhor e assim também segueria para todo e qualquer número adiante.

Ao passo que o número de buscas máximos cresce Linearmente com o tamanho da Lista Encadeada no primeiro exemplo. No segundo a quantidade de máxima de nós percorridos sempre será a profundidade máxima da árvore, e isto cresce de forma Não Linear com a quantidade de elementos da árvore.

Neste exemplo em especifico para a finalidade proposta a utilização de uma Estrutura Não Linear é preferível, tendo em vista a eficiência para resolver o problema. Mas cada caso é um caso e não é necessariamente a melhor solução para todos os casos.

Não quero entrar nos detalhes desse algorimo, trata-se de uma busca em árvore binária, mas se quiserem saber mais sobre o assunto, recomendo leitura sobre em Árvore binária de busca e Árvore AVL

Conclusão

Parte da ideia desse post é introduzir a maneira como eu pretendo representar Estruturas de Dados, Nós, um pouco de Memória e afins. A ideia central não é representar diversas estruturas diferentes de formas diferentes, muito menos me aprofundar no debate a respeito de alguma Estrutura em especifico. Mas apenas falar a respeito do tópico de modo suficiente para dar a entender a representação.

Obviamente o tópico de Estruturas de Dados é muito amplo e não pode ser resumido a esta categorização. Outros fatores são constantemente alvo de discussão e debate como por exemplo custo de inserção/remoção, custo de acesso aleatório, ordenação, mutabilidade e muitos outros. Neste artigo o foco é apenas a representação de Estruturas de Dados. E através dessa representação separar conceitualmente diferentes formas de categorizar Estruturas de Dados.