[racket] doubly linked list lib

On Tue, Aug 30, 2011 at 02:29:34PM +0200, Laurent wrote:
> On Tue, Aug 30, 2011 at 12:52, Jos Koot <jos.koot at telefonica.net> wrote:
> 
> > **
> > You are stating: hash with bounded memory
> > Does that mean you will have a limit on the number of entries?
> >
> 
> Not necessarily. It might grow, although I might limit it to logarithmic
> growth.
> Or the bound may be very large but unknown, and little memory should be used
> most of the time.
> 
> 
> > In that case a vector plus a current index might do, I think.
> > Gives you O(1) access to every element.
> > If the required number of elements may vary very much, a vector probably is
> > not a good idea, unless using resizable vectors, but that makes some
> > operations O(n).
> >
> 
> A hash+vector would nearly do it, but in the end it might not get any
> simpler than a doubly linked list.
> I also need to move items at the end of the list too.
> 
> I should add that this is not for production purpose, but for more
> "theoretical" properties, so I don't care much about a potential constant
> overhead per operation, but I care about how it would behave with an
> increasing number of items.
> 
> Laurent

Would you lso want entries to be garbage-collected?  If there are no 
longer any references to a hash entry's key except as a key in the hash 
table, would you want the garbage colelctor to be able to remove it?

-- hendrik