Lista 08 - Listas Encadeadas Duplas

Essa lista tem como objetivo fixar os conceitos de lista duplamente encadeada, 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 ListaDuplamenteEncadeada vistos em sala de aula (lista dinâmica, com ponteiros para o nó anterior e o próximo, além dos atributos primeiro, ultimo e tamanho). 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, tanto do início para o fim quanto do fim para o início;
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 (nos dois sentidos) após cada remoção.

Exercício 02

Considere uma lista duplamente encadeada 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 os seus atributos anterior e proximo apontam:

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

Ao final, informe qual é o valor dos atributos primeiro, ultimo e tamanho.

Exercício 03

Responda:

1. Qual critério é utilizado para saber se uma lista duplamente encadeada está vazia?
2. Qual é o valor dos atributos primeiro e ultimo quando a lista está vazia?
3. Qual é o valor do atributo anterior do primeiro nó da lista?
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 considerando a existência do atributo ultimo.
7. Qual é a complexidade de remover o último elemento em uma lista dupla com ultimo? E em uma lista simples? Justifique.
8. Por que guardar o ponteiro anterior não melhora a complexidade da pesquisa por um valor?

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 Duplamente Encadeada
Nó
primeiro
ultimo
próximo
anterior
inserir
remover
pesquisar
imprimir

Exercício 05

Compare o vetor não ordenado, a lista encadeada simples e a lista duplamente encadeada preenchendo a tabela abaixo. Considere que a lista dupla possui o atributo ultimo:

Operação	Vetor Não Ordenado	Lista Encadeada Simples	Lista Duplamente Encadeada
Inserir no início
Inserir no final
Remover no início
Remover no final
Pesquisar um valor
Acessar o elemento da posição i
Percorrer no sentido inverso
Memória utilizada

Exercício 06

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

1. Percorrer ao contrário: percorra a lista do último nó até o primeiro, utilizando apenas o atributo anterior, e imprima os valores;

   • Entrada: primeiro <-> 10 <-> 20 <-> 30 <-> 40 <- ultimo → Saída: 40, 30, 20, 10

2. Remover do final em O(1): implemente um método remover_fim() que remova o último nó da lista sem percorrê-la, utilizando o atributo ultimo;

   • Entrada: primeiro <-> 1 <-> 2 <-> 3 <- ultimo → Saída: primeiro <-> 1 <-> 2 <- ultimo

3. Palíndromo: verifique se os valores da lista formam um palíndromo, percorrendo simultaneamente do início (primeiro) para o fim e do fim (ultimo) para o início;

   • Entrada: a <-> b <-> b <-> a → Saída: True
   • Entrada: a <-> b <-> c → Saída: False

4. Remover um nó conhecido: implemente um método remover_no(no) que receba a referência de um nó e o remova da lista ajustando os ponteiros dos vizinhos, sem pesquisar pelo valor. Considere os casos em que o nó é o primeiro, o último ou o único elemento.

Exercício 07

Considere a lista duplamente encadeada abaixo:

primeiro <-> 5 <-> 8 <-> 12 <-> 20 <- ultimo

1. Desenhe a lista antes da remoção, indicando os valores dos atributos primeiro, ultimo, tamanho e, de cada nó, valor, anterior e proximo;
2. Execute a operação remover(12) e demonstre, passo a passo, como os quatro ponteiros envolvidos são ajustados (anterior.proximo e proximo.anterior);
3. Desenhe a lista após a remoção;
4. Informe qual é o novo valor de primeiro, ultimo e tamanho;
5. Descreva o que aconteceria ao executar remover(5) (remoção do início) e ao executar remover(99). Qual seria o valor retornado em cada caso?