Lista enlazada circular: ventajas y desventajas

¿Qué es una lista enlazada circular?

Una lista circular enlazada es una secuencia de nodos dispuestos de tal manera que cada nodo pueda volver a sí mismo. Aquí un "nodo" es un elemento autorreferencial con punteros a uno o dos nodos en su vecindad inmediata.

A continuación se muestra una representación de una lista enlazada circular con 3 nodos.

Aquí puede ver que cada nodo es rastreable hasta sí mismo. El ejemplo que se muestra arriba es una lista circular enlazada individualmente.

Nota: La lista circular enlazada más simple es un nodo que rastrea solo hasta sí mismo, como se muestra.

Básico Operaciones en listas circulares enlazadas

Las operaciones básicas en una lista enlazada circular son:

1. Inserción
2. Eliminación y
3. Travesía

• La inserción es el proceso de colocar un nodo en una posición específica en la lista circular enlazada.
• La eliminación es el proceso de eliminar un nodo existente de la lista vinculada. El nodo puede identificarse por la aparición de su valor o por su posición.
• El recorrido de una lista enlazada circular es el proceso de mostrar el contenido completo de la lista enlazada y volver al nodo de origen.

En la siguiente sección, comprenderá la inserción de un nodo y los tipos de inserción posibles en una lista circular individualmente enlazada.

Inserción Operadisrupción

Inicialmente, necesitas crear un nodo que apunte a sí mismo como se muestra en esta imagen. Sin este nodo, la inserción crea el primer nodo.

A continuación, existen dos posibilidades:

• Inserción en la posición actual de la lista circular enlazada. Esto corresponde a la inserción al principio del final de una lista enlazada singular regular. En una lista circular enlazada, el principio y el final son iguales.
• Inserción después de un nodo indexado. El nodo debe identificarse mediante un número de índice correspondiente al valor de su elemento.

Para insertar al principio/final de la lista circular enlazada, es decir, en la posición donde se agregó el primer nodo,

• Tendrás que romper el autovínculo existente con el nodo existente.
• El siguiente puntero del nuevo nodo se vinculará al nodo existente.
• El siguiente puntero del último nodo apuntará al nodo insertado.

NOTA: El puntero que es el token maestro o el principio/final del círculo se puede cambiar. Aún así regresará al mismo nodo en un recorrido, que se analiza más adelante.

Los pasos en (a) i-iii se muestran a continuación:

(Nodo existente)

PASO 1) Romper el enlace existente

PASO 2) Crear un enlace directo (desde un nuevo nodo a un nodo existente)

PASO 3) Crear un enlace de bucle al primer nodo.

A continuación, intentará la inserción después de un nodo.

Por ejemplo, insertemos "VALOR2" después del nodo con "VALOR0". Supongamos que el punto de partida es el nodo con “VALOR0”.

• Tendrás que romper la línea entre el primer y segundo nodo y colocar el nodo con “VALOR2” en el medio.
• El siguiente puntero del primer nodo debe vincularse a este nodo, y el siguiente puntero de este nodo debe vincularse al segundo nodo anterior.
• El resto del acuerdo permanece sin cambios. Todos los nodos son rastreables hasta ellos mismos.

NOTA: Dado que existe una disposición cíclica, insertar un nodo implica el mismo procedimiento para cualquier nodo. El puntero que completa un ciclo completa el ciclo como cualquier otro nodo.

Esto se muestra a continuación:

(Digamos que sólo hay dos nodos. Este es un caso trivial)

PASO 1) Retire el enlace interno entre los nodos conectados.

PASO 2) Conecte el nodo del lado izquierdo al nuevo nodo

PASO 3) Conecte el nuevo nodo al nodo del lado derecho.

Eliminacion Operadisrupción

Supongamos una lista enlazada circular de 3 nodos. Los casos de eliminación se detallan a continuación:

• Eliminar el elemento actual
• Eliminación después de un elemento.

