wordpress

Check if a Given Linked List is Circular Linked List – Simple Methods

Una lista enlazada es una estructura de datos lineal en la que los elementos están almacenados en nodos. Cada nodo contiene un valor y un puntero que apunta al siguiente nodo en la lista. En una lista enlazada simple, el último nodo apunta a NULL, lo que indica el final de la lista.

Por otro lado, una lista enlazada circular es aquella en la que el último nodo apunta al primer nodo de la lista, creando así un ciclo. Esto significa que se puede recorrer la lista enlazada de forma continua, sin llegar a un final.

En este artículo, exploraremos diferentes métodos para verificar si una lista enlazada dada es una lista enlazada circular. Estos métodos son simples y fáciles de implementar.

Implementación de una lista enlazada

Antes de profundizar en cómo verificar si una lista enlazada es circular, es importante comprender cómo se implementa una lista enlazada en primer lugar.

Una lista enlazada se implementa utilizando nodos. Cada nodo contiene un valor y un puntero que apunta al siguiente nodo en la lista. El primer nodo de la lista se llama «cabeza» y el último nodo se llama «cola». El puntero del último nodo apunta a NULL, lo que indica el final de la lista.

A continuación se muestra una implementación básica de una lista enlazada en lenguaje C:


#include 
#include 

// Definición de la estructura de un nodo
struct Node {
    int data;
    struct Node* next;
};

// Función para imprimir los elementos de la lista enlazada
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
}

int main() {
    // Creación de los nodos de la lista enlazada
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // Asignación de memoria para los nodos
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    // Asignación de valores a los nodos
    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    // Imprimir la lista enlazada
    printList(head);

    return 0;
}

En este ejemplo, creamos una lista enlazada con tres nodos. Cada nodo contiene un valor y un puntero que apunta al siguiente nodo en la lista. La función printList se utiliza para imprimir los elementos de la lista enlazada.

Verificación de una lista enlazada circular

Para verificar si una lista enlazada es circular, debemos encontrar si el puntero del último nodo apunta al primer nodo de la lista. Si es así, la lista enlazada es circular; de lo contrario, no lo es.

Existen diferentes métodos para verificar si una lista enlazada es circular. En este artículo, exploraremos un algoritmo simple para lograrlo.

Algoritmo para verificar una lista enlazada circular

El algoritmo para verificar si una lista enlazada es circular es bastante sencillo. A continuación se muestra el algoritmo paso a paso:

  1. Inicializar dos punteros, slow y fast, al primer nodo de la lista enlazada.
  2. Mover el puntero slow un paso a la vez, y el puntero fast dos pasos a la vez.
  3. Si el puntero fast alcanza el final de la lista (es decir, el puntero fast->next es NULL), la lista enlazada no es circular.
  4. Si el puntero fast alcanza el puntero slow en algún momento, la lista enlazada es circular.

Este algoritmo funciona porque si la lista enlazada es circular, el puntero fast eventualmente alcanzará al puntero slow en algún punto. Si la lista enlazada no es circular, el puntero fast alcanzará el final de la lista antes de alcanzar al puntero slow.

Ejemplo de código

A continuación se muestra un ejemplo de código en lenguaje C que implementa el algoritmo descrito anteriormente para verificar si una lista enlazada es circular:


#include 
#include 

// Definición de la estructura de un nodo
struct Node {
    int data;
    struct Node* next;
};

// Función para verificar si una lista enlazada es circular
int isCircular(struct Node* head) {
    // Caso base: si la lista enlazada está vacía, no es circular
    if (head == NULL) {
        return 0;
    }

    // Inicializar los punteros slow y fast al primer nodo de la lista
    struct Node* slow = head;
    struct Node* fast = head;

    // Mover el puntero slow un paso a la vez y el puntero fast dos pasos a la vez
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        // Si el puntero fast alcanza al puntero slow, la lista es circular
        if (slow == fast) {
            return 1;
        }
    }

    // Si el puntero fast alcanza el final de la lista, la lista no es circular
    return 0;
}

int main() {
    // Creación de los nodos de la lista enlazada
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // Asignación de memoria para los nodos
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    // Asignación de valores a los nodos
    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = head; // Haciendo que el último nodo apunte al primer nodo

    // Verificar si la lista enlazada es circular
    if (isCircular(head)) {
        printf("La lista enlazada es circular.");
    } else {
        printf("La lista enlazada no es circular.");
    }

    return 0;
}

En este ejemplo, creamos una lista enlazada con tres nodos. El último nodo apunta al primer nodo, lo que crea un ciclo y hace que la lista enlazada sea circular. La función isCircular se utiliza para verificar si la lista enlazada es circular o no.

Conclusión

Verificar si una lista enlazada es circular es un problema común en la programación. En este artículo, hemos explorado diferentes métodos para lograrlo. Hemos discutido cómo implementar una lista enlazada y cómo verificar si es circular utilizando un algoritmo simple.

Espero que este artículo te haya ayudado a comprender cómo verificar si una lista enlazada dada es una lista enlazada circular. Recuerda que la implementación de una lista enlazada y la verificación de su circularidad son conceptos fundamentales en la programación y pueden ser útiles en muchos escenarios.

Recomendado:  Generating Migrations en Laravel: Sintaxis para generar migraciones

Author

osceda@hotmail.com

Leave a comment

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *