[racket] doubly linked list lib

On Tue, Aug 30, 2011 at 12:23, Stephen Bloch <sbloch at adelphi.edu> wrote:

>
> On Aug 30, 2011, at 3:18 AM, Laurent wrote:
>
> Thank you very much for this nice intermediate solution, though I need
> constant-time append, split, insert, remove, + pointers to items, etc.
> Mutation does seem unavoidable, right.
>
>
> The "zipper" structure Neil posted has constant-time append if you're
> already at the head of one zipper and the tail of the other, but in general
> it'll be linear time.  It has constant-time split, insert, and remove.
>

Not if you are not already at the right place in the lists.
Finding the place of the element in the list would take linear time.


>   What do you mean by "pointers to items" -- that is, what do you need to
> DO with pointers to items?
>

Items are struct instances. By pointers I meant references, as they are
handled automatically in Racket.
The list of items gives me a modifiable preference order on the items (the
preference criterion may vary).
Each hash entry holds a "reference" to an item, and an item holds a
reference to the previous and next elements in the list.
For example, given a key in the hash I get the reference to the item, and I
can then put that element at the end of the list, or exchange it with the
next element, or remove it, etc.
This does not seem possible with the same time complexity with zippers.

Laurent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110830/aa26c2d5/attachment.html>