Scribd
Carregar
22 visualizações1 página

Vantagens da Lista Encadeada Estendida

A Lista Encadeada Estendida oferece melhor desempenho e uso de memória em comparação com listas encadeadas comuns, pois cada nó armazena múltiplos elementos. Embora aumentar o tamanho do array interno melhore a relação entre ponteiros e dados, pode prejudicar o desempenho em operações de inserção e remoção. A busca é híbrida, combinando busca sequencial entre nós e busca binária dentro de cada nó, resultando em uma estrutura eficiente para grandes conjuntos de dados ordenados.

Enviado por

jpedrovoges
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato DOCX, PDF, TXT ou leia on-line no Scribd
22 visualizações1 página

Vantagens da Lista Encadeada Estendida

A Lista Encadeada Estendida oferece melhor desempenho e uso de memória em comparação com listas encadeadas comuns, pois cada nó armazena múltiplos elementos. Embora aumentar o tamanho do array interno melhore a relação entre ponteiros e dados, pode prejudicar o desempenho em operações de inserção e remoção. A busca é híbrida, combinando busca sequencial entre nós e busca binária dentro de cada nó, resultando em uma estrutura eficiente para grandes conjuntos de dados ordenados.

Enviado por

jpedrovoges
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato DOCX, PDF, TXT ou leia on-line no Scribd

Aluno: João Pedro Voges

1. Desempenho em relação à lista encadeada comum


A Lista Encadeada Estendida apresenta um desempenho geral melhor do que uma lista
encadeada comum, pois cada nó armazena vários elementos em um pequeno array. Isso
reduz a quantidade de ponteiros e melhora o uso da memória. Além disso, o acesso e a
inserção se tornam mais rápidos em média, já que é necessário percorrer menos nós e fazer
menos alocações.

2. Aumento do tamanho do array interno


Aumentar o tamanho do array interno melhora a relação entre ponteiros e dados,
economizando memória. No entanto, isso traz problemas de desempenho. Inserir ou
remover um elemento em um array muito grande exige deslocar muitos valores, tornando
as operações mais lentas. Além disso, nós grandes podem ficar parcialmente cheios,
desperdiçando espaço.

3. Estratégia de busca
Cada nó da Lista Encadeada Estendida mantém seus elementos ordenados, permitindo o
uso de busca binária dentro do próprio nó. Porém, como os nós não estão armazenados de
forma contínua na memória, não é possível aplicar uma busca binária global na lista inteira.
Assim, a busca é híbrida: sequencial (argh) entre os nós e binária (yeeeh, hehe) dentro de
cada nó. Isso melhora o desempenho em relação à lista encadeada simples, mas ainda
mantém custo linear no pior caso.

4. Conclusão
A Lista Encadeada Estendida combina as vantagens das listas encadeadas e dos arrays
ordenados, oferecendo melhor desempenho, economia de memória e uma organização de
dados mais eficiente. É uma estrutura útil para representar grandes conjuntos de dados que
precisam ser mantidos em ordem, mas sem o custo elevado de realocações de memória.

Você também pode gostar