3 4 - Implementação de listas encadeadas duplas

Prévia do material em texto

<p>Implementação de listas</p><p>encadeadas duplas</p><p>Apresentação</p><p>As listas encadeadas duplas podem ser utilizadas na resolução de problemas computacionais, o que</p><p>consiste em receber uma certa entrada e obter uma determinada saída, conforme a entrada.</p><p>Um bom exemplo de um problema computacional resolvido utilizando listas encadeadas duplas é a</p><p>navegação entre diretórios em um sistema operacional. Imagine que a lista recebe como entrada</p><p>todos os diretórios do sistema operacional, e como saída uma ligação entre todos os diretórios, o</p><p>que permite realizar a navegação para qualquer diretório, a partir de outro diretório qualquer.</p><p>Além desses problemas, as listas encadeadas duplas podem ser utilizadas para implementar outros</p><p>tipos abstratos de dados, tais como pilhas, filas e árvores.</p><p>Nesta Unidade de Aprendizagem, você verá a utilização de listas encadeadas duplas em problemas</p><p>computacionais, além de analisar e resolver problemas computacionais utilizando esta abordagem.</p><p>Bons estudos.</p><p>Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:</p><p>Demonstrar a utilização de listas encadeadas duplas em problemas computacionais.•</p><p>Analisar a utilização de listas encadeadas duplas em problemas computacionais.•</p><p>Resolver problemas computacionais utilizando listas encadeadas duplas.•</p><p>Laiane</p><p>Laiane</p><p>Desafio</p><p>A aplicação de listas duplamente encadeadas é comumente utilizada para resolver diferentes</p><p>problemas do dia a dia, além dos problemas estritamente computacionais.</p><p>Suponha que você foi chamado para resolver o seguinte problema:</p><p>Descreva um passo a passo de como implementar um algoritmo que verifique quando a compra de</p><p>dois itens for igual a 7 reais, e informe os valores individuais de cada produto para que o cliente</p><p>pague apenas o de maior preço.</p><p>Infográfico</p><p>Com uma lista duplamente encadeada é possível realizar várias operações com os dados</p><p>armazenados em sua estrutura. Uma operação interessante é realizar a ordenação de elementos,</p><p>com o QuickSort, ou implementar outros algoritmos de ordenação, como o MergeSort.</p><p>Neste Infográfico, você vai ver como realizar a implementação do MergeSort em uma lista</p><p>duplamente encadeada.</p><p>Laiane</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/8126d973-5dc6-437e-ad45-e32722e8eedc/7402f3b8-ef1b-4532-a2f3-65aa75acef47.png</p><p>Conteúdo do livro</p><p>As listas duplamente encadeadas podem ser utilizadas em diferentes problemas computacionais.</p><p>Uma vez que os dados estão armazenados na lista, é possível realizar operações, como, por</p><p>exemplo, soma de elementos e ordenação de dados, além de encontrar elementos, e até mesmo</p><p>reestruturar os dados para outro tipo abstrato de dados.</p><p>No capítulo Implementação de listas encadeadas duplas, do livro Estrutura de dados, base teórica</p><p>desta Unidade de Aprendizagem, você vai utilizar as listas encadeadas duplas em problemas</p><p>computacionais. Além disso, vai analisar e solucionar problemas computacionais utilizando listas</p><p>encadeadas duplas com a linguagem de programação Python.</p><p>Boa leitura.</p><p>Laiane</p><p>Laiane</p><p>ESTRUTURA</p><p>DE DADOS</p><p>Rafael Albuquerque</p><p>Implementação de listas</p><p>encadeadas duplas</p><p>Objetivos de aprendizagem</p><p>Ao final deste texto, você deve apresentar os seguintes aprendizados:</p><p>� Demonstrar a utilização de listas encadeadas duplas em problemas</p><p>computacionais.</p><p>� Analisar a utilização de listas encadeadas duplas em problemas</p><p>computacionais.</p><p>� Resolver problemas computacionais utilizando listas encadeadas</p><p>duplas.</p><p>Introdução</p><p>As listas duplamente encadeadas são estruturas de dados sequenciais,</p><p>nas quais um registro de memória se liga a dois registros de espaço de</p><p>memória — também conhecidos como nós — tanto para um endereço</p><p>anterior como para um endereço posterior. Essa característica permite</p><p>que os elementos sejam percorridos em duas direções, partindo do início</p><p>ou do final da lista.</p><p>Em problemas computacionais, a aplicação de listas duplamente en-</p><p>cadeadas é utilizada em vetores fixos ou dinâmicos, nos quais uma coluna</p><p>indica qual é o dado anterior ou posterior. Essa abordagem em listas se</p><p>torna eficiente, pois, se comparada às listas de encadeamento simples,</p><p>o último elemento de uma lista pode ser acessado de forma direta, sem</p><p>que seja preciso percorrer todos os elementos anteriores. Assim como o</p><p>acesso, a remoção de qualquer nó da lista também é facilitada por não</p><p>precisar percorrer novamente a lista até o nó que se deseja eliminar para</p><p>guardar o elemento anterior.</p><p>Neste capítulo, você irá aprender a identificar a utilização de listas</p><p>encadeadas duplas em problemas computacionais, como realizar a</p><p>análise de utilização e como empregá-la para solucionar problemas</p><p>computacionais.</p><p>1 Listas encadeadas duplas em problemas</p><p>computacionais</p><p>Os problemas computacionais são situações que podem ser resolvidas passo a</p><p>passo com o computador. Por essa natureza, esses problemas geralmente são</p><p>bem definidos, com entradas bem estabelecidas, restrições e condições que</p><p>satisfazem os valores de saída. Alguns dos problemas podem ser de: tomada</p><p>de decisão, pesquisa, contagem, ordenação e otimização.</p><p>Conforme Piva Junior et al. (2014), além dos diversos tipos de dados que</p><p>podem ser armazenados, podem ser escolhidos também diferentes tipos de lista,</p><p>segundo a necessidade de nossos sistemas. As listas podem conter diferentes</p><p>aspectos, tais como:</p><p>� Tipo de informação: neste caso, a lista pode armazenar qualquer tipo de</p><p>informação, como nome, endereço, contatos, dentre outros elementos</p><p>existentes no mundo real.</p><p>� Ordem dos elementos: aqui, varia conforme a política de negócio, po-</p><p>dendo estar em ordem de inserção, crescente ou decrescente, etc.</p><p>� Homogeneidade da informação: todos os elementos de uma lista podem</p><p>ser representados pelo mesmo tipo de dado (inteiro, string ou uma classe</p><p>criada), ou armazenar tipos de dados diferentes. Em linguagens fraca-</p><p>mente tipadas, como Python e PHP, por exemplo, esse comportamento</p><p>é visto com maior naturalidade.</p><p>Um problema que aparece em tom de vantagem pela utilização das listas</p><p>duplamente encadeadas é que estas permitem a utilização de mais um ponteiro</p><p>para referenciar o elemento anterior, o que as difere de uma lista simplesmente</p><p>encadeada, permitindo menor esforço para que sejam feitas operações como</p><p>a de remoção, por exemplo. E essa abordagem de listas abre espaço para a</p><p>utilização de outras listas, como as listas duplas com cabeça fixa, as circulares,</p><p>as multidimensionais, as transversais (muito usadas em combinação com a</p><p>multidimensional) e as com a combinação desses tipos.</p><p>Implementação de listas encadeadas duplas2</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Listas com cabeça fixa</p><p>Geralmente, ao se iniciar uma lista encadeada, é comum verificar se ela está</p><p>vazia. Essa verificação é realizada para retornar uma mensagem ao usuário,</p><p>para que ele tenha ciência do que está acontecendo. Uma forma de deixar</p><p>o código mais simples e compacto é com a utilização de listas com cabeça</p><p>fixa, que consistem em fixar o primeiro nó (sendo ele o responsável por essa</p><p>denominação), e não armazenam nenhum elemento.</p><p>Uma lista com cabeça fixa é inicializada, de modo a alocar um nó e preen-</p><p>chermos seu campo com um endereço nulo (sem referência à memória). Seu</p><p>campo de informação não precisa ser preenchido, pois apenas pertence à lista</p><p>física (e não à lista lógica) (PIVA JUNIOR et al., 2014). Para ilustrar melhor,</p><p>a Figura 1 apresenta uma lista com três valores de nós, mas com apenas dois</p><p>deles contendo informação.</p><p>Figura 1. Lista dupla com início fixo.</p><p>Existem vários tipos de listas que podem ser utilizadas conforme a necessidade. Logo,</p><p>podemos usar listas duplamente encadeadas com uma técnica conhecida como</p><p>cabeça fixa. A diferença para as listas costumeiramente implementadas é que, além do</p><p>ponteiro de próximo, o ponteiro de anterior também deve ser iniciado com o valor nulo.</p><p>3Implementação</p><p>de listas encadeadas duplas</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>2 Análise da utilização de listas encadeadas</p><p>duplas em problemas computacionais</p><p>A utilização de listas encadeadas duplas, para solucionar alguns problemas</p><p>computacionais, pode apresentar soluções mais otimizadas do que outras</p><p>abordagens de solução, sempre respeitando as propriedades de uma lista en-</p><p>cadeada dupla. Dentre os diversos problemas computacionais, realizaremos a</p><p>análise do algoritmo de ordenação QuickSort aplicado em uma lista duplamente</p><p>encadeada. Geralmente, essas análises de desempenho de um algoritmo são</p><p>realizadas usando-se as seguintes medidas:</p><p>� Espaço necessário para concluir a tarefa desse algoritmo (complexidade</p><p>do espaço). Inclui espaços para programa e para dados.</p><p>� Tempo necessário para concluir a tarefa desse algoritmo (complexidade</p><p>do tempo).</p><p>A complexidade dessa implementação é igual à de tempo do QuickSort</p><p>para a ordenação de matrizes, ou seja, leva O (n2) tempo no pior caso e O (n</p><p>Log n) no melhor caso (CORMEN, 2002). O pior caso ocorre quando a lista</p><p>vinculada já está classificada, pois é necessário percorrer toda a lista.</p><p>Existe uma implementação do QuickSort que é mais eficiente, o QuickSort</p><p>aleatório. No entanto, o Quicksort pode ser implementado nas listas encadeadas</p><p>apenas quando podemos escolher um ponto fixo como o pivô, dessa forma,</p><p>o QuickSort aleatório não pode ser implementado com eficiência nas listas</p><p>encadeadas escolhendo o pivô aleatório.</p><p>Além dos problemas de ordenação, existem outros problemas, como os</p><p>aritméticos, que podem ser solucionados utilizando-se listas encadeadas duplas,</p><p>como, por exemplo, contar três números na lista que somam um determinado</p><p>valor x. Utilizando-se listas duplamente encadeadas, existem três abordagens</p><p>para solucionar esse problema:</p><p>1. Abordagem ingênua — essa é a abordagem mais simples, no entanto,</p><p>a mais complexa. Utilize três loops aninhados para gerar todas as</p><p>combinações de três números e verifique se a soma dos três elementos</p><p>é igual a x ou não.</p><p>Complexidade de tempo: O (n3)</p><p>Espaço auxiliar: O (1)</p><p>Implementação de listas encadeadas duplas4</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>2. Hashing — percorra a lista duplamente vinculada e armazene os dados</p><p>de cada nó e seu par de ponteiros (tupla) na tabela de hash. Agora, gere</p><p>cada par possível de nós. Para cada par de nós, calcule a soma dos dados</p><p>nos dois nós e verifique se o valor existe ou não na tabela de hash.</p><p>Complexidade do tempo: O (n2)</p><p>Espaço auxiliar: O (n)</p><p>3. Uso de dois ponteiros — percorra a lista duplamente vinculada da</p><p>esquerda para a direita. Para cada nó atual durante a travessia, inicie</p><p>dois ponteiros: primeiro = ponteiro para o nó próximo ao nó atual</p><p>e último = ponteiro para o último nó da lista. Agora, conte os pares na</p><p>lista do primeiro ao último ponteiro que somam o valor.</p><p>Complexidade do tempo: O (n2)</p><p>Espaço auxiliar: O (1)</p><p>Com esses exemplos, é possível verificar que, dependendo dos proble-</p><p>mas, existem maneiras diferentes de solucionar um problema usando listas</p><p>duplamente encadeadas e que, geralmente, cada abordagem apresenta um</p><p>desempenho diferente. Isso ocorre devido à flexibilidade de navegar entre os</p><p>elementos da lista duplamente encadeada. Na Figura 2, é possível verificar o</p><p>comportamento de cada complexidade de tempo dos problemas apresentados.</p><p>Figura 2. Notação Big O.</p><p>Fonte: Brundi (2019, documento on-line).</p><p>5Implementação de listas encadeadas duplas</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Além da complexidade da resolução dos problemas computacionais, que</p><p>varia muito de problema para problema, existem as complexidades de cada</p><p>operação básica que é feita em uma lista duplamente encadeada, como é</p><p>possível verificar no Quadro 1.</p><p>Média Pior</p><p>Acesso Procura Inser-</p><p>ção</p><p>Elimi-</p><p>nação</p><p>Acesso Procura Inser-</p><p>ção</p><p>Elimi-</p><p>nação</p><p>Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1)</p><p>Quadro 1. Complexidade temporal de operações comuns</p><p>Existe uma versão de lista encadeada dupla que utiliza apenas um espaço para o campo</p><p>de endereço em cada nó. Essa lista é chamada de lista encadeada XOR (disjunção</p><p>exclusiva), ou lista duplamente encadeada eficiente de memória, pois em vez de</p><p>armazenar endereços de memória reais, cada nó armazena o XOR dos endereços dos</p><p>nós anteriores e dos próximos.</p><p>3 Resolução de problemas computacionais</p><p>utilizando listas encadeadas duplas</p><p>Os problemas computacionais são situações que podem ser resolvidas passo a</p><p>passo com o computador. Por essa natureza, esses problemas geralmente são</p><p>bem definidos, com entradas bem estabelecidas, restrições e condições que</p><p>satisfazem os valores de saída. Alguns dos problemas podem ser de: tomada</p><p>de decisão, pesquisa, contagem, ordenação e otimização. Nesta seção, vamos</p><p>apresentar a resolução do problema de ordenação rápida com abordagem em</p><p>listas duplas, conhecido na literatura como QuickSort.</p><p>Implementação de listas encadeadas duplas6</p><p>Laiane</p><p>Laiane</p><p>Algoritmo QuickSort</p><p>O algoritmo QuickSort, também conhecido como algoritmo de ordenação</p><p>rápida, é assim chamado pela sua estratégia de divisão da lista em partes,</p><p>determinada por um elemento arbitrário, ou não, denominado como pivô.</p><p>Conforme Celes Filho, Cerqueira e Rangel (2004), supondo que esse elemento</p><p>ocupe uma posição fixa no vetor (início, meio ou fim), de índice i, com a partição</p><p>da lista original em duas sublistas, há dois problemas menores para serem</p><p>resolvidos, que seriam de ordenar as sublistas. Estas passarão pelo mesmo</p><p>processo de divisão, recursivamente, tornando-se cada vez menores até que</p><p>reste apenas um elemento, caso em que a sua ordenação estará concluída.</p><p>Conforme Tenenbaum, Langsam e Augenstein (1995), suponha que os</p><p>elementos de x (um vetor qualquer) sejam particionados de modo que os ele-</p><p>mentos a = x[0] (primeiro elemento) e a sejam remanejados para a posição j,</p><p>tendo que observar as seguintes condições:</p><p>� Elementos das posições 0 até j – 1 sejam menores ou iguais a a.</p><p>� Elementos das posições j + 1 até n – 1 sejam maiores que a.</p><p>Para fins de exemplificação do funcionamento do algoritmo de ordenação</p><p>QuickSort, se for repassado um vetor, tal como [20-52-43-32-7-87-81-28], cujo</p><p>primeiro elemento (20) é posto na posição correta de ordenação, que nesse</p><p>caso será o segundo índice do vetor, o resultado será [7-20-52-43-32-87-81-28].</p><p>A primeira rodada termina com a sequência correta de ordenação dos dois</p><p>primeiros elementos da lista (7 e 20 em ordem), pois cada elemento menor</p><p>ou igual a 20 está corretamente posicionado, assim como para os números</p><p>com valor superior. Como o número 20 já se encontra em sua posição final,</p><p>o problema inicial pode ser decomposto na classificação dos dois vetores: [7]</p><p>e [52-43-32-87-81-28].</p><p>7Implementação de listas encadeadas duplas</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Perceba que o primeiro vetor já se encontra em seu tamanho mínimo</p><p>(1 elemento). No entanto, para ordenar o segundo vetor, é realizada a repeti-</p><p>ção do processo, em que o número 52 será o pivô, resultando nos seguintes</p><p>subvetores: 7-[32-43-28]-52-[81-87]. Esse processo irá se repetir até que só</p><p>reste um elemento em cada subvetor com o seguinte resultado ordenado:</p><p>[7-28-32-43-52-81-87]. A Figura 3 apresenta uma das formas de implementação</p><p>do algoritmo de QuickSort.</p><p>Ainda na Figura 3, é possível notar duas etapas: a primeira é que o algoritmo</p><p>se divide em dois recursivamente; a segunda é a função partição, que realiza</p><p>toda a ordenação dos subelementos por meio da escolha de um elemento</p><p>chamado pivô.</p><p>Figura 3. Pseudocódigo do algoritmo de QuickSort.</p><p>QuickSort com lista duplamente encadeada</p><p>Uma vez compreendido o funcionamento do algoritmo QuickSort, veremos</p><p>como é feita a sua implementação ao utilizar listas com encadeamento duplo,</p><p>com sua implementação realizada na linguagem em Python3.X.</p><p>Implementação de listas encadeadas duplas8</p><p>Laiane</p><p>Laiane</p><p>A Figura 4 apresenta a implementação do algoritmo QuickSort para um</p><p>vetor simples, com os índices sendo números. Perceba que, para essa imple-</p><p>mentação,</p><p>o pivô selecionado foi o último elemento do vetor. Ao utilizar uma</p><p>lista encadeada, sabemos que precisaremos tratar os endereços de memória</p><p>diretamente, e não os índices, como ocorre quando trabalhamos com vetores.</p><p>Em Python, como já abordado, a manipulação do espaço de memória fica</p><p>completamente abstraída pela própria linguagem, não sendo manipulada</p><p>diretamente, como ocorre em linguagens como C/C++.</p><p>Figura 4. QuickSort em Python3.X.</p><p>A implementação da lista encadeada dupla para o problema de ordenação</p><p>do QuickSort requer um pouco mais de linhas de código, como pode ser</p><p>visto nas Figuras 5 e 6. As implementações em cada função das respectivas</p><p>imagens usaram a técnica de type hint de Python, encontrada em seu manual</p><p>de boas práticas PEP8, para explicitar os tipos de dados dos argumentos das</p><p>funções, além do tipo de dado que cada função retornará por meio do símbolo</p><p>-> (traço e maior).</p><p>A escolha do pivô por conveniência foi referente ao último elemento. Perceba</p><p>também que ao implementarmos o QuickSort, precisamos criar nossa própria</p><p>estrutura de lista duplamente encadeada para ser adicionada ao algoritmo de</p><p>ordenação. Portanto, a Figura 5 apresenta a implementação básica da lista du-</p><p>plamente encadeada somente com as funções de adicionar, remover e imprimir.</p><p>9Implementação de listas encadeadas duplas</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Figura 5. Implementação da lista duplamente encadeada.</p><p>Uma vez que contamos com a implementação da lista, agora precisamos</p><p>da implementação do algoritmo de ordenação, que pode ser observado na</p><p>Figura 6. Perceba que foram implementadas três funções. Além da utilização</p><p>de endereçamento, outra mudança adicionada foi na escolha do pivô, que foi</p><p>escolhido conforme o último elemento.</p><p>Figura 6. QuickSort com lista duplamente encadeada em Python3.X.</p><p>Implementação de listas encadeadas duplas10</p><p>BUNDI, B. Understanding Big-O notation with JavaScript. 2019. Disponível em: https://</p><p>dev.to/b0nbon1/understanding-big-o-notation-with-javascript-25mc. Acesso em: 4</p><p>fev. 2020.</p><p>CELES, W.; CERQUEIRA, R.; RANGEL, J. L. Introdução e estrutura de dados: com técnicas</p><p>de programação em C. 4. ed. Rio de Janeiro: Campus, 2004.</p><p>CORMEN, T. H. Algoritmos: teoria e prática. Rio de Janeiro: Elsevier, 2002.</p><p>PIVA JUNIOR, D. et al. Estrutura de dados e técnicas de programação. Rio de Janeiro:</p><p>Elsevier, 2014.</p><p>TENENBAUM, A. M; LANGSAM, Y.; AUGENSTEIN, M. J. Estruturas de dados em C. São</p><p>Paulo: Makron Books, 1995.</p><p>Os links para sites da web fornecidos neste livro foram todos testados, e seu funciona-</p><p>mento foi comprovado no momento da publicação do material. No entanto, a rede</p><p>é extremamente dinâmica; suas páginas estão constantemente mudando de local</p><p>e conteúdo. Assim, os editores declaram não ter qualquer responsabilidade sobre</p><p>qualidade, precisão ou integralidade das informações referidas em tais links.</p><p>11Implementação de listas encadeadas duplas</p><p>Dica do professor</p><p>A lista encadeada XOR é a versão com eficiência de memória da lista duplamente encadeada, pois</p><p>utiliza apenas um espaço para o campo de endereço em cada nó. Diferentemente de uma lista</p><p>comum duplamente encadeada, a qual armazena endereços dos itens de listas anteriores e</p><p>seguintes em cada nó da lista, exigindo a manutenção de dois campos de endereço por nó.</p><p>Nesta Dica do Professor, você vai ver a lista encadeada XOR, a qual é duplamente eficiente em</p><p>memória.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/64ff91f432a2ef0ad0829ec843edfec7</p><p>Exercícios</p><p>1) Existem várias formas de implementar as listas duplas.</p><p>Entre os tipos, há as listas duplas com cabeça fixa. Logo, qual seria a vantagem em utilizar</p><p>listas com cabeça fixas?</p><p>A) Listas com cabeça fixa permitem e carregam sempre seu valor em seu início, não</p><p>necessitando de ponteiros como início e fim.</p><p>B) Listas com cabeça fixa são estáticas e devem conter informações, como qualquer outro</p><p>elemento da lista.</p><p>C) Por serem fixas, o ponteiro dessa lista não tem seu endereço variante, permitindo que seu</p><p>ponteiro anterior seja apontado para algum elemento contendo informação, sendo muito</p><p>mais útil na sua inicialização.</p><p>D) Normalmente, listas com cabeça fixa permitem um tipo de implementação sem tantas</p><p>amarras de funções, como inserir e remover, por exemplo.</p><p>E) Em listas com cabeça fixa, a maior vantagem é que seu endereço, tanto o endereço anterior</p><p>como o que aponta para o próximo ponteiro, devem apontar para um endereço nulo, mesmo</p><p>após a inserção do primeiro elemento.</p><p>2) As listas duplas são vistas como vias de mão dupla, em que é possível percorrê-las em duas</p><p>direções.</p><p>Uma vez implementada, como transformá-la em uma lista circular?</p><p>A) Para que uma lista seja circular, deve haver um ponteiro que se liga a um endereço nulo de</p><p>um lado, e um endereço não nulo de outro.</p><p>B) Para que uma lista seja circular, o endereço próximo do primeiro elemento deve apontar para</p><p>o último, e o endereço nulo apontado pelo ponteiro anterior do primeiro elemento, deve</p><p>apontar para o último.</p><p>C) Para que uma lista dupla seja circular, o endereço de próximo do último elemento deve</p><p>apontar para o primeiro, e o endereço nulo apontado pelo ponteiro anterior do primeiro</p><p>elemento, deve apontar para o segundo.</p><p>Laiane</p><p>Laiane</p><p>Listas com cabeça fixa não precisam recorrer a mais elementos de uma lista, como os ponteiros nomeados como início e fim, por exemplo, para poder percorrê-la, pois seu endereço já carrega o início da lista consigo.Logo, o endereço nomeado como cabeça fixa não deve também conter nenhuma informação, sendo apenas uma sentinela para acessar o primeiro elemento que contenha informação em uma lista.Uma das propriedades das listas de cabeça fixa é que seu ponteiro anterior aponte para uma referência nula. Além disso, funções básicas de inserção, remoção e impressão, etc., permanecem.</p><p>Laiane</p><p>O que diferencia as listas circulares de outras é que nelas o último elemento aponta para o primeiro e vice-versa, em caso de ponteiros duplos, não fazendo referência a endereços nulos, mesmo que exista apenas um elemento.</p><p>D) Para que uma lista dupla seja circular, o endereço de próximo do último elemento deve</p><p>apontar para o primeiro, e o endereço nulo apontado pelo ponteiro anterior do primeiro</p><p>elemento, deve apontar para o último.</p><p>E) Uma lista dupla será circular, mesmo que tenha apenas um elemento nela, com os ponteiros</p><p>de anterior e próximo apontando para nulo.</p><p>3) Fazer a análise de um algoritmo, por natureza, envolve entender a sua complexidade.</p><p>Por que as funções de inserção têm complexidade O(1) e remoção O(n) para os piores casos?</p><p>A) De forma intuitiva, ambas as operações são realizadas de forma direta.</p><p>B) De forma intuitiva, a inserção é feita de forma direta O(1), enquanto a remoção depende de</p><p>percorrer (n) elementos na lista.</p><p>C) De forma intuitiva, a inserção é feita de forma a percorrer todos os elementos da lista para</p><p>inserir no fim, enquanto a remoção é feita de forma direta.</p><p>D) As operações diretas têm complexidades de tempo O(n) para os melhores casos.</p><p>E) De forma intuitiva, a inserção é feita de forma a percorrer todos os elementos de uma lista</p><p>para inserir no início, enquanto a remoção é feita de forma direta.</p><p>4) Os problemas computacionais têm entradas bem estabelecidas, restrições e condições que</p><p>satisfazem os valores de saída. As listas duplamente encadeadas podem ser usadas de</p><p>acordo com a necessidade de cada problema, devido aos aspectos de uma lista.</p><p>As listas podem ter diferentes aspectos, quais são esses aspectos?</p><p>A) Tipo de problema: resolve apenas problemas matemáticos; ordem dos elementos: sempre</p><p>ordenados de forma crescente; heterogeneidade da informação: os elementos de uma lista</p><p>podem ser representados apenas por um único tipo de dado.</p><p>B) Forma da lista: pode servir como base para outros tipos abstratos de dados; linguagem de</p><p>implementação: o comportamento da lista duplamente</p><p>encadeada muda de acordo com a</p><p>linguagem de implementação; homogeneidade da informação: só armazena dados do mesmo</p><p>tipo.</p><p>C) Ordem dos elementos: sempre ordenados pela ordem de inserção; complexidade: a</p><p>complexidade das operações de uma lista é sempre a mesma; tipos de dados: armazena</p><p>apenas dados primitivos.</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>QUESTÃO 3: Antes da remoção, é realizada a busca do elemento, tendo no pior caso que percorrer uma somatória de elementos, ou seja, por todos os elementos; enquanto a inserção é feita de modo direto, sem a necessidade de passar por nenhum elemento anterior, justamente pelos ponteiros de referência início e fim.</p><p>D) Tamanho da lista: espaços de memória são alocados de maneira fixa; complexidade: medida</p><p>apenas de espaço extra; tipo de lista: o tipo de lista é definida pelos seus elementos</p><p>armazenados.</p><p>E) Tipo de informação: pode armazenar qualquer tipo de informação; ordem dos elementos:</p><p>conforme a política de negócio; homogeneidade da informação: os elementos de uma lista</p><p>podem ser representados pelo mesmo tipo de dado ou armazenar tipos de dados diferentes.</p><p>5) Entre os diversos tipos de listas duplamente encadeadas, existe uma versão chamada de lista</p><p>encadeada XOR.</p><p>Em relação a uma lista duplamente encadeada simples, qual a principal característica de uma</p><p>lista encadeada XOR?</p><p>A) As listas encadeadas XOR têm ponteiros diretos, somente entre o primeiro e o último</p><p>elemento da lista.</p><p>B) Intercala os ponteiros entre os elementos, de maneira que não seja possível acessar o</p><p>próximo elemento sequencial da lista sem passar por outro elemento.</p><p>C) Armazenar endereços de memória reais; cada nó armazena o XOR dos endereços dos nós</p><p>anteriores e dos próximos, necessitando de apenas um espaço de memória.</p><p>D) Funciona como uma lista simplesmente encadeada: só consegue realizar um percurso, do</p><p>início para o fim.</p><p>E) As listas XOR têm três espaços adicionais de memória, para o elemento anterior, para o</p><p>próximo e para o operador XOR.</p><p>Laiane</p><p>Laiane</p><p>QUESTÃO 4: As listas podem ter diferentes aspectos, tais como:Tipo de informação: neste caso, a lista pode armazenar qualquer tipo de informação, como nome, endereço, contatos, entre outros elementos existentes no mundo real.Ordem dos elementos: aqui, varia conforme a política de negócio, podendo estar em ordem de inserção, em ordem crescente ou decrescente, etc.Homogeneidade da informação: todos os elementos de uma lista podem ser representados pelo mesmo tipo de dado (inteiro, string ou uma classe criada), ou armazenar tipos de dados diferentes. Em linguagens fracamente tipadas, como Python e PHP, por exemplo, este comportamento é visto com maior naturalidade.Os demais aspectos não fazem ou não são comportamentos de uma lista duplamente encadeada: tipo do problema, complexidade, forma da lista ou linguagem de programação.</p><p>Laiane</p><p>QUESTÃO 5:  Uma versão com eficiência de memória da lista duplamente vinculada pode ser criada usando apenas um espaço para o campo de endereço em cada nó. Essa lista vinculada duplamente eficiente em memória é chamada de lista vinculada XOR ou memória eficiente, pois a lista usa a operação XOR bit a bit para economizar espaço para um endereço.As listas duplamente encadeadas seguem a propriedade que, a partir de um determinado elemento, seja possível tanto avançar quanto voltar, logo, as outras opções estão incorretas.</p><p>Laiane</p><p>Na prática</p><p>Uma lista duplamente vinculada pode ser aplicada em vários cenários e aplicativos da vida real, o</p><p>jogo com baralho de cartas é um exemplo clássico de uma lista duplamente vinculada. Dado que</p><p>cada carta de um baralho tem a carta anterior e a próxima carta organizadas sequencialmente, esse</p><p>baralho pode ser facilmente representado usando uma lista duplamente vinculada.</p><p>Neste Na Prática, você vai ver como Mariana utilizou as listas duplas para realizar um aplicativo de</p><p>jogo de baralho.</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/93eb8534-c5d4-492e-a295-a70eb3995d01/ee37ae51-07ec-48bc-8f50-96b92571c76c.png</p><p>Saiba +</p><p>Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:</p><p>Desalocando uma lista duplamente encadeada em C</p><p>Neste vídeo, você vai acompanhar o procedimento de exclusão de um item da lista, ou a própria</p><p>lista, na qual é importante salientar a liberação de memória, a fim de evitar que dados permaneçam</p><p>mesmo sem utilização. Confira.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Estrutura de Dados e Algoritmos em Java</p><p>Para se aprofundar mais em estrutura de dados, leia este livro, que apresenta o conteúdo</p><p>pertinente ao que foi estudado nesta Unidade de Aprendizagem.</p><p>Conteúdo interativo disponível na plataforma de ensino!</p><p>Lista Duplamente Encadeada</p><p>No vídeo a seguir, o professor Thiago Jabur Bittar explica sobre lista duplamente encadeada de</p><p>forma simples e didática.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://www.youtube.com/embed/1hwARpWkD5k</p><p>https://www.youtube.com/watch?v=wqzUPt6DIwk</p>