Listas enlazadas en C - Operaciones en listas circulares

Entorno circular

En una lista circular, el último nodo enlaza nuevamente con el primero, creando un recorrido continuo. Esta característica exige precauciones especiales para insertar, eliminar y recorrer sin caer en bucles infinitos. A continuación se describen las operaciones fundamentales.

typedef struct NodoCircular {
  int valor;
  struct NodoCircular *sig;
} NodoCircular;

typedef struct {
  NodoCircular *cola;
} ListaCircular;

void lista_circular_inicializar(ListaCircular *lista) {
  lista->cola = NULL;
}

7.1 Inserción conservando la circularidad

bool lista_circular_insertar(ListaCircular *lista, int valor) {
  NodoCircular *n = malloc(sizeof(NodoCircular));
  if (!n) return false;
  n->valor = valor;
  if (!lista->cola) {
    n->sig = n;
    lista->cola = n;
    return true;
  }
  n->sig = lista->cola->sig;
  lista->cola->sig = n;
  lista->cola = n;
  return true;
}

Lista vacía: El nuevo nodo se apunta a sí mismo, formando un ciclo de un solo elemento.
Lista no vacía: El nuevo nodo se inserta entre la cola y la cabeza para mantener la circularidad.

7.2 Recorrido con condición correcta

void lista_circular_imprimir(const ListaCircular *lista) {
  if (!lista->cola) return;
  const NodoCircular *inicio = lista->cola->sig;
  const NodoCircular *reco = inicio;
  do {
    printf("%d -> ", reco->valor);
    reco = reco->sig;
  } while (reco != inicio);
  puts("(inicio)");
}

El ciclo do...while garantiza que se recorra al menos un nodo y se detiene cuando vuelve al inicio.

7.3 Eliminación segura

bool lista_circular_eliminar(ListaCircular *lista, int valor) {
  if (!lista->cola) return false;
  NodoCircular *reco = lista->cola->sig;
  NodoCircular *ant = lista->cola;
  do {
    if (reco->valor == valor) {
      if (reco == ant) {
        free(reco);
        lista->cola = NULL;
      } else {
        ant->sig = reco->sig;
        if (reco == lista->cola) {
          lista->cola = ant;
        }
        free(reco);
      }
      return true;
    }
    ant = reco;
    reco = reco->sig;
  } while (reco != lista->cola->sig);
  return false;
}

7.4 Caso de un único nodo

Cuando la lista solo tiene un nodo, cola y cola->sig apuntan al mismo elemento. Las operaciones deben reconocer este escenario para evitar referencias incorrectas. En la función anterior se controla con if (reco == ant).

7.5 Prevención de loops infinitos

Siempre referencia un nodo inicial antes de recorrer.
Evita usar while (nodo); en listas circulares nunca se alcanza NULL.
Al insertar o eliminar, verifica que la referencia al nodo inicial siga siendo correcta.

7.6 Código completo para practicar en CLion

El siguiente set de archivos permite probar todas las operaciones:

/* lista_circular.h */
#ifndef LISTA_CIRCULAR_H
#define LISTA_CIRCULAR_H
#include <stdbool.h>

typedef struct NodoCircular {
  int valor;
  struct NodoCircular *sig;
} NodoCircular;

typedef struct {
  NodoCircular *cola;
} ListaCircular;

void lista_circular_inicializar(ListaCircular *lista);
bool lista_circular_insertar(ListaCircular *lista, int valor);
bool lista_circular_eliminar(ListaCircular *lista, int valor);
void lista_circular_imprimir(const ListaCircular *lista);
void lista_circular_limpiar(ListaCircular *lista);

#endif

/* lista_circular.c */
#include "lista_circular.h"
#include <stdio.h>
#include <stdlib.h>

void lista_circular_inicializar(ListaCircular *lista) {
  lista->cola = NULL;
}

bool lista_circular_insertar(ListaCircular *lista, int valor) {
  NodoCircular *n = malloc(sizeof(NodoCircular));
  if (!n) return false;
  n->valor = valor;
  if (!lista->cola) {
    n->sig = n;
    lista->cola = n;
    return true;
  }
  n->sig = lista->cola->sig;
  lista->cola->sig = n;
  lista->cola = n;
  return true;
}

bool lista_circular_eliminar(ListaCircular *lista, int valor) {
  if (!lista->cola) return false;
  NodoCircular *reco = lista->cola->sig;
  NodoCircular *ant = lista->cola;
  do {
    if (reco->valor == valor) {
      if (reco == ant) {
        free(reco);
        lista->cola = NULL;
      } else {
        ant->sig = reco->sig;
        if (reco == lista->cola) {
          lista->cola = ant;
        }
        free(reco);
      }
      return true;
    }
    ant = reco;
    reco = reco->sig;
  } while (reco != lista->cola->sig);
  return false;
}

void lista_circular_imprimir(const ListaCircular *lista) {
  if (!lista->cola) {
    puts("(lista vacía)");
    return;
  }
  const NodoCircular *inicio = lista->cola->sig;
  const NodoCircular *reco = inicio;
  do {
    printf("%d -> ", reco->valor);
    reco = reco->sig;
  } while (reco != inicio);
  puts("(inicio)");
}

void lista_circular_limpiar(ListaCircular *lista) {
  if (!lista->cola) return;
  NodoCircular *inicio = lista->cola->sig;
  NodoCircular *reco = inicio;
  do {
    NodoCircular *tmp = reco->sig;
    free(reco);
    reco = tmp;
  } while (reco != inicio);
  lista->cola = NULL;
}

/* main.c */
#include "lista_circular.h"
#include <stdio.h>

int main(void) {
  ListaCircular lista;
  lista_circular_inicializar(&lista);
  lista_circular_insertar(&lista, 5);
  lista_circular_insertar(&lista, 10);
  lista_circular_insertar(&lista, 15);
  lista_circular_imprimir(&lista);
  lista_circular_eliminar(&lista, 10);
  lista_circular_imprimir(&lista);
  lista_circular_limpiar(&lista);
  return 0;
}

Copia cada archivo en CLion, compila y verifica que las inserciones y eliminaciones mantengan la circularidad.

Retornar