Ayuda | Lista Circular

Lista Circular

Descripcion del TAD

Lista enlazada circular donde el ultimo nodo apunta nuevamente al primero. La interpretacion paso a paso debe evidenciar el cierre del ciclo en cada alta/baja de nodos para evitar rupturas o ciclos invalidos. La Lista Circular reutiliza el ultimo enlace para volver al primer nodo. La simulacion permite verificar que el ciclo nunca se rompa tras cada actualizacion de enlaces.

Objetivo

Conservar el cierre y terminar recorridos seguros.

Estrategia

Seguir HEAD/TAIL y detectar la vuelta al inicio.

Invariante

TAIL->next == HEAD cuando hay nodos.

Memoria dinámica

Actualizar el cierre antes de liberar el nodo retirado.

Errores frecuentes

Esperar NULL en un recorrido
Dejar TAIL apuntando a memoria liberada

Glosario contextual

Nodo: Objeto dinámico con datos y uno o más enlaces.
Enlace: Campo puntero que conecta objetos.
Alias: Dos punteros que designan el mismo objeto.
LIFO: El último en entrar es el primero en salir.
FIFO: El primero en entrar es el primero en salir.
Prioridad: Criterio de selección independiente del orden físico.
Circularidad: El último enlace vuelve al inicio.
malloc: Reserva memoria; puede devolver NULL.
free: Libera una reserva que deja de ser válida.

Controles de ejecucion paso a paso

Checkbox Interpretar codigo paso a paso: activado muestra toda la traza; desactivado aplica solo el resultado final.
Botones de ejecucion: Reproducir y Reiniciar.
Navegacion por traza: Anterior paso y Siguiente paso.
Velocidad de simulacion: slider de -2x a +2x (0.00x = 1.00x real).
En modo rapido (checkbox desactivado), el resultado visual final debe coincidir con el ultimo estado de la traza interpretada.
Al llegar al ultimo paso, Siguiente paso se bloquea hasta cambiar entradas/operacion; Anterior paso se habilita solo cuando ya avanzaste.

Operaciones soportadas

lcir_insertar_inicio
lcir_insertar_final
lcir_eliminar_inicio
lcir_eliminar_primero
lcir_buscar_posiciones
lcir_invertir
lcir_destruir

Operaciones pendientes / restricciones

No existe eliminar_final en el TAD suministrado.
No existe eliminar_posicion en el TAD suministrado.

Estructura del TAD en C

struct lcir_nodo {
    int valor;
    struct lcir_nodo *sgte;
};

typedef struct lcir_nodo LCirNodo;

typedef struct {
    LCirNodo *cabeza;  
    LCirNodo *cola;    
    int cantidad;      
} ListaCircular;

Metodos del TAD en C

Codigo C: insertar_inicio

Inserta nodo al inicio: enlaza el nuevo nodo antes del actual primero y actualiza la cabecera.

/**
 * @brief Inserta un nuevo elemento al inicio de la lista circular.
 *
 * @param[in,out] lista Puntero a la lista.
 * @param[in]     valor Dato a insertar.
 *
 * @return true si se insertó con éxito, false en caso de error.
 *
 * @post Si la lista estaba vacía, el nodo apunta a sí mismo.
 * @note Complejidad temporal: O(1) ya que se mantiene el puntero a la cola.
 */
bool lcir_insertar_inicio(ListaCircular *lista, int valor) {
    LCirNodo *nuevo;

    if (lista == NULL) {
        return false;
    }

    nuevo = lcir_crear_nodo(valor);
    if (nuevo == NULL) {
        return false;
    }

    if (lista->cabeza == NULL) {
        nuevo->sgte = nuevo;
        lista->cabeza = nuevo;
        lista->cola = nuevo;
        lista->cantidad = 1;
        return true;
    }

    nuevo->sgte = lista->cabeza;
    lista->cola->sgte = nuevo;
    lista->cabeza = nuevo;
    lista->cantidad++;
    return true;
}

Codigo C: insertar_final

Recorre hasta el ultimo nodo y conecta el nuevo elemento al final de la secuencia.

/**
 * @brief Inserta un nuevo elemento al final de la lista circular.
 *
 * @param[in,out] lista Puntero a la lista.
 * @param[in]     valor Dato a insertar.
 *
 * @return true si se insertó con éxito, false en caso de error.
 *
 * @note Complejidad temporal: O(1) debido a la existencia del puntero a la cola.
 */
bool lcir_insertar_final(ListaCircular *lista, int valor) {
    LCirNodo *nuevo;

    if (lista == NULL) {
        return false;
    }

    nuevo = lcir_crear_nodo(valor);
    if (nuevo == NULL) {
        return false;
    }

    if (lista->cabeza == NULL) {
        nuevo->sgte = nuevo;
        lista->cabeza = nuevo;
        lista->cola = nuevo;
        lista->cantidad = 1;
        return true;
    }

    nuevo->sgte = lista->cabeza;
    lista->cola->sgte = nuevo;
    lista->cola = nuevo;
    lista->cantidad++;
    return true;
}

Codigo C: eliminar_inicio

Remueve la cabecera, mueve el inicio al siguiente nodo y libera el nodo anterior.

/* Este TAD en C no define una funcion directa lcir_eliminar_inicio(). */
/* Se puede eliminar la cabeza usando lcir_eliminar_primero con su valor actual. */
int head;
int usados = lcir_copiar_valores(&lista, &head, 1);
if (usados == 1) {
    lcir_eliminar_primero(&lista, head);
}

