Resumo de Estruturas de dados

## Introdução às Estruturas de Dados No vasto universo da computação, a maneira como organizamos e armazenamos os dados é tão vital quanto os algoritmos que os processam. As **estruturas de dados** são formas específicas de organizar dados em um computador para que possam ser utilizados de maneira eficiente. A escolha da estrutura de dados correta pode influenciar drasticamente o desempenho de um programa, impactando tanto o tempo de execução quanto o uso da memória. Este material foi preparado para você, estudante de nível médio e superior, como uma introdução essencial aos princípios, operações, vantagens, desvantagens e aplicações práticas das estruturas de dados mais fundamentais. > **Estrutura de Dados:** Uma maneira particular de organizar e armazenar dados em um computador para que possam ser acessados e modificados eficientemente. ### Array (Vetor) vs. Lista Encadeada Duas das estruturas de dados mais básicas e frequentemente comparadas são o **array (vetor)** e a **lista encadeada**. Vamos explorá-las em detalhes para entender suas diferenças e quando usar cada uma. #### Array (Vetor) Um **array** é uma coleção de elementos do mesmo tipo de dados, armazenados em posições de memória contíguas. Pense neles como uma sequência de caixas numeradas, onde cada caixa guarda um item. Cada elemento é acessado por um **índice numérico**, que geralmente começa em $0$. Uma característica importante é que arrays têm um **tamanho fixo**, definido no momento da sua criação. **Operações Principais:** * **Acesso:** Acessar um elemento em uma posição específica é muito rápido. Por exemplo, `vetor[i]` permite encontrar o elemento diretamente. Isso acontece porque o endereço de memória pode ser calculado a partir do endereço inicial do array e do índice do elemento. A sua complexidade de tempo é de $O(1)$ (tempo constante). * **Exemplo:** Em um array de inteiros, se o primeiro elemento está no endereço $1000$ e cada inteiro ocupa $4$ bytes, o elemento no índice $2$ estará no endereço $1000 + (2 \times 4) = 1008$. * **Inserção/Remoção:** Inserir ou remover um elemento no meio de um array é uma operação custosa. Para inserir, é necessário deslocar todos os elementos seguintes para abrir espaço. Para remover, os elementos subsequentes precisam ser deslocados para preencher a lacuna. A complexidade é de $O(n)$, onde $n$ é o número de elementos no array. * **Busca:** A busca por um valor específico pode ser $O(n)$ no pior caso (se você precisar percorrer o array inteiro, como na busca linear). Se o array estiver ordenado, a busca pode ser mais eficiente, como $O(\log n)$ usando busca binária. **Vantagens:** * **Acesso rápido e direto:** Qualquer elemento pode ser acessado em tempo constante ($O(1)$). * **Eficiência da memória cache:** Devido à contiguidade na memória, arrays aproveitam bem a cache do processador, o que pode acelerar o acesso aos dados. **Desvantagens:** * **Tamanho fixo:** É difícil redimensionar um array dinamicamente após sua criação. Se você precisar de mais espaço, geralmente terá que criar um novo array maior e copiar os elementos. * **Inserções e remoções lentas:** No meio da estrutura, essas operações são ineficientes. **Exemplo Prático:** Imagine um array de números inteiros: `[10, 20, 30, 40, 50]`. Para acessar o terceiro elemento (índice $2$), basta utilizar `vetor[2]`, que retornará $30$ em tempo constante ($O(1)$). Did you know that o primeiro array foi implementado em linguagens de programação muito antigas, como o FORTRAN, e continua sendo uma das estruturas mais fundamentais em quase todas as linguagens modernas? #### Lista Encadeada Uma **lista encadeada** é uma coleção de elementos, conhecidos como **nós**. Cada nó contém dois componentes principais: o **dado** (o valor que queremos armazenar) e uma **referência** (ou **ponteiro**) para o próximo nó na sequência. A principal diferença em relação aos arrays é que os nós de uma lista encadeada não precisam estar em posições de memóri