3 - Tipos de listas enlazadas

Panorama general

Una vez dominamos los nodos y punteros, el siguiente paso es diferenciar las variantes de listas. Existen tres familias clásicas: simplemente enlazadas, doblemente enlazadas y circulares. Cada una balancea memoria, complejidad y velocidad según el patrón de acceso que queremos resolver.

3.1 Lista simplemente enlazada

La lista simplemente enlazada conecta cada nodo con su sucesor mediante un único puntero sig. Es ideal para pilas, colas singulares o estructuras donde el recorrido siempre va hacia adelante.

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

typedef struct {
  NodoSimple *cabeza;
} ListaSimple;

bool lista_simple_insertar(ListaSimple *lista, int valor) {
  NodoSimple *n = malloc(sizeof(NodoSimple));
  if (!n) return false;
  n->valor = valor;
  n->sig = lista->cabeza;
  lista->cabeza = n;
  return true;
}

El código inserta al inicio en O(1). El costo de recorrer es lineal y no hay forma de retroceder sin usar estructuras auxiliares. Es la variante más económica en memoria porque solo guarda un puntero por nodo.

3.2 Lista doblemente enlazada

La lista doblemente enlazada agrega un puntero ant para navegar hacia atrás. Esto permite eliminaciones y recorridos bidireccionales más eficientes, a costa de mayor uso de memoria.

typedef struct NodoDoble {
  int valor;
  struct NodoDoble *ant;
  struct NodoDoble *sig;
} NodoDoble;

typedef struct {
  NodoDoble *cabeza;
  NodoDoble *cola;
} ListaDoble;

void lista_doble_insertar_final(ListaDoble *lista, int valor) {
  NodoDoble *n = malloc(sizeof(NodoDoble));
  if (!n) return;
  n->valor = valor;
  n->sig = NULL;
  n->ant = lista->cola;
  if (lista->cola) {
    lista->cola->sig = n;
  } else {
    lista->cabeza = n;
  }
  lista->cola = n;
}

Al mantener punteros a cabeza y cola, las inserciones en ambos extremos se vuelven O(1). El riesgo principal es olvidar actualizar ant y sig simultáneamente, lo que corrompe la lista.

3.3 Lista circular

En la lista circular, el último nodo enlaza de vuelta al primero. Esta propiedad se aplica tanto a variantes simples como dobles y resulta útil para algoritmos que requieren recorrer indefinidamente, como planificadores round-robin.

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

typedef struct {
  NodoCircular *cola;
} ListaCircular;

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

void lista_circular_recorrer(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("");
}

El recorrido utiliza un ciclo do...while para garantizar que se visite cada nodo una sola vez. Las listas circulares simplifican la implementación de buffers que necesitan reutilizar posiciones sin detener el flujo.