Una lista enlazada guarda cada valor en su propio nodo del heap, y cada nodo apunta al siguiente; el último apunta a NULL. La lista es solo un puntero al primer nodo, la cabeza. Añadir al principio es barato: crea un nodo cuyo next sea la antigua cabeza, y pasa a ser la nueva.
Recorrer la lista usa un puntero que avanza por los enlaces: for (p = head; p != NULL; p = p->next). No hay índices, así que llegar al décimo elemento significa seguir diez enlaces, y los nodos están dispersos por la memoria, lo que es lento para la caché comparado con un array.
Liberar exige cuidado: guarda p->next antes de llamar a free(p), porque leer un nodo después de liberarlo es comportamiento indefinido.
El nodo nuevo apunta a la antigua cabeza y pasa a ser la cabeza.