Lista Lista

Duplamente Duplamente

Encadeada Encadeada

EstruturasdeDados EstruturasdeDados

Prof.AlexSandro alexscunha@yahoo.com.br

ListaDuplamenteEncadeada

Encadeamentosimples

Nóssãoalocadosdinamicamenteeligados entresiporapontadores

Cadaelementopossuiumlinkparaopróximonódalista.

Desvantagem

Nãotemoscomopercorrereficientementeosnósnaordem inversa;

Dificultaaretiradadonó

Parateracessoaonóanterioraoqueestamosposicionado,temos queusarumponteirorastreador.

Solução:

Colocarmaisumlinknonó!

Alémdonodoapontarparaoseusucessor,também apontaráparaoseuantecessor.

ListaDuplamenteEncadeada

Oqueganhamoscomisso?

Dadoumelemento,poderemosacessarambosos elementosadjacentes:opróximoeoanterior

Retirarelementosconhecendo-seapenaso endereçodonó

Inserçãoàdireitaeàesquerdadeumnó

Setivermosumponteiroparaoúltimoelementoda lista,poderemospercorrê-lanaordeminversa.

Primeironododalistapossuioponteiroparaoanteriorigual aNULL

Representação ed1 javadelphi Lista

ListaDuplamenteEncadeada

Desvantagens

Parapercorreralistadeformainversa,é necessárioqueumapontadorsejadeslocado atéoúltimonó

ListaDuplamenteEncadeada

Observações:

OprimeironododalistapossuiovalorNULLparaos ponteirossucessoreantecessor

Oquevaisermodificadonainserção? ed1 javadelphi Lista ed1 javadelphi Lista

ListaDuplamenteEncadeada

Quemodificaçõesteremosquerealizarem relaçãoarepresentaçãosimplesmente encadeada?

EstruturadeDados: typedef struct stnolista { int dado; struct stnolista *prox; struct stnolista *ant;

}no; typedef no* lista;

Operações:

voidcriar(lista*lst); intvazia(listalst); inttamanho(listalst); intinserir(lista*lst,intposicao,intvalor); intbusca(listalst,intvalor); intretira(lista*lst,intposicao,int*valor); intelemento(listalst,intposicao,int*valor);

ListaDuplamenteEncadeada

EstruturadeDados

Bibliografia

C.,BOCKMAN,C.“Estruturasdedados:

conceitosetécnicasdeimplementação”.Riode Janeiro:Campus,1993.

M.“EstruturasdedadosusandoC”.São Paulo:Bookman,1995.

Comentários