Um resumo sobre: listas encadeadas simples.
Tags: algorithms
Published: 2023-02-25 03:19:53

Neste resumo irei abordar dois tópicos principais:

- Diferença entre vetores e listas encadeadas;
- Processo de pesquisa, exclusão e inserção de dados em listas encadeadas simples.

**<u>Diferença entre vetores e listas encadeadas:</u>**

**<u>Vetores:</u>**
- Em um vetor não ordenado a busca é lenta;
- Vetor ordenado a inserção é lenta;
- Em ambos a remoção é lenta;
- O tamanho do vetor não pode ser alterado depois de criado;
- Mesmo vazios ocupam espaço na memória;

**<u>Lista encadeada:</u>**
- Cada item de dado é incorporado em um nó, sendo que cada nó possui referência para o próximo nó da lista;
- A lista possui cabeça e cauda que é apontada.

Em um vetor nós trabalhamos com posição, já em uma lista, nós trabalhamos com relacionamento. No vetor, nós trabalhamos com o item em uma certa posição e nós acessamos esses elementos por meio do índice que esses itens ocupam.
Com as listas nós trabalhamos com relacionamento e a posição do elemento é no endereço da memória. Dessa maneira, nós teremos acesso ao primeiro da lista e para chegarmos ao último, precisamos acessar todos até encontrá-lo. Os dados não podem ser acessados diretamente. Cada elemento da lista é armazenado em um objeto, sendo que esse elemento referencia o próximo e é alocado dinamicamente conforme a necessidade. Lembrando que o vetor é pré criado, o que ocupa mais lugar na memória. Imagina que estivéssemos em um ambiente que cabe mil pessoas e quando forem surgindo pessoas, nós inserimos ela dentro desse ambiente. Agora termos uma segunda situação, nós inserimos uma pessoa e ela fica em um ambiente suficiente para ela e conforme for entrando, o espaço é aumentado. O primeiro é o vetor e neste último caso é uma lista, que aumenta conforme a necessidade. Para referenciar o primeiro elemento, é utilizado o elemento cabeça da lista. Sabemos que a lista chegou ao final, quando o próximo elemento for nulo.
Nessas duas imagens você terá uma comparação entre vetores de listas:

**Vetores:**
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fu3zjnocl2rxtk4nva6i.png)


**Listas:**

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c6zsoedk1x2qt6nl3w3t.png)

Depois dessa visão geral sobre a comparação entre as  listas e os vetores, vamos falar um pouco sobre as listas simples.

**<u>Listas Simples:</u>**

Nessa estrutura, nós podemos realizar 5 operações: **Inserir no início, excluir no início, mostrar lista, pesquisar e excluir da posição.**

**<u>Inserir no início:</u>** Este é o local mais fácil de inserir um item. Quando inserimos o novo nó (elemento), o que era o primeiro passa a ser o segundo da lista e o novo dado terá um ponteiro indicando que ele é a cabeça da lista. Na próxima imagem nós iremos ver 3 operações básicas. 
1- Criar o novo nó 
2- Apontar o novo nó para o nó que antes era o primeiro 
3- Apontar a cabeça da lista para o primeiro elemento. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gvetim6p0lcw91dtf1kw.png)

**<u>Excluir no início:</u>** É inverso do inserir no início. Iremos sobrescrever o ponteiro que indicava a cabeça da lista que agora irá indicar que o primeiro nó é o que era o segundo. O segundo nó é encontrado por meio do ‘próximo’ do primeiro nó. Observe na imagem:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/641tu1j7ak9tjw02kha3.png)

**<u>Mostrar lista e pesquisar:</u>** Para essas duas operações, irá funcionar de forma parecida. O programa irá iniciar no primeiro nó e irá percorrer de nó em nó, até chegar em um nó que irá apontar para o ‘próximo’ que será nulo. Se quisermos mostrar a lista toda, ele percorrerá todo nó, se quisermos encontrar um elemento, ele segue do início de nó em nó até encontrar e caso não exista o elemento ele irá percorrer toda a lista e não achará. Muito parecido com a pesquisa linear que vimos nos vetores. 

**<u>Excluir na posição: </u>**Por fim, essa operação é realizada quando queremos excluir um nó específico da lista. Iremos basicamente realizar uma pesquisa até encontrar o elemento desejado e então faremos com que o nó anterior a ele aponte o ‘Próximo’ para o que está posterior ao nó excluído. Observe na imagem:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1aexk15hmb96mdli80kk.png)


Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: [Estruturas de dados e algoritmos em python](https://www.udemy.com/course/estrutura-de-dados-e-algoritmos-python-guia-completo/)