Eliminación al principio/final:

1. Atraviese hasta el primer nodo desde el último nodo.
2. Para eliminar desde el final, debe haber solo un paso transversal, desde el último nodo hasta el primer nodo.
3. Elimine el enlace entre el último nodo y el siguiente.
4. Vincula el último nodo al siguiente elemento del primer nodo.
5. Libera el primer nodo.

(Configuración existente)

PASO 1) Retire el enlace circular

PASOS 2) Eliminar el vínculo entre el primero y el siguiente, vincular el último nodo al nodo siguiente al primero.

PASO 3) Liberar/desasignar el primer nodo

Eliminación después de un nodo:

1. Recorra hasta que el siguiente nodo sea el nodo que se va a eliminar.
2. Vaya al siguiente nodo y coloque un puntero en el nodo anterior.
3. Conecte el nodo anterior al nodo posterior al nodo actual, utilizando su puntero siguiente.
4. Libere el nodo actual (desvinculado).

PASO 1) Digamos que necesitamos eliminar un nodo con "VALOR1".

PASO 2) Elimine el vínculo entre el nodo anterior y el nodo actual. Vincula su nodo anterior con el siguiente nodo señalado por el nodo actual (con VALOR1).

PASO 3) Liberar o desasignar el nodo actual.

Recorrido de una lista enlazada circular

Para recorrer una lista enlazada circular, comenzando desde un último puntero, verifique si el último puntero es NULL. Si esta condición es falsa, verifique si solo hay un elemento. De lo contrario, recorra usando un puntero temporal hasta que se alcance nuevamente el último puntero, o tantas veces como sea necesario, como se muestra en el GIF a continuación.

Ventajas de la lista enlazada circular

Algunas de las ventajas de las listas enlazadas circulares son:

1. No se requiere una asignación NULL en el código. La lista circular nunca apunta a un puntero NULL a menos que se desasigne por completo.
2. Las listas enlazadas circulares son ventajosas para las operaciones finales ya que el inicio y el final coinciden. Algorithms como la programación Round Robin puede eliminar claramente los procesos que están en cola de forma circular sin encontrar punteros colgantes o de referencia NULL.
3. La lista enlazada circular también realiza todas las funciones habituales de una lista enlazada individualmente. De hecho, circular listas doblemente enlazadas que se analiza a continuación puede incluso eliminar la necesidad de un recorrido completo para ubicar un elemento. Ese elemento, como máximo, solo estaría exactamente opuesto al inicio, completando solo la mitad de la lista vinculada.

Desventajas de la lista enlazada circular

Las desventajas de utilizar una lista enlazada circular se encuentran a continuación:

1. Las listas circulares son complejas en comparación con listas enlazadas individualmente.
2. RevEl uso de una lista circular es complejo en comparación con las listas simples o dobles.
3. Si no se maneja con cuidado, el código puede entrar en un bucle infinito.
4. Es más difícil encontrar el final de la lista y el control del bucle.
5. Insertando al Inicio, tenemos que recorrer la lista completa para encontrar el último nodo. (Perspectiva de implementación)

Lista enlazada individualmente como lista enlazada circular

Le recomendamos que intente leer e implementar el código siguiente. Presenta la aritmética de punteros asociada con listas circulares enlazadas.

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Explicación del código:

1. Las dos primeras líneas de código son los archivos de encabezado necesarios incluidos.
2. La siguiente sección describe la estructura de cada nodo autorreferencial. Contiene un valor y un puntero del mismo tipo que la estructura.
3. Cada estructura se vincula repetidamente con objetos de estructura del mismo tipo.
4. Existen diferentes prototipos de funciones para:
   1. Agregar un elemento a una lista enlazada vacía
   2. Insertando en el actualmente apuntado Posición de una lista circular enlazada.
   3. Insertar después de un particular indexado valor en la lista vinculada.
   4. Quitar/eliminar después de un particular indexado valor en la lista vinculada.
   5. Eliminar en la posición actual de una lista enlazada circular
