Listas

Nesse post você verá 8 exercícios resolvidos sobre Listas Ligadas no contexto de estrutura de dados. Esse questionário é essencialmente teórico, ou seja, você não implementará nenhum código. Procure responder o questionário e depois confira suas respostas no final do post.

Os exercícios apresentados nesse post fazem parte de uma sequência de posts sobre estruturas de dados. Veja mais conteúdos sobre isso aqui.

Listas Ligadas

1- Quais são as vantagens da lista ligada em relação ao vetor?  

2- E quais são as desvantagens da lista ligada em relação ao vetor?  

3- Explique, com suas palavras, como funciona a remoção de um elemento que está no meio de uma lista ligada?  

4- Explique com suas palavras qual o tempo de execução da operação de remoção?  

Listas duplamente Ligadas  

5- Qual a diferença entre uma lista ligada simples e uma lista duplamente ligada?  

6- Como é o tempo de remoção de uma lista duplamente ligada?  

7- Explique, com suas palavras, como funciona uma inserção de um elemento no meio de uma lista duplamente ligada?  

8- Qual o tempo de execução da inserção no início e no fim de uma lista ligada?  

---

Respostas

1- A vantagem da lista ligada é que como a relação entre duas células é feita por referências, é fácil inserir um elemento no meio da lista (afinal, basta acertar das células a esquerda e a direita). Inserir no começo e no fim também leva tempo constante, afinal geralmente a estrutura possui referências para o primeiro e último elemento.  

2- Recuperar um elemento em uma posição aleatória pode levar tempo linear. Afinal, diferente do vetor, onde pegar um elemento qualquer custa uma simples operação de array, em uma lista ligada, precisamos navegar pelas referências até encontrar o elemento desejado.  

3- Se o elemento (por exemplo, X) está no meio de uma lista, a remoção dele é basicamente acertar a referência proximo do elemento a esquerda e fazê-lo apontar para o próximo de X. Dessa forma, “pulamos” o elemento X e a lista continua certa.  

4- A remoção em uma lista ligada simples (igual a que vimos) leva tempo linear. Afinal, precisamos navegar na lista até achar o elemento antes e o depois do elemento a ser removido. No próximo capítulo, veremos como melhorar isso.  

5- Na lista ligada simples a célula só aponta para a próxima célula da lista. Já na lista duplamente ligada, a célula tem referências para a anterior e para a próxima. A grande vantagem é que muitas operações necessitam também da célular anterior, e tudo fica mais fácil com a referência armazenada em cada célula.  

6- A remoção em uma lista ligada pode ser ou linear ou constante. Se você tiver a referência em mãos da célula que será deletada, então o tempo é constante. Afinal, já que você tem anterior e proximo nas mãos, basta acertar as referências. Se você precisar procurar pelo elemento primeiro, então o tempo será linear, afinal passará por todas as células no pior caso.  

7- A célula X para entrar no meio de uma lista duplamente ligada precisa:

• Pegar a célula anterior e marcar o proximo dela como X
• Pegar a antiga célula proximo da anterior, e marcar a anterior dela como X
• Marcar anterior de X como a antiga anterior
• Marcar proxima de X como sendo a antiga proxima

8- Em ambos o tempo é constante. Assim como na lista ligada simples, basta acertar as referências, já que a estrutura armazena o primeiro e ultimo nós.