Space complexity is the issue for only a subset of problems, those with extremely large input sets. I think those cases are the exception rather than the rule. I certainly agree that special techniques are required with gigantic or streaming data sets. Finding that size limit is probably interesting... I guess my inclination is to go for either the hash table or search tree solution unless I really, really have to implement some special algorithm.<p>How would you ever not know the start state of the mark on each node? It's a field you invented, null field = not seen.  If you are talking about a very large list, it's not going to fit into memory - things tend to get extremely tricky with really big data sets like that. It could be perhaps a node per file ? File where you can add an additional field?