Um resumo sobre: listas encadeadas simples.

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.

Diferença entre vetores e listas encadeadas:

Vetores:

• 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;

Lista encadeada:

• 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:

Listas:

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

Listas Simples:

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.

Inserir no início: 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.

Excluir no início: É 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:

Mostrar lista e pesquisar: 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.

Excluir na posição: 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:

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