 # Implementing a queue based on a list zipper?

Hi all,

How to implement a queue in Elixir with O(1) insertion and O(1) deletion using a list zipper?

According to this blog post on zippers, one can use a list zipper to have a queue-like behaviour:

Zipper lists are conceptually simple enough to be easy to reinvent and replace with queues.

Considering the following zipper:

``````defmodule Zipper.ListZipper do
defguard is_range(range) when is_struct(range, Range)

def new, do: {[], []}

def from_list(list) when is_list(list), do: {[], list}

def from_range(range) when is_range(range), do: from_list(Enum.to_list(range))

def to_list({prev, next}), do: Enum.reverse(prev) ++ next

def prev({[], next}), do: {[], next}

def current({_, []}), do: nil
def current({_, [current | _]}), do: current

def pop({_, []} = lzip), do: {nil, lzip}
def pop({prev, [current | tail]}), do: {current, {prev, tail}}

def next({prev, []}), do: {prev, []}

def replace({prev, []}, val), do: {prev, [val]}
def replace({prev, [_ | next]}, val), do: {prev, [val | next]}

def put({prev, next}, val), do: {prev, [val | next]}

def delete({prev, []}), do: {prev, []}
def delete({prev, [_ | next]}), do: {prev, next}
end
``````

If I insert the sequence `1, 2, 3` into the list zipper, the `current` will point to the last element `3`:

``````iex(9)> ListZipper.new()|> ListZipper.put(1) |> ListZipper.put(2) |> ListZipper.put(3)
{[], [3, 2, 1]}
``````

Now, I could use `next` to move the `current` to the first inserted element everytime I call `put/2` (unless the zipper has only one element):

``````iex(10)> ListZipper.new()|> ListZipper.put(1) |> ListZipper.put(2) |> ListZipper.next() |> ListZipper.put(3) |> ListZipper.next()
{[3, 2], }
``````

However, I still need to go through the whole list to get the second element `2` :think
Is it possible, or did I misunderstood the quoted sentence in the blog post?

Looking at the queue implementation in Elixir in rosettacode, I get the gist of it.

We use two queues, (input/output queues). When we want to pop, the input queue becomes the output queues and is reversed. Next time we want to pop, we won’t need to reverse the output queue (because it isn’t empty).

This is not always O(1) but it looks like a good compromise.

I think the Erlang queue module implements kind of the same thing. When you call `:queue.new()` it yelds a similar initial state: `{[], []}`.

1 Like