GUÍA 28-09-26 Estructuras de Datos

CN122 · lunes 28/09/2026 · 13:00-14:15 · Sesión 14

Listas ligadas simples: estructura e inserción

EL CAMBIO DE PARADIGMA

Hasta aquí toda estructura vivía en memoria contigua. Una lista ligada rompe eso: cada nodo se aloja donde haya lugar y guarda la dirección del siguiente. El orden ya no lo da la posición física sino los enlaces.

EL NODO

• typedef struct Nodo { int dato; struct Nodo *sig; } Nodo;
• La estructura debe nombrarse para poder referirse a sí misma; un typedef anónimo no funciona aquí.
• La lista se identifica por un apuntador a su primer nodo; NULL significa lista vacía.

MEMORIA DINÁMICA

• malloc(sizeof(Nodo)) reserva y devuelve la dirección, o NULL si falla. Siempre hay que verificar.
• free(p) libera. Cada malloc necesita exactamente un free.
• Después de free, el apuntador queda colgante: conviene ponerlo en NULL.

INSERCIÓN AL INICIO

1. Reservar el nodo nuevo y llenar su dato.

2. nuevo->sig = cabeza.

3. cabeza = nuevo.

Es O(1) y no depende del tamaño de la lista. Ese es el argumento fuerte a favor de las listas.

INSERCIÓN AL FINAL Y EN POSICIÓN

Al final cuesta O(n) porque hay que recorrer, salvo que se mantenga un apuntador a la cola. En posición intermedia hay que detenerse en el anterior: si te pasas al nodo objetivo, ya no puedes enlazar hacia atrás.

EL ORDEN DE LAS ASIGNACIONES IMPORTA

Si haces anterior->sig = nuevo antes de nuevo->sig = anterior->sig, pierdes el resto de la lista de forma irrecuperable. Es el error más frecuente del tema y no produce ningún mensaje de error.

PRÁCTICA

Implementar inserción al inicio, al final y en posición ordenada, con impresión completa de la lista.