Listas Circulares

Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero.

La siguiente figura es una representación gráfica de una lista circular.

Enseguida se mostrarán los algoritmos más comunes en listas circulares. Al igual que en las secciones anteriores, utilizaremos el apuntador top para hacer referencia al primer nodo en la lista.

Algoritmo de creación

repite

new(p)

lee(p(dato))

si top=nil entonces

top<--p

q<--p

en caso contrario

q(liga)<--p

q<--p

p(liga)<--top

mensaje (otro nodo ?)

lee(respuesta)

hasta respuesta=no  

Algoritmo para recorrer la lista

p<--top

repite

escribe(p(dato))

p<--p(liga)

hasta p=top 

Algoritmo para insertar antes de 'X' información

new(p)

lee(p(dato))

si top=nil entonces

top<--p

p(liga)<--top

en caso contrario

mensaje(antes de ?)

lee(x)

q<--top

r<--top(liga)

repite

si q(dato)=x entonces

p(liga)<--q

r(liga)<--p

si p(liga)=top entonces

top<--p

q<--q(liga)

r<--r(liga)

hasta q=top 

Algoritmo para insertar después de 'X' información

new(p)

lee(p(dato))

mensaje(después de ?)

lee(x)

q<--top

r<--top(liga)

repite

si q(dato)=x entonces

q(liga)<--p

p(liga)<--r

q<--q(liga)

r<--r(liga)

hasta q=top 

Algoritmo para borrar

mensaje(valor a borrar )

lee(valor_a_borrar)

q<--top

r<--top

p<--top

mientras q(liga)<>top haz

q<--q(liga)

repite

si p(dato)=valor_a_borrar entonces

si p=top entonces

si top(liga)=top entonces

top<--NIL

en caso contrario

top<--top(liga)

q(liga)<--top

en caso contrario

r(liga)<--p(liga)

dispose(p)

p<--top

en caso contrario

r<--p

p<--p(liga)

hasta p=top