Estrutura de dados
737 palavras
3 páginas
ESTRUTURA DE DADOSListas Duplamente Ligadas
LISTA DUPLAMENTE LIGADA
IMPORTANTE SABER...
•
Até o momento aprendemos os conceitos de Pilhas, Filas e
Listas Ligadas, agora veremos aplicações mais robustas e flexíveis utilizando-se de Listas Duplamente Ligadas;
•
MANIPULAÇÃO: Ao utilizar Listas Duplamente Ligadas, não respeitaremos os conceitos de Pilhas ou Filas o que implica em manipulação de dados em diversos sentidos;
•
INICIO/FIM: Mesmo utilizando Listas Duplamente Ligadas devemos saber qual é o primeiro elemento da cadeia e também qual o ultimo.
LISTA DUPLAMENTE LIGADA
OS ELEMENTOS...
•
PONTEIROS (ANT/PROX): Cada elemento da Lista
Duplamente Ligada, contem além da informação um indicador que aponta para o elemento antecessor e outro indicador que aponta para o elemento sucessor;
LISTA DUPLAMENTE LIGADA
INSERÇÃO
•
INICIO: Insere um novo elemento no início da Lista;
•
APÓS/MEIO: Insere um novo elemento determinado elemento presente na Lista;
•
FINAL: Insere um novo elemento no final da Lista;
após
um
LISTA DUPLAMENTE LIGADA
INSERÇÃO
•
INICIO: Note que o elemento fisicamente é adicionado no final da Lista, no entanto, na sequencia lógica ele é o primeiro, perceba também que o ponteiro de início passou a apontar para o novo elemento. Sequencia anterior A – B nova sequencia C – A – B.
LISTA DUPLAMENTE LIGADA
INSERÇÃO
•
FINAL: Ao adicionarmos um elemento no final, devemos nos preocupar em fazer o ultimo elemento apontar para o novo elemento e reposicionar o ponteiro de final para o endereço onde se encontra o novo elemento;
Sequencia anterior C – A – B nova sequencia C – A – B – D.
LISTA DUPLAMENTE LIGADA
INSERÇÃO
•
APÓS ELEMENTO ‘X’: Ao adicionarmos um elemento após um elemento qualquer, devemos atualizar os ponteiros dos elementos adjacentes, imagine a sequencia ‘AB’, caso desejemos adicionar ‘C’ entre, devemos atualizar os ponteiros de ‘A’ e ‘B’. No exemplo