Estruturas de Dados Básicas com exemplos em C#

Introdução

Uma das principais necessidades de sistemas computacionais é guardar dados e operar sobre eles. Além disso, a quantidade a se guardar e número de operações feitas é bastante considerável. Imagine quantos dados são gerados durante o seu uso nas redes sociais, portanto, é vital entender como fazê-lo eficientemente. Nesse sentido, temos diferentes maneiras de organizar os dados para determinado fim, o que chamamos de estrutura de dados.

Diferentes estruturas de dados são mais performáticas em diferentes cenários. Vamos ver as mais importantes e saber o momento certo de usar cada uma. E, para tornar mais concreto, veremos exemplos de cada uma na linguagem C#.

Arrays e Matrizes

Comecemos pelo mais simples. Array é uma coleção de elementos do mesmo tipo. Podemos acessar, ou modificar, um elemento pelo seu índice, ou sua ordem, no array. Mais comumente criado quando sabemos exatamente o tamanho que o array precisa ter. Já em C#, podemos criar um array de tamanho constante ou de acordo com o valor de alguma variável. Uma coisa bem importante é que o acesso à qualquer elemento de um array é muito rápido. Exemplos:

int[] NewArray(int n)
{
    int[] array = new int[n];
    return array;
}

int[] array = new int[3];

int[] outroArray = {1, 2, 3, 4};

for(int i = 0; i < 4; i++)
{
  //Acessando o valor a partir do índice
    Console.WriteLine(outroArray[i]);
}

outroArray[3] = 99;

for(int i = 0; i < 4; i++)
{
  //Acessando o valor a partir do índice
    Console.WriteLine(outroArray[i]);
}

//Acessar um elemento que não existe gera uma exceção
//outroArray[4] = 100;

Em seguida, temos as matrizes. Basicamente, são arrays multidimensionais. Cada posição do array é um novo array. A ideia é a mesma do array.

int[,] matrix = new int[2,2];
matrix[0, 0] = 1;
matrix[0, 1] = 2;
matrix[1, 0] = 3;
matrix[1, 1] = 4;

for (int i = 0; i < 2; i++)
{
    for (int j = 0; j < 2; j++)
    {
        Console.WriteLine(matrix[i,j]);
    }
}

Também temos os jagged arrays. Podem ser entendidos como arrays de arrays. Cada array pode ter um array de tamanho n.

int[][] jaggedArray = new int[3][];

jaggedArray[0] = [1, 3, 5, 7, 9];
jaggedArray[1] = [0, 2, 4, 6];
jaggedArray[2] = [11, 22];

int[][] jaggedArray2 =
[
    [1, 3, 5, 7, 9],
    [0, 2, 4, 6],
    [11, 22]
];

Fonte: The array reference type - C# reference | Microsoft Learn

Listas e Listas Ligadas

Com os arrays temos uma certa inflexibilidade, pois devemos saber já de cara qual o tamanho que será necessário, mas e nos casos que não sabemos quantos itens iremos guardar, ou se a quantidade irá mudar durante a execução? Para isso temos as listas e listas ligadas.

Listas permitem adicionar elementos com facilidade. O acesso também é rápido, semelhante aos arrays. Por debaixo dos panos, listas, no geral, são implementadas com arrays. Quando se necessita de mais espaço, é alocado um novo array com o dobro de tamanho e todos os elementos são copiados para essa nova estrutura, o que torna a operação mais lenta que o comum. Para remoção, é necessário encontrar o elemento, seja percorrendo ou acessando o índice, e reorganizando os elementos à direita. Similarmente, para encontrar um elemento, sem saber o índice, é necessário percorrê-lo, gastando-se tempo proporcional ao tamanho da lista.

List<int> lista = new List<int>();

lista.Add(1);
lista.Add(2);
lista.Add(3);

Console.WriteLine($"Imprimindo a lista após as inserções");
lista.ForEach(Console.WriteLine);

lista.Insert(1, 99);

Console.WriteLine($"Imprimindo a lista após a inserção do 99");
lista.ForEach(Console.WriteLine);

bool exists = lista.Contains(4);
Console.WriteLine($"O número 4 existe na lista? {exists}");

lista.Remove(1);

Console.WriteLine($"Imprimindo a lista após a remoção do elemento 1");
lista.ForEach(Console.WriteLine);

Já listas ligadas permitem uma adição, remoção e busca mais flexível, mas com um custo de tempo associado. No geral, as operações são mais lentas que as operações numa lista. Por que isso acontece? Vejamos nessa imagem:

Fonte: Lista ligada – Wikipédia, a enciclopédia livre

