← Volver a los ejercicios

Lo que cobra cada implementación

Las cuatro implementaciones responden al mismo contrato de lista: enlazada simple, doblemente enlazada, circular doble y circular doble que llega a la posición por el lado corto. Cuatro programas, cada uno con su perfil de uso.

1. Borrar nodos que ya se tienen

El programa guarda punteros a los elementos que inserta y más tarde los borra uno por uno con esos punteros. No consulta posiciones ni recorre hacia atrás.

2. Mover el frente en cada vuelta

En cada vuelta el primer elemento pasa al final y el segundo queda de primero. El orden relativo de los elementos no cambia.

3. Consultar posiciones cerca del final

El programa llama obtener(p) muchas veces, casi siempre con posiciones del último cuarto de la lista. Inserta poco y no borra.

4. Insertar al frente y recorrer una vez

El programa inserta cada dato que llega en la posición 0 y, cuando no llegan más, recorre la lista una sola vez de principio a fin. Nada más.

5. Lo que cuesta insertar al frente

Sobre una lista que ya tiene elementos, insertar(0, e) es Θ(1) en las cuatro, pero no ejecuta el mismo número de asignaciones de puntero. Cuente las que ejecuta cada una, contando la que mueve cabeza y la que deja un campo en NULL.

Enlazada simple
Doblemente enlazada
Circular doble
Circular, por el lado corto