Listas encadeadas

Prévia do material em texto

ESTRUTURA DE DADOS:
TIPOS DE LISTAS ENCADEADAS:
Serão apresentados os algoritmos de inclusão no final e exclusão no início da lista,
para cada um dos tipos de lista linear encadeada.
Lista Simplesmente Encadeada (LSE):
 i
 10 20 30 40 ^
INCLUSÃO (FINAL): EXCLUSÃO (INÍCIO):
ALOQUE(t) IF i = ^
INFOt ß VALOR THEN “Lista vazia”
PROXt ß ^ ELSE p ß i
IF i = ^ i ß PROXi
THEN i ß t DESALOQUE(p)
ELSE PROXf ß t
f ß t
t ß ^
Lista Simplesmente Encadeada Circular (LSEC):
 i
 10 20 30 40
INCLUSÃO (FINAL): EXCLUSÃO (INÍCIO):
ALOQUE(t) IF i = ^
INFOt ß VALOR THEN “Lista vazia”
IF i = ^ ELSE p ß i
 THEN i ß t i ß PROXi
PROXi ß i PROXf ß i
 ELSE PROXt ß i DESALOQUE(p)
PROXf ß t
f ß t
t ß ^
Lista Simplesmente Encadeada com Header (LSEH):
 i
 10 20 30 40 ^
INCLUSÃO (FINAL): EXCLUSÃO (INÍCIO):
ALOQUE(t) IF PROXi = ^
INFOt ß VALOR THEN “Lista vazia”
PROXt ß ^ ELSE p ß PROXi
PROXf ß t PROXi ß PROXp
f ß t IF PROXi = ^
t ß ^ THEN f ß i
 DESALOQUE(p)
Lista Simplesmente Encadeada Circular com Header (LSECH):
 i
 10 20 30 40
INCLUSÃO (FINAL): EXCLUSÃO (INÍCIO):
ALOQUE(t) IF PROXi = i
INFOt ß VALOR THEN “Lista vazia”
PROXt ß i ELSE p ß PROXi
PROXf ß t PROXi ß PROXp
f ß t IF PROXi = i
t ß ^ THEN f ß i
 DESALOQUE(p)
Lista Duplamente Encadeada (LDE):
 i
 ^ 10 20 30 40 ^
INCLUSÃO (FINAL): EXCLUSÃO (INÍCIO):
ALOQUE(t) IF i = ^
INFOt ß VALOR THEN “Lista vazia”
PROXt ß ^ ELSE p ß i
IF i = ^ i ß PROXi
THEN i ß t IF i <> ^
 f ß t THEN ANTi ß ^
 ANTi ß ^ DESALOQUE(p)
ELSE PROXf ß t
 ANTt ß f
 f ß t
t ß ^
Lista Duplamente Encadeada Circular (LDEC):
 i
 10 20 30 40
INCLUSÃO (FINAL): EXCLUSÃO (INÍCIO):
ALOQUE(t) IF i = ^
INFOt ß VALOR THEN “Lista vazia”
IF i = ^ ELSE p ß i
 THEN f ß t i ß PROXi
 i ß t PROXf ß i
 PROXi ß i ANTi ß f
 ANTi ß i DESALOQUE(p)
 ELSE ANTt ß f
 PROXt ß PROXf
 ANTi ß t
 PROXf ß t
 f ß t
t ß ^
Lista Duplamente Encadeada com Header (LDEH):
 i
 ^ 10 20 30 40 ^
INCLUSÃO (FINAL): EXCLUSÃO (INÍCIO):
ALOQUE(t) IF PROXh = ^
INFOt ß VALOR THEN “Lista vazia”
PROXt ß ^ ELSE p ß PROXh
PROXf ß t PROXh ß PROXp
ANTt ß f IF PROXp <> ^
f ß PROXf THEN ANTPROXp ß h
 t ß ^ ELSE f ß h
 DESALOQUE(p)
Lista Duplamente Encadeada Circular com Header (LDECH):
 i
 10 20 30 40
INCLUSÃO (FINAL): EXCLUSÃO (INÍCIO):
ALOQUE(t) IF PROXh = h
INFOt ß VALOR THEN “Lista vazia”
PROXt ß h ELSE p ß PROXh
ANTt ß ANTh PROXh ß PROXp
ANTh ß t ANTPROXp ß ANTp
PROXANTt ß t DESALOQUE(p)
t ß ^