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

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz