Inserting at the head of a linked list is O(1), but this involves moving pointers, and they are not constant size
We usually analyze algorithms using the RAM model, in which basic operations on machine words cost $O(1)$. On an input of length $n$ bits, the size of a machine word is $\log n$. In your case, a pointer should fit into one machine word, and so moving a pointer should take $O(1)$ time.

A different issue is how much time is required to maintain the heap. One way around this is to work in the "heap-enabled RAM model", in which heap operations are for free. Probably many papers on algorithms implicitly work in this model.

Finally, a few words on the RAM model. It extends the Turing machine model in two ways. First, it allows indexing. This matches the way actual computers work. Second, it allows constant time arithmetic on machine words, which are usually chosen as indicated above. The size of machine words is chosen so that operations on indices take $O(1)$. For example, consider the following program for summing an array $A$:

sum = 0
for i from 1 to n:
  sum = sum + A[i]
return sum


If we want this algorithm to run in $O(n)$, we need the operation $i \to i + 1$ to run in $O(1)$. Since $i$ could be $\log n$ bits long, we need machine words to be at least $\log n$ bits long. Practice shows that it is not necessary to consider larger machine words. Note that machine words of size $C\log n$ can be simulated using $O(1)$ machine words of size $\log n$ using a multiplicative overhead of $O(1)$; since we don't care about constant factors, increasing the machine word to size $C\log n$ doesn't affect the power of the model.