> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever?

Yes.