5. La última función imprime cada elemento a través de un recorrido circular en cualquier estado de la lista vinculada.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
    
struct node *insertCurrent(struct node *last, int data)

Explicación del código:

1. Para el código addEmpty, asigne un nodo vacío usando la función malloc.
2. Para este nodo, coloque los datos en la variable temporal.
3. Asignar y vincular la única variable a la variable temporal
4. Devuelve el último elemento al contexto principal()/de la aplicación.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Explicación del código

1. Si no hay ningún elemento para insertar, debe asegurarse de agregarlo a una lista vacía y devolver el control.
2. Cree un elemento temporal para colocarlo después del elemento actual.
3. Vincule los punteros como se muestra.
4. Devuelve el último puntero como en la función anterior.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );


    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Explicación del código:

1. Si no hay ningún elemento en la lista, ignore los datos, agregue el elemento actual como el último elemento de la lista y devuelva el control.
2. Para cada iteración en el ciclo do- while, asegúrese de que haya un puntero anterior que contenga el último resultado recorrido.
3. Sólo entonces podrá ocurrir el siguiente recorrido.
4. Si se encuentran los datos, o si la temperatura llega al último puntero, el proceso do- while finaliza. La siguiente sección de código decide qué se debe hacer con el artículo.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Explicación del código:

1. Si se ha recorrido toda la lista, pero aún no se encuentra el elemento, muestre un mensaje de "elemento no encontrado" y luego devuelva el control a la persona que llama.
2. Si se encuentra un nodo y/o el nodo aún no es el último nodo, cree un nuevo nodo.
3. Enlace el nodo anterior con el nuevo nodo. Vincula el nodo actual con temp (la variable transversal).
4. Esto asegura que el elemento se coloque después de un nodo particular en la lista circular enlazada. Regrese a la persona que llama.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Explicación del código

1. Para eliminar solo el último nodo (actual), verifique si esta lista está vacía. Si es así, no se podrá eliminar ningún elemento.
2. La variable temporal simplemente atraviesa un enlace hacia adelante.
3. Vincula el último puntero al puntero después del primero.
4. Libere el puntero temporal. Desasigna el último puntero no vinculado.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Explicación del código

1. Al igual que con la función de eliminación anterior, verifique si no hay ningún elemento. Si esto es cierto, entonces no se podrá eliminar ningún elemento.
2. Punteros Se asignan posiciones específicas para localizar el elemento a eliminar.
3. Los punteros avanzan, uno detrás del otro. (anterior detrás de la temperatura)
4. El proceso continúa hasta que se encuentra un elemento, o el siguiente elemento retrocede hasta el último puntero.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;	

Explicación del programa

1. Si el elemento se encuentra después de recorrer toda la lista vinculada, se muestra un mensaje de error que dice que no se encontró el elemento.
2. De lo contrario, el elemento se desvincula y se libera en los pasos 3 y 4.
3. El puntero anterior está vinculado a la dirección señalada como “siguiente” por el elemento a eliminar (temp).
4. Por lo tanto, el puntero temporal se desasigna y se libera.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;    
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Explicación del código

1. El vistazo o el recorrido no es posible si no se necesitan ceros. El usuario necesita asignar o insertar un nodo.
2. Si solo hay un nodo, no es necesario atravesarlo, el contenido del nodo se puede imprimir y el ciclo while no se ejecuta.
3. Si hay más de un nodo, la temperatura imprime todo el elemento hasta el último elemento.
4. En el momento en que se alcanza el último elemento, el ciclo termina y la función devuelve la llamada a la función principal.

Aplicaciones de la Lista Enlazada Circular

• Implementación de programación por turnos en procesos del sistema y programación circular en gráficos de alta velocidad.
• Programación de Token Rings en redes informáticas.
• Se utiliza en unidades de visualización como tableros de tiendas que requieren un recorrido continuo de datos.