Resumo de Lista encadeada

## Listas Encadeadas: Estruturas de Dados Dinâmicas As estruturas de dados são ferramentas cruciais na ciência da computação para organizar e armazenar informações de maneira eficiente. Entre as várias opções, as **listas encadeadas** se destacam por sua capacidade de gerenciar dados de forma dinâmica, o que as diferencia de estruturas mais estáticas como os arrays. Entender as listas encadeadas é fundamental para desenvolver algoritmos eficazes e otimizar o uso da memória. ### O Conceito de Nó e Ponteiro No coração de qualquer lista encadeada está o **nó** (ou elemento) e o **ponteiro** (ou referência). Um nó é a unidade básica que guarda a informação. Cada nó geralmente possui dois componentes principais: 1. **Dados**: A informação que o nó armazena. Pode ser um número, um texto, ou até um objeto mais complexo. 2. **Ponteiro (ou Referência)**: Um campo que guarda o endereço de memória do próximo nó na sequência. É esse ponteiro que "encadeia" os nós, formando a lista. O ponteiro do último nó da lista aponta para um valor nulo (`NULL` ou `nil`), indicando o seu fim. > Um nó é a unidade fundamental de uma lista encadeada, contendo os dados e um ponteiro para o próximo elemento. O primeiro nó de uma lista encadeada é chamado de **cabeça** (`head`). A cabeça serve como o ponto de partida para acessar todos os outros nós da lista. Se a cabeça aponta para nulo, a lista está vazia. ### Tipos de Listas Encadeadas Existem diferentes tipos de listas encadeadas, cada um com suas particularidades: 1. **Lista Simplesmente Encadeada**: É o tipo mais simples. Cada nó tem apenas um ponteiro, que aponta para o próximo nó. Isso significa que você só pode percorrer a lista em uma direção (para frente). 2. **Lista Encadeada Circular**: Nesta variação, o ponteiro do último nó aponta de volta para o primeiro nó (a cabeça), criando um ciclo. Isso é útil quando você precisa percorrer a lista continuamente, sem um "fim" definido. Este material focará principalmente nas listas simplesmente encadeadas para construir uma base sólida de conhecimento. ### Operações Fundamentais em Listas Encadeadas As operações mais comuns que você pode realizar em listas encadeadas são inserir, remover, buscar e percorrer nós. #### 1. Inserção de um Nó Inserir um novo nó pode ser feito em diferentes posições na lista: * **Inserção no Início da Lista ($O(1)$)**: Esta é a operação mais rápida. Você cria um novo nó, faz com que seu ponteiro `próximo` aponte para a cabeça atual da lista, e então atualiza a cabeça da lista para ser o novo nó. A complexidade de tempo é constante, $O(1)$, porque sempre envolve o mesmo número de passos, independentemente do tamanho da lista. *Exemplo:* Para inserir um nó `N` com valor `X` no início de uma lista `L` cuja cabeça atual é `H`: 1. Crie um novo nó `N_novo` com valor `X`. 2. Faça `N_novo.próximo = H`. 3. Faça `H = N_novo`. * **Inserção no Fim da Lista ($O(n)$ para lista simplesmente encadeada, $O(1)$ se mantivermos um ponteiro para a cauda)**: Se a lista for simplesmente encadeada e você não tiver um ponteiro especial para o último nó (a **cauda**), você precisa percorrer a lista desde a cabeça até encontrar o último nó (aquele cujo ponteiro `próximo` é nulo). Uma vez que o último nó é encontrado, seu ponteiro `próximo` é atualizado para apontar para o novo nó. Isso leva um tempo proporcional ao número de nós na lista, $O(n)$, pois pode ser necessário visitar todos eles. No entanto, se você mantiver um ponteiro para a cauda da lista, a inserção no fim se torna uma operação de tempo constante, $O(1)$. * **Inserção em Posição Específica ($O(n)$)**: Para inserir um nó no meio da lista, você precisa percorrer a lista até encontrar o nó que virá *antes* da posição desejada. Depois de encontrá-lo, o ponteiro `próximo` do nó anterior é ajustado para apontar para o novo nó, e o ponteiro `próximo` do novo nó aponta para o nó que estava originalmente na posição seguinte. Esta operação também tem uma