Estructura de datos: lista enlazada circular

La lista enlazada circular es una variación de la lista enlazada en la que el primer elemento apunta al último elemento y el último elemento apunta al primer elemento. Tanto la lista enlazada individualmente como la lista enlazada doblemente se pueden convertir en una lista enlazada circular.

Lista enlazada individualmente como circular

En la lista enlazada individualmente, el siguiente puntero del último nodo apunta al primer nodo.

Lista doblemente enlazada como circular

En la lista doblemente enlazada, el siguiente puntero del último nodo apunta al primer nodo y el puntero anterior del primer nodo apunta al último nodo haciendo circular en ambas direcciones.

Según la ilustración anterior, los siguientes son los puntos importantes que deben considerarse.

• El siguiente enlace del último enlace apunta al primer enlace de la lista en ambos casos, tanto de lista individual como doblemente enlazada.

• El anterior del primer enlace apunta al último de la lista en el caso de una lista doblemente enlazada.

Operaciones básicas

A continuación se presentan las operaciones importantes respaldadas por una lista circular.

• insert - Inserta un elemento al principio de la lista.

• delete - Elimina un elemento del inicio de la lista.

• display - Muestra la lista.

Operación de inserción

El siguiente código demuestra la operación de inserción en una lista enlazada circular basada en una lista enlazada única.

Ejemplo

insertFirst(data):
Begin
   create a new node
   node -> data := data
   if the list is empty, then
      head := node
      next of node = head
   else
      temp := head
      while next of temp is not head, do
      temp := next of temp
      done
      next of node := head
      next of temp := node
      head := node
   end if
End

Operación de eliminación

El siguiente código demuestra la operación de eliminación en una lista enlazada circular basada en una lista enlazada única.

deleteFirst():
Begin
   if head is null, then
      it is Underflow and return
   else if next of head = head, then
      head := null
      deallocate head
   else
      ptr := head
      while next of ptr is not head, do
         ptr := next of ptr
      next of ptr = next of head
      deallocate head
      head := next of ptr
   end if
End

Operación de la lista de visualización

El siguiente código demuestra la operación de la lista de visualización en una lista enlazada circular.

display():
Begin
   if head is null, then
      Nothing to print and return
   else
      ptr := head
      while next of ptr is not head, do
         display data of ptr
         ptr := next of ptr
      display data of ptr
   end if
End

Para conocer su implementación en lenguaje de programación C, haga clic aquí .