Separate Marked and Unmarked Nodes into Disjoint Lists
Locating a marked or unmarked node should be constant time always, to allow programs that iterate through every node to always be constant time. This can be achieved by separating nodes into two arrays: one for marked and one for unmarked nodes.
Having a separate list for every mark needs serious consideration as well.