Lista 07 - Listas Encadeadas Simples

Essa lista tem como objetivo fixar os conceitos de lista encadeada simples, bem como a implementação de suas operações básicas.

Exercício 01

Implementar em linguagem Python os pseudocódigos das classes No e ListaEncadeada vistos em sala de aula (lista dinâmica, sem capacidade fixa). Faça também:

1. Teste o método esta_vazia() através do método remover(valor);
2. Demonstre a inserção no início de cada um dos caracteres que compõem o seu primeiro nome;
3. Imprima a lista após cada inserção;
4. Pesquise por pelo menos três caracteres existentes na lista e por um caractere inexistente;
5. Remova um elemento do início, um do meio e um do final da lista;
6. Imprima a lista após cada remoção.

Exercício 02

Considere uma lista encadeada simples inicialmente vazia. Execute a sequência de operações abaixo e demonstre o resultado após cada passo:

1. inserir_inicio(3)
2. inserir_inicio(2)
3. inserir_inicio(1)
4. inserir_fim(4)
5. remover(2)

Para cada passo, preencha a tabela abaixo indicando o valor de cada nó e para onde o seu atributo proximo aponta:

Ordem do nó	valor	proximo
-	-	-
-	-	-
-	-	-
-	-	-

Ao final, informe qual é o valor do atributo primeiro e qual é o valor do atributo tamanho.

Exercício 03

Responda:

1. Qual critério é utilizado para saber se uma lista encadeada simples está vazia?
2. Qual é o valor do atributo primeiro quando a lista está vazia?
3. Qual é o valor do atributo tamanho quando a lista contém apenas um elemento?
4. Qual é o valor do atributo proximo do último nó da lista?
5. Por que a lista encadeada não possui o método esta_cheia()?
6. Qual é a complexidade de inserir um elemento no início da lista? E no final? Justifique.

Exercício 04

Durante as aulas, usamos as nomenclaturas em português para nos referirmos aos elementos e métodos da lista encadeada. No entanto, na literatura, é comum encontrar os nomes em inglês. Preencha a tabela abaixo com os nomes em inglês correspondentes aos nomes em português:

Nome em Português	Nome comum usado em Inglês
Lista Encadeada
Nó
primeiro
próximo
inserir
remover
pesquisar
imprimir

Exercício 05

Compare a lista encadeada simples com o vetor não ordenado estudado anteriormente, preenchendo a tabela abaixo:

Operação	Vetor Não Ordenado	Lista Encadeada Simples
Inserir no início
Inserir no final
Pesquisar um valor
Acessar o elemento da posição i

Exercício 06

Utilizando a classe ListaEncadeada implementada no Exercício 01, resolva os desafios abaixo:

1. Contar elementos: percorra a lista e conte quantos nós existem, sem utilizar o atributo tamanho;

   • Entrada: 10 -> 20 -> 30 -> 40 → Saída: 4

2. Inverter lista: percorra a lista e inverta a ordem dos nós, ajustando apenas as referências proximo (sem criar uma nova lista);

   • Entrada: 1 -> 2 -> 3 -> 4 → Saída: 4 -> 3 -> 2 -> 1

3. Concatenar listas: receba duas listas encadeadas e ligue o último nó da primeira ao primeiro da segunda;

   • Entrada: Lista 1: 1 -> 2 e Lista 2: 3 -> 4 → Saída: 1 -> 2 -> 3 -> 4

Exercício 07

Considere a lista encadeada simples abaixo:

primeiro -> 5 -> 8 -> 12 -> 20 -> None

1. Desenhe a lista antes da remoção, indicando os valores dos atributos primeiro, valor, proximo e tamanho;
2. Execute a operação remover(12) e demonstre, passo a passo, como os ponteiros são ajustados;
3. Desenhe a lista após a remoção;
4. Informe qual é o novo valor de primeiro e de tamanho;
5. O que aconteceria se executássemos remover(99)? Qual seria o valor retornado?