Memory used during GC

During the "mark-reachable" phase of GC, there clearly needs to be a
list of objects pending marking. So in my implementation, I reserve 4
bytes per object and form a linked list of pending objects. This is good
news since it means that no extra memory is required, and the algorithm
is guaranteed to succeed. But that seems wasteful, since a linked list
is slightly slower than an array, and the reserved memory is of no use
at any other time. Also the 4 bytes is completely wasted for objects
that are not live during marking, so a stack is likely to use less
overall memory.

So wouldn't it be better to reserve this memory when I need it, and
return it to the system when finished GC. I expect it would quicker and
less wasteful. The down-side is that the system might deny a memory
request and then it all goes horribly wrong...

Does anybody else have experiences of this sort of thing, or are there
approaches I have not thought of?

Cheers, Calum