Codigo C: eliminar_primero

Elimina la primera coincidencia de un valor y recompone enlaces para mantener continuidad.

/**
 * @brief Elimina el primer nodo que contenga el valor especificado.
 *
 * @param[in,out] lista Puntero a la lista.
 * @param[in]     valor Elemento a remover de la lista.
 *
 * @return true si el nodo fue eliminado, false si no se encontró.
 *
 * @post Reajusta cabeza y/o cola si fueron eliminadas.
 * @note Complejidad temporal: O(N) en el peor caso.
 */
bool lcir_eliminar_primero(ListaCircular *lista, int valor) {
    LCirNodo *actual;
    LCirNodo *anterior;

    if (lista == NULL || lista->cabeza == NULL) {
        return false;
    }

    actual = lista->cabeza;
    anterior = lista->cola;
    do {
        if (actual->valor == valor) {
            if (actual == lista->cabeza && actual == lista->cola) {
                free(actual);
                lista->cabeza = NULL;
                lista->cola = NULL;
                lista->cantidad = 0;
                return true;
            }

            anterior->sgte = actual->sgte;
            if (actual == lista->cabeza) {
                lista->cabeza = actual->sgte;
            }
            if (actual == lista->cola) {
                lista->cola = anterior;
            }
            free(actual);
            if (lista->cantidad > 0) {
                lista->cantidad--;
            }
            return true;
        }
        anterior = actual;
        actual = actual->sgte;
    } while (actual != lista->cabeza);

    return false;
}

Codigo C: buscar_posiciones

Recorre toda la lista y registra todas las posiciones donde aparece el valor buscado.

/**
 * @brief Busca un valor y guarda las posiciones (índices basados en 1) en las que aparece.
 *
 * @param[in]  lista     Puntero constante a la lista.
 * @param[in]  valor     Elemento a buscar.
 * @param[out] destino   Arreglo donde se escribirán las posiciones (1-based).
 * @param[in]  capacidad Capacidad máxima del arreglo de posiciones.
 *
 * @return El número de apariciones de dicho valor en la lista.
 *
 * @note Complejidad temporal: O(N), recorre la lista completa.
 */
int lcir_buscar_posiciones(const ListaCircular *lista, int valor, int *destino, int capacidad) {
    LCirNodo *actual;
    int encontrados = 0;
    int pos = 1;

    if (lista == NULL || lista->cabeza == NULL) {
        return 0;
    }

    actual = lista->cabeza;
    do {
        if (actual->valor == valor) {
            if (destino != NULL && encontrados < capacidad) {
                destino[encontrados] = pos;
            }
            encontrados++;
        }
        actual = actual->sgte;
        pos++;
    } while (actual != lista->cabeza);

    return encontrados;
}

Codigo C: invertir

Reasigna enlaces nodo a nodo para invertir la direccion completa de la lista.

/**
 * @brief Invierte la dirección de la lista circular internamente.
 *
 * @details
 * Recorre todos los nodos invirtiendo los punteros "sgte".
 * Al terminar, actualiza los punteros globales de cabeza y cola.
 *
 * @param[in,out] lista Puntero a la lista.
 *
 * @note Complejidad temporal: O(N).
 */
void lcir_invertir(ListaCircular *lista) {
    LCirNodo *prev;
    LCirNodo *curr;
    LCirNodo *next;
    LCirNodo *old_head;

    if (lista == NULL || lista->cabeza == NULL || lista->cabeza == lista->cola) {
        return;
    }

    prev = lista->cola;
    curr = lista->cabeza;
    do {
        next = curr->sgte;
        curr->sgte = prev;
        prev = curr;
        curr = next;
    } while (curr != lista->cabeza);

    old_head = lista->cabeza;
    lista->cabeza = lista->cola;
    lista->cola = old_head;
}

Codigo C: limpiar

Recorre la estructura liberando todos los nodos y deja el puntero raiz en estado nulo para reinicio seguro.

/**
 * @brief Libera la memoria de todos los nodos de la lista y la limpia.
 *
 * @param[in,out] lista Puntero a la lista.
 *
 * @post La estructura se reinicializa al estado vacío.
 * @note Complejidad temporal: O(N).
 */
void lcir_destruir(ListaCircular *lista) {
    LCirNodo *actual;
    LCirNodo *next;

    if (lista == NULL || lista->cabeza == NULL) {
        return;
    }

    actual = lista->cabeza->sgte;
    while (actual != NULL && actual != lista->cabeza) {
        next = actual->sgte;
        free(actual);
        actual = next;
    }
    free(lista->cabeza);
    lista->cabeza = NULL;
    lista->cola = NULL;
    lista->cantidad = 0;
}

/* Reinicio recomendado del TAD luego de liberar nodos */
/**
 * @brief Inicializa la estructura principal de la lista circular vacía.
 *
 * @param[in,out] lista Puntero a la estructura de la lista circular.
 *
 * @post La cabeza y cola quedan apuntando a NULL.
 * @note Complejidad temporal: O(1).
 */
void lcir_inicializar(ListaCircular *lista) {
    if (lista == NULL) {
        return;
    }
    lista->cabeza = NULL;
    lista->cola = NULL;
    lista->cantidad = 0;
}

Ir a la visualizacion