Are there any Doubly Linked List / Deque Libraries or Custom Implementations?

Hello! Firstly, I would like to offer my thanks to this amazing Elixir community that has really made my life easier in learning elixir. Thank you so much everyone.

As my question states, are there any doubly linked list or deque libraries present in Elixir/Hex? I know of Dlist, however, it doesn’t has the pop and remove functions which is like a core of such data structures.

If there aren’t any such libraries, has anyone tried making their custom implementations of these data structures and would be willing to share their work?

You might look at the :queue module that is built in. It might suit your needs (or it might not).

3 Likes

Erlang itself provides double-ended queues as part of the :queue module.
Of course, this does not very nicely integrates with Elixir (like Collectable, Enum(erable) and Inspect).

Libraries like for instance Okasaki disclaimer: I am its author provide nicer integration and a nicer API, as well as various different implementations (besides one based on :queue) which you can benchmark for your use-case so you can decide which is the most appropriate.

7 Likes

@Qqwy is the resident data structures person in the community :slight_smile:

3 Likes

For this problem from AoC 2018, I wrote a doubly-linked circular list built on top of ETS:

Each entry in ETS is a 3-tuple:

{value, left_value, right_value}

In this problem, value is unique (no duplicate-numbered marbles) so it works fine as an identifier.

The circular list was efficient here because all of the rules in the problem are phrased in terms of offsets from the “current position”; no matter how big the list of marbles gets, each round only requires going forward or backwards by a fixed amount.

That’s also my general advice for picking data structures: think about what you need them to do, and find a shape that makes that operation efficient.

2 Likes

This looks pretty good. Will check this out. Thank you!

1 Like

Thank you for sharing this! Will definitely explore this :+1: