Listas enlazadas en C - Operaciones en listas simples

Flujo general

Una lista simplemente enlazada basa su comportamiento en insertar, eliminar, buscar y recorrer nodos que solo conocen a su sucesor. A continuación se detalla cada operación clave con ejemplos en C y recomendaciones de memoria.

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

typedef struct {
  Nodo *cabeza;
} Lista;

void lista_inicializar(Lista *lista) {
  lista->cabeza = NULL;
}

5.1 Insertar al inicio

Es la operación más eficiente: basta con apuntar el nuevo nodo a la antigua cabeza y actualizar el puntero principal.

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

bool lista_insertar_inicio(Lista *lista, int valor): Crea una función que recibe la lista y el nuevo valor, devolviendo true en caso de éxito.
Nodo *n = malloc(sizeof(Nodo));: Reserva memoria para el nuevo nodo.
if (!n) return false;: Verifica que la reserva haya sido exitosa; de lo contrario, informa fallo.
n->valor = valor;: Guarda el dato proporcionado en el campo del nodo.
n->sig = lista->cabeza;: Enlaza el nodo para que apunte al antiguo primer elemento.
lista->cabeza = n;: Actualiza el puntero principal para que el nuevo nodo sea la cabeza.
return true;: Confirma que la operación se realizó correctamente.

5.2 Insertar al final

Requiere recorrer hasta el último nodo a menos que mantengamos un puntero a cola. El siguiente ejemplo muestra la versión sin cola.

bool lista_insertar_final(Lista *lista, int valor) {
  Nodo *n = malloc(sizeof(Nodo));
  if (!n) return false;
  n->valor = valor;
  n->sig = NULL;
  if (!lista->cabeza) {
    lista->cabeza = n;
    return true;
  }
  Nodo *reco = lista->cabeza;
  while (reco->sig) {
    reco = reco->sig;
  }
  reco->sig = n;
  return true;
}

bool lista_insertar_final(Lista *lista, int valor): Define la función que insertará al final y reportará éxito o fallo.
Nodo *n = malloc(sizeof(Nodo));: Reserva memoria para el nuevo nodo.
if (!n) return false;: Sale con error si no hay memoria disponible.
n->valor = valor;: Asigna el dato al nodo.
n->sig = NULL;: El nuevo nodo no apunta a nadie porque quedará al final.
if (!lista->cabeza) { ... }: Si la lista estaba vacía, el nuevo nodo se convierte en la cabeza y termina.
Nodo *reco = lista->cabeza;: Comienza un recorrido desde el primer nodo.
while (reco->sig) { reco = reco->sig; }: Avanza hasta el último nodo actual.
reco->sig = n;: Enlaza el último nodo con el nuevo.
return true;: Finaliza confirmando que la inserción se completó.

5.3 Insertar en posición específica

Consiste en recorrer hasta el nodo previo a la posición deseada y actualizar los punteros. Si la posición es 0, se aprovecha la función de inserción al inicio.

bool lista_insertar_en(Lista *lista, int posicion, int valor) {
  if (posicion <= 0 || !lista->cabeza) {
    return lista_insertar_inicio(lista, valor);
  }
  Nodo *reco = lista->cabeza;
  for (int i = 0; reco && i < posicion - 1; ++i) {
    reco = reco->sig;
  }
  if (!reco) return false;
  Nodo *n = malloc(sizeof(Nodo));
  if (!n) return false;
  n->valor = valor;
  n->sig = reco->sig;
  reco->sig = n;
  return true;
}

bool lista_insertar_en(Lista *lista, int posicion, int valor): Define la operación para insertar en una posición específica.
if (posicion <= 0 || !lista->cabeza): Si la posición es 0 o la lista está vacía, recicla la inserción al inicio.
Nodo *reco = lista->cabeza;: Inicializa un puntero para recorrer.
for (int i = 0; reco && i < posicion - 1; ++i): Avanza hasta el nodo anterior a la posición requerida, cuidando no pasar de NULL.
if (!reco) return false;: Si no se encontró un nodo válido, la posición es inválida.
Nodo *n = malloc(sizeof(Nodo));: Reserva memoria para el nuevo nodo.
if (!n) return false;: Verifica la reserva antes de continuar.
n->valor = valor;: Guarda el dato.
n->sig = reco->sig;: Apunta el nuevo nodo al siguiente del nodo previo.
reco->sig = n;: Inserta el nuevo nodo entre reco y el resto de la lista.
return true;: Confirma que la inserción se completó.

5.4 Eliminar primer nodo

Solo se mueve la cabeza al segundo nodo y se libera el primero.

bool lista_eliminar_primero(Lista *lista) {
  if (!lista->cabeza) return false;
  Nodo *victima = lista->cabeza;
  lista->cabeza = victima->sig;
  free(victima);
  return true;
}

bool lista_eliminar_primero(Lista *lista): Define la operación de eliminar el primer nodo.
if (!lista->cabeza) return false;: Si la lista está vacía no hay nada que borrar.
Nodo *victima = lista->cabeza;: Guarda el puntero al nodo que se eliminará.
lista->cabeza = victima->sig;: Mueve la cabeza al segundo nodo.
free(victima);: Libera la memoria del nodo inicial.
return true;: Indica que la eliminación fue exitosa.

5.5 Eliminar último nodo

Necesita llegar al penúltimo nodo para cortar el enlace y liberar el final.

bool lista_eliminar_ultimo(Lista *lista) {
  if (!lista->cabeza) return false;
  if (!lista->cabeza->sig) {
    free(lista->cabeza);
    lista->cabeza = NULL;
    return true;
  }
  Nodo *reco = lista->cabeza;
  while (reco->sig->sig) {
    reco = reco->sig;
  }
  free(reco->sig);
  reco->sig = NULL;
  return true;
}

bool lista_eliminar_ultimo(Lista *lista): Encapsula la eliminación del nodo final.
if (!lista->cabeza) return false;: Si no hay nodos, la operación no se realiza.
if (!lista->cabeza->sig): Casos de un solo nodo: se libera la cabeza y se deja NULL.
Nodo *reco = lista->cabeza;: Inicia un recorrido desde el primer elemento.
while (reco->sig->sig): Avanza hasta el penúltimo nodo (el que tiene un sig cuyo sig es NULL).
free(reco->sig);: Libera el último nodo.
reco->sig = NULL;: Actualiza el penúltimo nodo para que sea el nuevo final.
return true;: Confirma que la operación se completó.

5.6 Eliminar nodo específico

Se busca el nodo previo al que queremos eliminar para reajustar el enlace. Si el valor está en la cabeza, se aprovecha la función anterior.

bool lista_eliminar_valor(Lista *lista, int valor) {
  if (!lista->cabeza) return false;
  if (lista->cabeza->valor == valor) {
    return lista_eliminar_primero(lista);
  }
  Nodo *reco = lista->cabeza;
  while (reco->sig && reco->sig->valor != valor) {
    reco = reco->sig;
  }
  if (!reco->sig) return false;
  Nodo *victima = reco->sig;
  reco->sig = victima->sig;
  free(victima);
  return true;
}

bool lista_eliminar_valor(Lista *lista, int valor): Permite eliminar el primer nodo que contenga el valor indicado.
if (!lista->cabeza) return false;: Si la lista está vacía, no se hace nada.
if (lista->cabeza->valor == valor): Si el valor está en la cabeza, se reaprovecha la función de eliminación inicial.
Nodo *reco = lista->cabeza;: Inicio del recorrido para encontrar el nodo previo.
while (reco->sig && reco->sig->valor != valor): Avanza mientras haya nodos y el siguiente no contenga el valor buscado.
if (!reco->sig) return false;: Si se llega al final sin encontrarlo, se informa que no existe.
Nodo *victima = reco->sig;: Guarda el nodo que será eliminado.
reco->sig = victima->sig;: Saltea el nodo objetivo, enlazando el previo con el siguiente.
free(victima);: Libera la memoria del nodo eliminado.
return true;: Reporta éxito.

5.7 Buscar un elemento

Se recorre secuencialmente hasta encontrar el valor o llegar al final. Puede devolver el puntero al nodo o solo un indicador booleano.

Nodo *lista_buscar(const Lista *lista, int valor) {
  const Nodo *reco = lista->cabeza;
  while (reco) {
    if (reco->valor == valor) {
      return (Nodo *)reco;
    }
    reco = reco->sig;
  }
  return NULL;
}

Nodo *lista_buscar(const Lista *lista, int valor): Devuelve un puntero al nodo que contiene el valor buscado o NULL.
const Nodo *reco = lista->cabeza;: Inicia un puntero de lectura en la cabeza.
while (reco): Recorre mientras existan nodos.
if (reco->valor == valor): Compara el valor actual con el buscado.
return (Nodo *)reco;: Retorna el nodo encontrado (el casteo elimina la constancia para reutilizarlo).
reco = reco->sig;: Avanza al siguiente nodo.
return NULL;: Si termina el recorrido sin coincidencias, indica que no existe.

5.8 Recorrer e imprimir

Funciona igual que la búsqueda, pero imprime el contenido. Es una herramienta de depuración sencilla.

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

void lista_imprimir(const Lista *lista): Declara una función de depuración que no modifica la lista.
const Nodo *reco = lista->cabeza;: Ubica un puntero de solo lectura en el primer nodo.
while (reco): Recorre la lista hasta encontrar NULL.
printf("%d -> ", reco->valor);: Muestra el valor del nodo seguido de una flecha.
reco = reco->sig;: Avanza al siguiente nodo.
puts("NULL");: Indica el final de la lista con un texto centinela.

5.9 Manejo de memoria y liberación correcta

La función de limpieza debe recorrer todos los nodos y liberar cada bloque. También es buena idea poner la cabeza en NULL para evitar accesos a memoria liberada.

void lista_limpiar(Lista *lista) {
  Nodo *reco = lista->cabeza;
  while (reco) {
    Nodo *tmp = reco->sig;
    free(reco);
    reco = tmp;
  }
  lista->cabeza = NULL;
}

