Lista enlazada circular: ventajas y desventajas

¿Qué es una lista enlazada circular?

Una lista enlazada circular es una secuencia de nodos dispuestos de manera que cada nodo pueda ser...traccada “nodo” es un elemento autorreferencial con punteros a uno o dos nodos en su proximidad inmediata.

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

Aquí, puedes ver que cada nodo es retraccapaz de sí misma. El ejemplo que se muestra arriba es una lista enlazada simple circular.

Nota: La lista enlazada circular más simple es un único nodo cuyo puntero siguiente tracvuelve a sí mismo, como se muestra a continuación.

Básico Operaciones en listas enlazadas circulares

Las tres 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 todo el contenido de la lista enlazada y volver a mostrarlo.tracvolviendo al nodo de origen.

La siguiente sección explica cómo funciona la inserción y los dos tipos de inserción posibles en una lista circular enlazada simple.

Inserción Operadisrupción

Primero, crea un nodo cuyo puntero next apunte a sí mismo, como se muestra a continuación. Sin este nodo semilla, la primera inserción se convierte en el primer nodo de la lista.

A continuación, existen dos posibilidades:

• Inserción en la posición actual de la lista enlazada circular. Esto equivale a insertar un elemento al principio o al final de una lista enlazada simple regular; en una lista enlazada circular, el principio y el final coinciden.
• 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 un nodo al principio o al final de la lista enlazada circular, es decir, en la posición donde se agregó el primer nodo, siga los pasos que se indican a continuación:

• 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 marca el inicio o el final del círculo se puede reasignar a cualquier nodo. El recorrido seguirá devolviendo al mismo nodo, como se explica más adelante en este artículo.

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, inserte “VALUE2” después del nodo que contiene “VALUE0”, suponiendo que el punto de partida es el nodo con “VALUE0”.

• Rompe el vínculo entre el primer y el segundo nodo, y coloca el nodo con “VALUE2” en medio.
• El puntero siguiente del primer nodo apunta al nuevo nodo, y el puntero siguiente del nuevo nodo apunta a lo que antes era el segundo nodo.
• El resto de la disposición permanece sin cambios. Todos los nodos son retraccapaces de hacerlo por sí mismos.

NOTA: Debido a que la disposición es cíclica, el procedimiento para insertar un nodo es idéntico independientemente de la posición que se elija. El puntero que cierra el ciclo se comporta como cualquier otro puntero de la lista.

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 dos casos de eliminación son:

• 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. Eliminar elementos desde el final requiere solo un paso de recorrido, desde el último nodo hasta el primero.
3. Elimine el enlace entre el último nodo y el primer nodo.
4. Vincula el último nodo al siguiente elemento del primer nodo.
5. Libera el primer nodo.

(Configuración existente)

Paso 1) Eliminar el enlace circular

Paso 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. Recorre la lista hasta que el siguiente nodo sea el 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, luego vincule el nodo anterior directamente al nodo al que apunta el puntero siguiente del nodo actual (el nodo después de VALUE1).

Paso 3) Liberar o desasignar el nodo actual.

Recorrido de una lista enlazada circular

Para recorrer una lista enlazada circular desde el último puntero, primero compruebe si este es nulo. Si no lo es, verifique si la lista tiene un solo elemento. De lo contrario, recorra la lista con un puntero temporal hasta llegar nuevamente al último puntero, como se muestra en la animación 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 de final de lista porque el principio y el final coinciden. Algorithms Los métodos de planificación como round-robin pueden recorrer los procesos en cola de forma limpia, sin encontrar punteros colgantes o nulos.
3. Una lista enlazada circular aún admite todas las operaciones regulares de una lista enlazada simple. lista doblemente enlazada Incluso puede eliminar la necesidad de recorrer toda la lista para localizar un elemento; en el peor de los casos, el objetivo se encuentra frente al puntero de inicio, por lo que como máximo es necesario recorrer la mitad de la lista.

Desventajas de la lista enlazada circular

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

