Lista duplamente ligada

Prévia do material em texto

Lista duplamente ligada
Customização Dúvidas ao tutorUnidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão

Fe
ed
ba
ck
Uma limitação da ED lista simplesmente ligada é que qualquer
inserção/remoção/leitura feita no final da lista tem um custo computacional alto,
pois é preciso percorrer todos os nós da lista até encontrar a última posição. Esse
custo é ainda maior se quisermos, por exemplo, percorrer a lista de trás para frente,
ou seja, do último elemento para o primeiro.
Para tentar mitigar essas limitações, surgiu o conceito de lista duplamente ligada.
Há duas diferenças importantes da lista duplamente ligada para a lista simplesmente
ligada.
Diferenças entre a lista duplicamente ligada e lista simplesmente ligada. Fonte: elaborado pelo autor.
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
Veja as alterações necessárias no código das structs “Lista” e “No” de uma lista
duplamente ligada:
struct No {
 int info;
 struct No* anterior;
 struct No* proximo;
};
struct ListaDupla {
 struct No* inicio;
 struct No* fim;
 int tamanho;
};
Para diferenciarmos da lista simplesmente ligada, nós mudamos o nome da struct
“Lista” para “ListaDupla”.
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
A ilustração de uma lista duplamente ligada pode ser visualizada na figura –
Ilustração do processo de busca de um nó a ser removido da lista. A seta apontada
para a esquerda representa o ponteiro “anterior” de um nó.
Ilustração do processo de busca de um nó a ser removido da lista - Fonte: elaborada pelos autores.
A partir de agora, apresentaremos as mesmas operações da lista simplesmente
ligada, comentando a diferença de implementação para o caso da lista duplamente
ligada.
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
Comecemos pela função “criar” (código - Função para criar uma lista duplamente
encadeada).
Função para criar uma lista duplamente encadeada - Fonte: elaborada pelos autores.
A única diferença, para esta função, é que agora temos que inicializar também o
ponteiro “fim” da struct “ListaDupla” com o valor NULL, pois a lista é criada vazia.
O código da função “vazia” se mantém praticamente o mesmo, a não ser pelo nome
da struct que mudou para “ListaDupla” (código - Função para verificar se uma lista
duplamente encadeada está vazia). Isso porque a forma de verificar se uma lista está
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
vazia é a mesma, tanto para a lista simplesmente ligada quanto para a duplamente
ligada.
Função para verificar se uma lista duplamente encadeada está vazia - Fonte: elaborada pelos autores.
O mesmo ocorre com as funções “tamanho” e “liberar”. Assim, o código dessas
funções não será apresentado aqui novamente.
Vamos, então, olhar para aquelas funções que sofreram maiores modificações, a
saber, as funções “inserir” e “remover”. Isso porque agora nós temos que atualizar
também os ponteiros “anterior”, da struct “No”, e “fim”, da struct “ListaDupla”.
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
Vamos começar pela função “inserir”, cujo código encontra-se no código – Função
inserir um elemento em uma lista duplamente encadeada.
Função inserir um elemento em uma lista duplamente encadeada - Fonte: elaborada pelos autores.
No trecho de código das linhas 8 a 13, que trata da inserção do início da lista, foi
preciso incluir instruções para atualizar o ponteiro “anterior” do novo nó para
NULL, pois não há nós anteriores ao nó inicial. 
Também foi preciso atualizar o ponteiro “fim” da lista, no caso de ser a inserção do
primeiro elemento da lista, ou seja, quando a lista tem apenas um elemento, tanto o
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
ponteiro “inicio” quanto o “fim” apontam para o mesmo elemento. O bloco else-if
das linhas 14 a 18 é inédito e trata da inserção no final da lista. 
Agora, como temos acesso direto ao último elemento da lista, não precisaremos mais
percorrê-la até o fim. Basta atualizarmos o ponteiro “fim” da lista. Essa é a grande
vantagem da lista duplamente ligada: a inserção de um elemento tanto no início da
lista quanto no seu fim tem um desempenho muito bom.
Por fim, o trecho de código das linhas 19 a 27, que trata da inserção de um elemento
em qualquer posição entre o primeiro e o último elemento, é bem similar ao da lista
simplesmente ligada, com a exceção que, agora, é preciso atualizar o ponteiro
“anterior” do nó que está sendo inserido.
Passando agora para a função “remover”, o código para a lista duplamente ligada
está no código – Função remover um elemento em uma lista duplamente encadeada
–, conforme podemos ver a seguir:
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
Função remover um elemento em uma lista duplamente encadeada - Fonte: elaborada pelos autores.
De forma análoga ao que fizemos na função “inserir”, também precisamos verificar
se se trata de uma remoção no início da lista, no fim ou em qualquer outra posição
entre o início e o fim. Isso é feito por meio do comando if-else-if, contido no código.
Caso seja uma remoção no início da lista, além do que já fizemos para a lista
simplesmente ligada, devemos atualizar o ponteiro “anterior” do nó que estava na
segunda posição da lista, bem como do ponteiro “fim”, da lista (caso a lista tenha
ficado vazia) – linhas 8 a 13. 
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
Também criamos uma sequência de instruções para o caso de a remoção ocorrer no
final da lista (linhas 15 a 17). Nesse caso, devemos atualizar o ponteiro “fim” da lista
(linha 16), bem como o ponteiro “próximo” do penúltimo nó da lista, fazendo-o
apontar para NULL, pois ele passará a ser o último nó da lista (linha17). 
Por último, das linhas 19 a 28, temos o caso de remoção para qualquer elemento
entre o primeiro e o último elemento.
As diferenças para a função remover da lista simplesmente ligada são que, agora,
precisamos atualizar o ponteiro “anterior” do elemento subsequente ao que será
sendo removido (linha 28).
A sequência de comandos responsável por liberar espaço da memória e retornar a
informação contida no elemento removido (linhas 31 a 34) mantém-se a mesma da
função da lista simplesmente ligada.
Para terminar, vejamos o código da função “obter” para a lista duplamente ligada
(código – Função obter um elemento em uma lista duplamente encadeada).
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
Função obter um elemento em uma lista duplamente encadeada - Fonte: elaborada pelos autores.
A diferença dessa função é que, agora, temos condições de acessar a última posição
da lista sem ter que percorrê-la, como era feito na lista simplesmente ligada. Isso é
feito acessando diretamente o ponteiro “fim” na lista, como mostra a linha 9.
Chegamos ao final desta aula. Você pode encontrar o código completo da lista
duplamente ligada a seguir, utilizando a ferramenta Paiza.io.
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
https://paiza.io/projects/JLmYkgv7BjluTh4A624qTw
Bons estudos!
Avalie este conteúdo Escolha de 1 a 5 estrelas
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck
Conteúdo anterior Próximo conteúdoUnidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Vídeoaula: Operações com Listas
Ligadas
Conclusão
Fe
ed
ba
ck