GUÍA 30-09-26 Estructuras de Datos

CN122 · miércoles 30/09/2026 · 13:00-14:15 · Sesión 15

Listas ligadas simples: búsqueda y acceso

EL PRECIO DEL ENLACE

En un arreglo el elemento i se calcula. En una lista hay que caminar desde la cabeza contando nodos: el acceso por posición es O(n). Ese es el costo de la flexibilidad ganada en la inserción.

RECORRIDO ESTÁNDAR

• Nodo *p = cabeza; while (p != NULL) { … ; p = p->sig; }
• Nunca modificar cabeza durante el recorrido: se pierde el acceso a la lista.

BÚSQUEDA

Secuencial y O(n) sin excepción. Aunque la lista esté ordenada no se puede hacer búsqueda binaria, porque no hay acceso directo al elemento medio. Es una limitación estructural, no de implementación.

DEVOLVER EL ANTERIOR

Casi todas las operaciones de modificación necesitan el nodo previo. Conviene escribir una función que devuelva ambos, o llevar dos apuntadores durante el recorrido: uno actual y uno anterior.

LISTA CONTRA ARREGLO

• Acceso por índice: arreglo O(1), lista O(n).
• Inserción al inicio: arreglo O(n), lista O(1).
• Inserción al final: arreglo O(1) amortizado, lista O(1) con apuntador a cola.
• Memoria: el arreglo necesita bloque contiguo; la lista gasta un apuntador extra por nodo.
• Caché: el arreglo gana con claridad; los nodos dispersos causan fallos de caché constantes.

En la práctica los arreglos ganan más seguido de lo que la teoría sugiere, precisamente por la caché. La lista brilla cuando hay muchas inserciones y borrados en posiciones arbitrarias.

TÉCNICAS ÚTILES

• Nodo centinela — un nodo ficticio al inicio elimina el caso especial de insertar en cabeza.
• Dos apuntadores a distinta velocidad — detecta ciclos y encuentra el elemento medio en una pasada.

PRÁCTICA

Búsqueda con devolución de anterior, conteo de nodos, y detección de ciclo con el algoritmo de la liebre y la tortuga.