Fully persistent linked list

Why isn't there any implementation (in C, C ++, Java, or even Python ...) of a completely persistent (not necessarily functional) linked list that has constant time / space overhead in the number of modifications?

I mean the data structure described in this article: http://www.cs.cmu.edu/~sleator/papers/Persistence.htm

After a long search on google, I could not find even a partially duplicate implementation of linked lists with the above overhead.

PS: The definitions of persistence I'm talking about are the ones described on the next page on Wikipedia: http://en.wikipedia.org/wiki/Persistent_data_structure

EDIT (after asking the question on hold):

I don't think the reason mentioned is relevant to my question. I am not really asking for recommendations among the different libraries available, so there can be no "stubborn answers and spam". My question is amazement that a data structure that should be great in theory has not been implemented by any known language. So before I implemented it myself, I asked this question to see if there was an answer: "It's okay, the X data structure dominates the one you're looking for, and why it wasn't implemented despite its simplicity." Another answer might be "This is not as good as you think, as there is a large hidden constant" or "this is not very good with how caches are created these days" ... I apologize if my question was not clear enough ... I changed my question to make the request more explicit.

+3


source to share


1 answer


Have you tried the Java functional library? It got some persistent data structures:



http://www.functionaljava.org/features.html

+1


source







All Articles