Lista simplemente enlazada

Metadatos

• nodo* head
• size_t cant
• nodo* tail

Nodo

• nodo* siguiente
• void*

Primitivas

• Lista* crear() → O(1)
• void destruir(Lista* l) → O(n)
• boolean insert_first(void*value, Lista *l) → true si todo salió bien (pudo crear el espacio en memoria con un malloc) y false si no había y quedó NULL → O(1)

bool insert_first(val, l){
nodo*	new = malloc(sizeof(nodo))
if(!new) return False

• boolean insert_last(.. igual al first) → O(1)
• void* pop_first(Lista *l) → O(1)
• void* pop_last(Lista *l) → O(n) aunque tenga el tail
• size_t cant(Lista* l) → O(1)

Ejercicio

Dada una lista ordenada [1] → [2] → [2] → [3]