[erlang-questions] how are implemented lists?

[Roger Lipscombe]

On 25 May 2015 at 08:14, Benoit Chesneau <bchesneau@REDACTED> wrote:
> Indeed; sorry for that: So indeed that is this kind of data structure that I
> would like to have. Was thinking to use a skip-list data-structure as a nif
> but that may be overkill..

You want:

> a fast and concurrent data structure that allows me to retrieve the items
> in order and do pop/tail, while still being abble to remove them by key.

When you say "remove by key", do you need to retrieve the value, or do
you need to simply discard it?

I'm thinking that an ordinary list, coupled with an ordinary set,
might be what you want. When you remove the value, you _don't_ remove
it; you put it in the dictionary. Then, when it comes time to pop the
head, just look to see if the value is in the dictionary, and should
be ignored. Drop it on the floor, remove it from the dictionary. Done.

Obviously this depends on your exact use case, and the frequency of
the different operations. It also won't necessarily work if you want
to reuse a key, but you might be able to fudge that with some kind of
generation ID.

Cheers,
Roger.