1. Las listas circulares son más complejas que listas enlazadas individualmente.
2. RevInvertir una lista circular es más complejo que invertir una lista enlazada simple o doble.
3. Si la terminación del bucle no se maneja con cuidado, el código de recorrido puede entrar en un bucle infinito.
4. Es más difícil encontrar el final de la lista y escribir las condiciones de control de bucle correctas.
5. Insertar al principio requiere recorrer toda la lista para llegar al último nodo (desde una perspectiva de implementación).

Lista enlazada individualmente como lista enlazada circular

Le recomendamos leer e implementar el código C que aparece a continuación. Este código ilustra la aritmética de punteros asociada a una lista enlazada simple circular.

#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 define la estructura de cada nodo autorreferencial. Contiene un valor y un puntero del mismo tipo que la estructura.
3. Cada instancia de estructura se vincula con otros 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 addToEmpty, asigne un nodo vacío utilizando la función malloc().
2. Coloque los datos entrantes en el nodo temporal.
3. Asigne el nodo temporal al último nodo y establezca su puntero siguiente hacia sí mismo, de modo que el nodo único apunte de nuevo hacia sí mismo.
4. Devuelve el último puntero 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 la lista está vacía, pase el control a addToEmpty() y devuelva el control.
2. Crea un nodo temporal para colocarlo después del nodo actual.
3. Conecte los punteros como se muestra en el diagrama anterior.
4. Devuelve el último puntero, que coincide con el patrón utilizado 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 la lista está vacía, ignore la clave de búsqueda, agregue el elemento actual como el único nodo en la lista y devuelva el control.
2. En cada iteración del bucle do-while, un puntero anterior almacena el último resultado recorrido.
3. Solo entonces se produce el siguiente paso del recorrido.
4. El bucle do-while finaliza cuando se encuentran los datos de destino o cuando temp vuelve a alcanzar el último puntero. El siguiente bloque de código decide qué hacer con el elemento encontrado.

...
    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 no se encuentra el elemento, muestre un mensaje de "Elemento no encontrado" y devuelva el control a quien realizó la llamada.
2. Si se encuentra el nodo de destino, asigne un nuevo nodo para insertar el valor.
3. Enlace el nodo anterior al nuevo nodo, y vincular el puntero siguiente del nuevo nodo a temp (la variable de recorrido).
4. Esto coloca el nuevo elemento inmediatamente después del nodo de destino en la lista enlazada circular. A continuación, el control regresa a quien realizó la llamada.

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 el último nodo (el actual), primero compruebe si la lista está vacía. Si lo está, no se puede eliminar ningún elemento.
2. La variable temporal avanza un enlace.
3. Vincula el último puntero al nodo siguiente al primer nodo.
4. Libere el puntero temporal para desasignar el nodo 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, primero compruebe si la lista está vacía. Si lo está, no se puede eliminar ningún elemento.
2. Dos punteros Se asignan posiciones específicas para localizar el elemento a eliminar.
3. Los punteros avanzan uno tras otro (temperatura de los senderos anteriores).
4. El recorrido continúa hasta que se encuentra el elemento de destino o el siguiente puntero vuelve a alcanzar el último nodo.

    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 se recorre toda la lista enlazada sin encontrar el elemento deseado, se muestra un mensaje de "Elemento no encontrado".
2. De lo contrario, el elemento se desvincula y se libera en los pasos 3 y 4.
3. El puntero anterior está vinculado al nodo al que apunta el siguiente puntero de temp (el nodo que sigue al que se está eliminando).
4. A continuación, se libera el puntero temporal.

...
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 recorrido de exploración no es posible si no hay nodos; el usuario primero debe asignar o insertar un nodo.
2. Si solo hay un nodo, no es necesario recorrerlo: el contenido del nodo se imprime directamente y el bucle while no se ejecuta.
3. Si hay más de un nodo, la función temp imprime todos los elementos hasta el último.
4. En el momento en que se alcanza el último elemento, el bucle termina y la función devuelve el control a main().

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.
• Planificación mediante anillo de tokens en redes informáticas.
• Se utiliza en unidades de visualización, como por ejemplo en paneles digitales para tiendas, que requieren un desplazamiento continuo de datos.

Preguntas Frecuentes