[racket] doubly linked list lib

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110830/2fbc256e/attachment.html>