Listas enlazadas en C - Operaciones en listas dobles

Control total en ambos sentidos

Las listas doblemente enlazadas incorporan dos punteros en cada nodo: ant y sig. Esto habilita recorridos en ambos sentidos y eliminaciones más eficientes, a cambio de mayor complejidad de mantenimiento. Las siguientes secciones detallan cada operación básica con ejemplos en C.

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

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

void lista_doble_inicializar(ListaDoble *lista) {
  lista->cabeza = NULL;
  lista->cola = NULL;
}

6.1 Inserción al inicio

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

Reserva y asignación: Se crea un nuevo nodo con malloc y se llenan sus campos.
Actualización de punteros: Si la lista estaba vacía, cabeza y cola apuntan al nuevo nodo; de lo contrario, se enlaza como anterior del que era cabeza.

6.2 Inserción al final

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

6.3 Eliminación eficiente

Al conocer el nodo objetivo, una lista doble permite eliminarlo sin recorrer desde la cabeza. Solo se actualizan los punteros de sus vecinos.

void lista_doble_eliminar_nodo(ListaDoble *lista, NodoDoble *nodo) {
  if (!nodo) return;
  if (nodo->ant) {
    nodo->ant->sig = nodo->sig;
  } else {
    lista->cabeza = nodo->sig;
  }
  if (nodo->sig) {
    nodo->sig->ant = nodo->ant;
  } else {
    lista->cola = nodo->ant;
  }
  free(nodo);
}

Casos en extremos: Si el nodo es cabeza o cola, se actualizan los punteros globales.
Enlaces centrales: Los punteros ant y sig de los vecinos se reasignan para saltar al nodo eliminado.

6.4 Recorrido hacia adelante

void lista_doble_imprimir(const ListaDoble *lista) {
  const NodoDoble *reco = lista->cabeza;
  while (reco) {
    printf("%d -> ", reco->valor);
    reco = reco->sig;
  }
  puts("NULL");
}

6.5 Recorrido hacia atrás

void lista_doble_imprimir_inverso(const ListaDoble *lista) {
  const NodoDoble *reco = lista->cola;
  while (reco) {
    printf("%d <- ", reco->valor);
    reco = reco->ant;
  }
  puts("NULL");
}

6.6 Consideraciones cuando la lista está vacía

En listas dobles es crucial mantener sincronizados cabeza y cola. Siempre que se elimine el único nodo, ambos deben quedar en NULL. Del mismo modo, al insertar el primer elemento se inicializan de forma conjunta.

Verifica ant y sig antes de acceder: pueden ser NULL.
Al limpiar la lista, recorre con cuidado para no perder la referencia a los nodos siguientes.
Evita mezclar funciones pensadas para listas simples con listas dobles; los punteros adicionales requieren atención especial.

6.7 Código completo para practicar en CLion

El siguiente conjunto de archivos permite copiar y pegar en CLion para probar todas las operaciones descritas:

/* lista_doble.h */
#ifndef LISTA_DOBLE_H
#define LISTA_DOBLE_H
#include <stdbool.h>

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

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

void lista_doble_inicializar(ListaDoble *lista);
bool lista_doble_insertar_inicio(ListaDoble *lista, int valor);
bool lista_doble_insertar_final(ListaDoble *lista, int valor);
void lista_doble_eliminar_nodo(ListaDoble *lista, NodoDoble *nodo);
void lista_doble_imprimir(const ListaDoble *lista);
void lista_doble_imprimir_inverso(const ListaDoble *lista);
void lista_doble_limpiar(ListaDoble *lista);

#endif

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

void lista_doble_inicializar(ListaDoble *lista) {
  lista->cabeza = NULL;
  lista->cola = NULL;
}

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

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

void lista_doble_eliminar_nodo(ListaDoble *lista, NodoDoble *nodo) {
  if (!nodo) return;
  if (nodo->ant) {
    nodo->ant->sig = nodo->sig;
  } else {
    lista->cabeza = nodo->sig;
  }
  if (nodo->sig) {
    nodo->sig->ant = nodo->ant;
  } else {
    lista->cola = nodo->ant;
  }
  free(nodo);
}

void lista_doble_imprimir(const ListaDoble *lista) {
  const NodoDoble *reco = lista->cabeza;
  while (reco) {
    printf("%d -> ", reco->valor);
    reco = reco->sig;
  }
  puts("NULL");
}

void lista_doble_imprimir_inverso(const ListaDoble *lista) {
  const NodoDoble *reco = lista->cola;
  while (reco) {
    printf("%d <- ", reco->valor);
    reco = reco->ant;
  }
  puts("NULL");
}

void lista_doble_limpiar(ListaDoble *lista) {
  NodoDoble *reco = lista->cabeza;
  while (reco) {
    NodoDoble *tmp = reco->sig;
    free(reco);
    reco = tmp;
  }
  lista->cabeza = NULL;
  lista->cola = NULL;
}

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

int main(void) {
  ListaDoble lista;
  lista_doble_inicializar(&lista);
  lista_doble_insertar_inicio(&lista, 10);
  lista_doble_insertar_final(&lista, 20);
  lista_doble_insertar_inicio(&lista, 5);
  lista_doble_imprimir(&lista);
  lista_doble_imprimir_inverso(&lista);
  lista_doble_eliminar_nodo(&lista, lista.cabeza->sig);
  lista_doble_imprimir(&lista);
  lista_doble_limpiar(&lista);
  return 0;
}

Copia cada sección en su archivo dentro de CLion, compila y ejecuta para comprobar el comportamiento en ambos sentidos.

Ilustración de lista doblemente enlazada

Retornar

6 - Operaciones en listas doblemente enlazadas