Uma lista ligada é formada por diversos nós, em cada nó só conhece o próximo vizinho. Temos um campo conhecido como cabeça da lista(do inglês head), que aponta para o primeiro elemento da lista. A partir dessa informação conseguimos entender a causa da dita lentidão em relação à lista: Para adicionar um elemento precisamos percorrer todos os elementos da lista até encontrar um nó que não possui o próximo vizinho. Imagine uma lista ligada com 999 999 elementos, para adicionar o milionésimo, deve-se percorrer todos eles para ao fim ser possível adicioná-lo. Para remoção e acesso, segue o mesmo raciocínio.

Inclusive, existe a lista duplamente ligada, em que cada nó conhece o vizinho anterior e o próximo. E também temos a cabeça e o a cauda(do inglês tail) da lista, facilitando as operações nos cantos da lista.

Em C# a LinkedList é implementada como uma lista duplamente ligada. Além disso, podemos inserir um nó diretamente antes ou após outro nó. O que permite uma inserção rápida quando já tem o nó, mas por outro lado, encontrá-lo necessita de uma busca proporcional ao tamanho da lista. A remoção também é feita dessa forma.

LinkedList<int> listaLigada = new LinkedList<int>();

//Adiciona no início da lista
listaLigada.AddFirst(1);

//Adiciona no fim da lista
listaLigada.AddLast(2);
listaLigada.AddLast(3);

//Imprimindo a lista após as inserções
Console.WriteLine($"Imprimindo a lista após as inserções");
ImprimirListaLigada(listaLigada);

var firstNode = listaLigada.First;
listaLigada.AddAfter(firstNode, 99);

Console.WriteLine($"Imprimindo a lista após a inserção do 99");
ImprimirListaLigada(listaLigada);

bool exists = listaLigada.Contains(4);
//se não encontrar o node, será nulo
var node = listaLigada.Find(4);

Console.WriteLine($"O número 4 existe na lista? {exists}");

listaLigada.Remove(1);
listaLigada.RemoveFirst();

Console.WriteLine($"Imprimindo a lista após a remoção do elemento 1 e o primeiro elemento da lista");
ImprimirListaLigada(listaLigada);

void ImprimirListaLigada(LinkedList<int> listaLigada)
{
    foreach (int node in listaLigada)
    {
        Console.WriteLine(node);
    }
}

Conjuntos e Dicionários

Vamos agora para algumas estruturas de dados mais interessantes para verificação da existência ou não de elementos numa coleção e armazenamento de valores com identificadores.

Primeiramente, os conjuntos são estruturas de dados que guardam elementos únicos. A determinação de unicidade de um elemento é feito por um cálculo de hash, função matemática complicada que gera idealmente um valor único para cada valor de entrada. Normalmente, esse cálculo é feito rapidamente. Então, ao inserir um elemento no conjunto, o hash será calculado e, não havendo repetição, o elemento será inserido. A remoção segue a mesma lógica. Ambos são rápidos.

A partir disso, é perceptível o porquê do conjunto ser uma estrutura de dados interessante quando temos problemas que precisem de unicidade ou verificação se certo elemento está presente: é muito eficiente realizar tal operação.

Comparando as listas com os conjuntos, naqueles o tempo de operação de adição, remoção e busca é proporcional ao tamanho, já nos últimos é um tempo constante - duração do cálculo.

HashSet<int> set = new HashSet<int>();
set.Add(1);
set.Add(2);
set.Add(3);
ImprimirConjunto(set);

Console.WriteLine($"Tentando adicionar 3 no conjunto");
bool added = set.Add(3);

Console.WriteLine($"O valor 3 foi adicionado no conjunto? {added}");
ImprimirConjunto(set);

bool contains = set.Contains(1);
Console.WriteLine($"O valor 1 existe no conjunto? {added}");

void ImprimirConjunto(HashSet<int> conjunto)
{
    Console.WriteLine("{ " + string.Join(" ", conjunto) + " }");
}

Também estão presentes métodos de operações de conjuntos matemáticos, como UnionWith - para união, IntersectWith - para interseção, ExceptWith - para subtração, dentre outros. Sugiro a leitura da documentação para saber mais.

Em seguida, temos os dicionários, que funciona de forma muito semelhante aos conjuntos. A diferença é o dicionário guarda um par de chave e valor. A chave é o identificador do elemento. Aqui também temos o uso da operação de hash, onde age sobre a chave. Ou seja, um elemento será adicionado se a chave não existir. Será removido apenas se a chave existir. E, por fim, será encontrado a partir de sua chave.

Dictionary<string, string> timesEstadios = new Dictionary<string, string>();

timesEstadios.Add("Flamengo", "Maracanã");
timesEstadios.Add("Botafogo-PB", "Almeidão");
timesEstadios.Add("Sport", "Ilha do Retiro");
timesEstadios.Add("Fluminense", "Maracanã");

Console.WriteLine("Times e estádios como mandante");
ImprimirDicionário(timesEstadios);

