Java – How to increase the efficiency of an Immutable Queue in java

data structuresimmutabilityjavaqueue

I have been developing an Immutable queue in java, but the version I have developed is supposedly slow and I have been suggested to create a faster version of the same and I have no idea as to how to accomplish that.

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class ImmutableQueueImpl<E> implements ImmutableQueue<E>
{

    private List<E> queue;
    public ImmutableQueueImpl()
    {
       queue=new ArrayList<E>();
    }

    public ImmutableQueueImpl(List<E> queue)
    {
       this.queue=queue;
    }

    public ImmutableQueue<E> enqueue(E e)
    {
            if(e==null) throw new IllegalArgumentException();
            List<E> clone = new ArrayList<E>(queue);
            clone.add(e);
            return new ImmutableQueueImpl<E>(clone);
    }

    public ImmutableQueue<E> dequeue()
    {
            if(queue.isEmpty())
            {
              throw new NoSuchElementException();
            }
            List<E> clone = new ArrayList<E>(queue);
            clone.remove(0);
            return new ImmutableQueueImpl<E>(clone);
    }

    public E peek()
    {
            if(queue.isEmpty()) throw new NoSuchElementException();
            return queue.get(0);
    }


public int size()
{
    return queue.size();
}
}

Please suggest any improvements in the implementation or the libraries used .

We remove elements from immutable lists all the time and dequeue is just a special case of that. The point is that the result is not really the element, but another immutable list without it. The point of this design is mutation safety and way better in parallelized settings than mutable data structures.

Best Answer

You should read up on structure sharing for immutable datatypes. Obviously, when your enqueue involves creating a complete clone of that list, then your enqueue is O(n). The whole idea of structure sharing is that you return a new object, that in some way reuses the original object such as to avoid this duplication.

For your queue implementation in particular, you cannot simply rely on a mutable Java ArrayList. Take a look at some functional language and cons-cells for constructing immutable list datastructures. They allow you to simply keep track of start and end elements of your queue and derive a new queue object by reusing all cons-cells and simply adding a new one. The new object reuses the original cons-cells, but has a different end-pointer to the newly added cons cell.

Long story short: When writing immutable datastructures avoid copies and share structures instead.

In response to the comment about Java: All of this is language-agnostic. It is just that functional languages have been working with immutable datastructures for decades, whereas it is a relatively recent trend to add immutability to OO languages. All of this structure sharing, cons-cells, etc. is implementable in any programming language (well, Turing-complete that is).

Related Topic