void lista_limpiar(Lista *lista): Comienza la función dedicada a liberar todos los nodos.
Nodo *reco = lista->cabeza;: Apunta a la cabeza para iniciar el recorrido.
while (reco): Continúa hasta que no queden nodos.
Nodo *tmp = reco->sig;: Guarda la referencia al siguiente nodo antes de liberar el actual.
free(reco);: Libera la memoria del nodo actual.
reco = tmp;: Avanza al siguiente nodo usando la referencia guardada.
lista->cabeza = NULL;: Una vez terminada la limpieza, resetea la cabeza para evitar punteros colgantes.

En proyectos grandes se recomienda envolver malloc/free en funciones propias para centralizar verificaciones y logs.

5.10 Código completo para practicar en CLion

Para consolidar las operaciones anteriores, a continuación se muestra un pequeño proyecto listo para compilar en CLion:

/* lista.h */
#ifndef LISTA_H
#define LISTA_H
#include <stdbool.h>

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

typedef struct {
  Nodo *cabeza;
} Lista;

void lista_inicializar(Lista *lista);
bool lista_insertar_inicio(Lista *lista, int valor);
bool lista_insertar_final(Lista *lista, int valor);
bool lista_insertar_en(Lista *lista, int posicion, int valor);
bool lista_eliminar_primero(Lista *lista);
bool lista_eliminar_ultimo(Lista *lista);
bool lista_eliminar_valor(Lista *lista, int valor);
Nodo *lista_buscar(const Lista *lista, int valor);
void lista_imprimir(const Lista *lista);
void lista_limpiar(Lista *lista);

#endif

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

void lista_inicializar(Lista *lista) {
  lista->cabeza = NULL;
}

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

bool lista_insertar_final(Lista *lista, int valor) {
  Nodo *n = malloc(sizeof(Nodo));
  if (!n) return false;
  n->valor = valor;
  n->sig = NULL;
  if (!lista->cabeza) {
    lista->cabeza = n;
    return true;
  }
  Nodo *reco = lista->cabeza;
  while (reco->sig) {
    reco = reco->sig;
  }
  reco->sig = n;
  return true;
}

bool lista_insertar_en(Lista *lista, int posicion, int valor) {
  if (posicion <= 0 || !lista->cabeza) {
    return lista_insertar_inicio(lista, valor);
  }
  Nodo *reco = lista->cabeza;
  for (int i = 0; reco && i < posicion - 1; ++i) {
    reco = reco->sig;
  }
  if (!reco) return false;
  Nodo *n = malloc(sizeof(Nodo));
  if (!n) return false;
  n->valor = valor;
  n->sig = reco->sig;
  reco->sig = n;
  return true;
}

bool lista_eliminar_primero(Lista *lista) {
  if (!lista->cabeza) return false;
  Nodo *victima = lista->cabeza;
  lista->cabeza = victima->sig;
  free(victima);
  return true;
}

bool lista_eliminar_ultimo(Lista *lista) {
  if (!lista->cabeza) return false;
  if (!lista->cabeza->sig) {
    free(lista->cabeza);
    lista->cabeza = NULL;
    return true;
  }
  Nodo *reco = lista->cabeza;
  while (reco->sig->sig) {
    reco = reco->sig;
  }
  free(reco->sig);
  reco->sig = NULL;
  return true;
}

bool lista_eliminar_valor(Lista *lista, int valor) {
  if (!lista->cabeza) return false;
  if (lista->cabeza->valor == valor) {
    return lista_eliminar_primero(lista);
  }
  Nodo *reco = lista->cabeza;
  while (reco->sig && reco->sig->valor != valor) {
    reco = reco->sig;
  }
  if (!reco->sig) return false;
  Nodo *victima = reco->sig;
  reco->sig = victima->sig;
  free(victima);
  return true;
}

Nodo *lista_buscar(const Lista *lista, int valor) {
  const Nodo *reco = lista->cabeza;
  while (reco) {
    if (reco->valor == valor) {
      return (Nodo *)reco;
    }
    reco = reco->sig;
  }
  return NULL;
}

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

void lista_limpiar(Lista *lista) {
  Nodo *reco = lista->cabeza;
  while (reco) {
    Nodo *tmp = reco->sig;
    free(reco);
    reco = tmp;
  }
  lista->cabeza = NULL;
}

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

int main(void) {
  Lista lista;
  lista_inicializar(&lista);
  lista_insertar_inicio(&lista, 10);
  lista_insertar_final(&lista, 20);
  lista_insertar_en(&lista, 1, 15);
  lista_imprimir(&lista);
  lista_eliminar_valor(&lista, 15);
  lista_eliminar_ultimo(&lista);
  lista_imprimir(&lista);
  lista_limpiar(&lista);
  return 0;
}

Esquema de inserciones y eliminaciones en lista simple

Copia cada sección en su archivo correspondiente dentro de CLion, compila y ejecuta para validar todas las operaciones.

Retornar

5 - Operaciones en listas simplemente enlazadas