Console.WriteLine("\n\n");
try
{
    //Adicionar um elemento que já existe causa exceção
    Console.WriteLine("Tentativa de adicionar o Botafogo-PB");
    timesEstadios.Add("Botafogo-PB", "Almeidão2");
}
catch
{
    Console.WriteLine("Tentativa de adicionar elemento que já existe");
}

Console.WriteLine("\n\n");

bool added = timesEstadios.TryAdd("Souza", "Marizão");
if (added)
{
    Console.WriteLine("Sousa adicionado");
}
else 
{
    Console.WriteLine("Sousa não foi adicionado");
}

//Semelhate a fazer desta forma
if (!timesEstadios.ContainsKey("Sousa"))
{
    Console.WriteLine("Sousa não está no dicionário, vamos adicionar");
    timesEstadios.Add("Sousa", "Marizão");
}

Console.WriteLine("\n\n");
Console.WriteLine("Qual estádio do Sport?");
if (timesEstadios.TryGetValue("Sport", out string estadioDoSport))
{
    Console.WriteLine($"Estádio: {estadioDoSport}");
}
else
{
    Console.WriteLine("Sport não está na lista, então não sei.");
}

Console.WriteLine("\n\n");
timesEstadios.Remove("Fluminense");
ImprimirDicionário(timesEstadios);

void ImprimirDicionário(Dictionary<string, string> dicionario)
{
    foreach (var item in dicionario)
    {
        Console.WriteLine($"Time: {item.Key}, Estádio: {item.Value}");
    }
}

Por baixo dos panos, ambas usam arrays como estrutura básica para armazenar os dados. Isso acontece por que a função hash indica idealmente um valor único. Esse valor é usado como índice no array principal, definindo onde o elemento será armazenado.

Um exemplo simples seria um função hash a seguir:

int[] arrayInterno;
int Hash(int n)
{
    //Irá retornar um valor entre 0 e o tamanho do array - 1
    return n % arrayInterno.Length;
}

Nesse sentido, uma boa função hash minimiza a colisão entre entradas diferentes. Mas caso aconteçam, é preciso tratá-las. Exemplos disso seriam:

• Adicionar no próximo índice
• Cada elemento ser também uma lista/array para adicionar as possíveis colisões.

Além disso, é importante que a estrutura também tenha espaço suficiente para guardar os elementos. Quando não há mais espaço, uma nova é alocado e os valores são copiados para o ele.

Filas e Pilhas

Esta estrutura de dados é bem semelhante a uma fila na vida real. Pessoas chegam na fila do supermercado, a que está na frente é atendida primeiro. Depois a segunda é atendida e assim por diante. Temos uma estrutura em que os elementos processados e descartadas são sempre o que estão na primeira posição.

A adição sempre é feita no fim da fila, o que é bem rápido. A remoção também é bem rápida e sempre feito do começo. Já a busca dura proporcionalmente ao seu tamanho. A fila é implementada como um array circular que permite que velocidade

Queue<int> numeros = new Queue<int>();
numeros.Enqueue(1);
numeros.Enqueue(2);
numeros.Enqueue(3);

Console.WriteLine("Inicialmente:");
foreach (var num in numeros)
{
    Console.WriteLine(num);
}

Console.WriteLine("\n");

Console.WriteLine($"Qual o primeiro elemento? {numeros.Peek()}");

Console.WriteLine("\n");

//também retorna o que foi retirado da fila
numeros.Dequeue();

Console.WriteLine("Por fim:");
foreach (var num in numeros)
{
    Console.WriteLine(num);
}

Por fim, mas não menos importante, temos a pilha. Essa estrutura é semelhante a fila. O que muda é a inserção que acontece no topo da pilha. A remoção também é no início. Em termos de velocidade, igual à fila. Por debaixo dos panos, é implementada como uma lista.

Stack<int> numeros = new Stack<int>();
numeros.Push(1);
numeros.Push(2);
numeros.Push(3);

Console.WriteLine("Inicialmente:");
foreach (var num in numeros)
{
    Console.WriteLine(num);
}

Console.WriteLine("\n");

Console.WriteLine($"Qual o primeiro elemento? {numeros.Peek()}");

Console.WriteLine("\n");

//também retorna o que foi retirado da fila
numeros.Pop();

Console.WriteLine("Por fim:");
foreach (var num in numeros)
{
    Console.WriteLine(num);
}

Conclusão e Referências

Este foi uma introdução a um tema bastante exigidos dos desenvolvedores de software. Gostaria de esclarecer que em determinados momentos fui vago em relação à velocidade das operações, pois não quis introduzir também o assunto de análise de algoritmos e Notação O Grande. Possivelmente, posso trazer isso em futuros artigos. Recomendo pra quem interessou buscar mais sobre.

Baseei meu artigo nas aulas que assiste na universidade, na documentação da Microsoft(https://learn.microsoft.com/en-us/dotnet/standard/collections/) e também no curso de Coding Interview feito por Maurício Aniche na Jornada Dev+Eficiente.

Obrigado e até mais!